ARC选做

atcoder

ARC176A

考虑斜线构造，一条斜线可以做到给每行每列一个 $1$，这是非常好的，而且两条斜线互相不会干扰，当然这个斜线实际是环状的：每次往左上走一步放 $1$ ，到达边界就飞到另一边，从左边界到右边界，上到下。

从每个给定点出发去跑斜线，如果经过了别的给定点就说明还要额外再找点出发，这样肯定是可以的，但是实现可能有点复杂。

我们可以考虑对于每个给定点 $O(n)$ 的 找出其对应的在第一行的点，从这些点跑即可，如果少了就顶多 $O(n)$ 的扫一遍底端点补到 $m$ 个即可。

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m;
int x,y;
bool ok[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        while(x>1){
            x--,y++;
            if(y==n+1) y=1;
        }
        ok[y]=1;
    } 
    int sum=0;
    for(int i=1;i<=n;i++){
        if(ok[i]) sum++;
    }
    int pos=1;
    while(sum<m){
        while(ok[pos]) pos++;
        ok[pos]=1,sum++;
    }
    cout<<n*m<<endl;
    for(int i=1;i<=n;i++){
        if(ok[i]){
            int x=1,y=i;
            while(x<=n){
                cout<<x<<" "<<y<<endl;
                x++,y--;
                if(y==0) y=n;
            }
        }
    }
}