AtCoder Beginner Contest 165 E - Rotation Matching

E - Rotation Matching

解説

まず操作ですが、人の数字割り当てが回転するのではなく、対戦場の割り当てが回転していくと考えても同じことです。 ある対戦場の割り当ては回回転するので、円形に考えると一周することになります。 同じ割り当てになってしまうのは、円における距離が等しい割り当てです。つまり、最初の段階で初期位置がかぶっておらず、距離が異なる個をとることができればいいです。偶奇によって実装が変わりますが、概ね似たような実装になります。

実装

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int N, M;
    cin >> N >> M;
    vector<i_i> ans;
    //奇数は単純
    if(N&1){
        for(int l = 1, r = N;l < r;l++,r--){
            ans.emplace_back(l, r);
        }
    }
    //偶数は途中で変えないといけない
    else{
        bool f = false;
        map<i_i, int> map;
        for(int l = 1,r = N; l < r; l++, r--){
            int a = r - l;
            int b = N - a;
            if(a > b)swap(a,b);
            if(!f&&(map[{a,b}]>0||a==b)){
                f = true;
                r--;
            }
            a = r-l;
            b = N-a;
            if(a > b)swap(a,b);
            ans.emplace_back(l, r);
            map[{a,b}]++;
        }
        print(map);
    }
    rep(i,M){
        cout << ans[i].first << " " << ans[i].second << endl;
    }
}