結果

問題 No.3256 Permutation Equation
ユーザー Iroha_3856
提出日時 2025-09-05 05:11:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,548 bytes
コンパイル時間 3,373 ms
コンパイル使用メモリ 287,412 KB
実行使用メモリ 12,456 KB
最終ジャッジ日時 2025-09-05 19:35:44
合計ジャッジ時間 15,617 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 48
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i, l, r) for (int i = (int)(l); i < (int)(r); i++)
#define siz(x) (int)(x).size()

int main() {
    int N; cin >> N;
    vector<int> P(N);
    rep(i, 0, N) {
        cin >> P[i];
        P[i]--;
    }

    vector<int> S(N);
    rep(i, 0, N) S[i] = (P[i] + 1) % N;

    vector<bool> seen(N, false);

    vector<vector<vector<int>>> cycles(N+1);

    rep(i, 0, N) {
        if (seen[i]) continue;
        int v = i;
        vector<int> cycle;
        do {
            cycle.push_back(v);
            seen[v] = true;
            v = S[v];
        } while(v != i);
        cycles[siz(cycle)].push_back(cycle);
    }

    vector<int> R(N);
    rep(l, 1, N+1) {
        if (l%2 == 0) {
            if ((int)cycles[l].size()%2 == 1) {
                cout << -1 << endl;
                return 0;
            }
            rep(i, 0, siz(cycles[l])/2) {
                vector<int> c1 = cycles[l][i*2], c2 = cycles[l][i*2+1];
                rep(t, 0, l) {
                    R[c1[t]] = c2[t];
                    R[c2[t]] = c1[(t+1)%l];
                }
            }
        }
        else {
            for (vector<int> c : cycles[l]) {
                rep(i, 0, siz(c)) {
                    //((l+1)/2) * 2 = (l + 1) = l (mod l)
                    R[c[i]] = c[(i+(l+1)/2)%l];
                }
            }
        }
    }

    vector<int> Q(N);
    rep(i, 0, N) {
        Q[i] = (R[i] - 1 + N) % N;
    }
    
    rep(i, 0, N) {
        cout << Q[i] + 1 << " ";
    }
    cout << endl;
}
0