結果

問題 No.100 直列あみだくじ
コンテスト
ユーザー codershifth
提出日時 2015-09-02 00:44:53
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 3,326 bytes
コンパイル時間 1,666 ms
コンパイル使用メモリ 166,144 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-24 01:37:35
合計ジャッジ時間 2,638 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;


class SeriesAmidakuji {
public:
    bool make_group(vector<int> &s, int start, vector<bool> &used, const vector<int> &A) {
            vector<int>  save_s = s;    // 上書きされるので
            vector<bool> save_u = used; // 上書きされるので
            int cur = start;

            do {
                if (s[cur] == A[cur]) // 自己ループはダメ
                    return false;
                s[s[cur]] = A[cur]; // group を埋める
                cur = s[cur];
            } while (cur != start);

            // ループがずれていることもあるので再度チェック
            cur = start;
            do {
                used[cur] = true; // 使用数字を更新
                if (s[s[cur]] != A[cur]) // ダメだった
                {   // もどす
                    s    = save_s;
                    used = save_u;
                    return false;
                }
                cur = s[cur];
            } while (cur != start);
            return true;
    }
    void solve(void) {
            int N;
            cin>>N;
            vector<int> A(N);
            REP(i,N)
            {
                cin>>A[i];
                --A[i];
            }

            // 1,...,N の置換 s のうち
            // s^2 = A なるものを見つける
            //
            // 置換は部分置換の直積として表現できる。
            // s = s1*s2*...*sr
            // 部分置換の個数は最大 N なので全探索でできる。
            //
            vector<int> s(N,-1);
            vector<bool> used(N,false);
            REP(i,N)
            {   // 自己ループは先に埋める
                if (i == A[i])
                {
                    s[i] = i;
                    used[i] = true;
                }
            }

            // 部分置換ごとに独立なので各 group をうめる
            // O(N^3)
            REP(i,N) // i -> ... からはじまる group
            {
                if (s[i] >= 0)  // すでに確定済み
                    continue;
                REP(j,N)
                {
                    if (i==j) // 自己ループになりうるものはすでに処理済みなので飛ばす
                        continue;
                    if (used[j])
                        continue;
                    // i->j から始まるとして group を作ってみる
                    s[i] = j;
                    if (make_group(s,i,used,A))
                        break; // 部分置換毎に独立なので i から始まるグループは確定
                    s[i] = -1;
                }
                if (s[i] < 0) // i から始まるグループで条件を満たすものはなかった
                {
                    cout<<"No"<<endl;
                    return;
                }
            }
            cout<<"Yes"<<endl;

    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new SeriesAmidakuji();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0