結果

問題 No.100 直列あみだくじ
コンテスト
ユーザー codershifth
提出日時 2015-09-01 23:34:46
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,851 bytes
コンパイル時間 1,331 ms
コンパイル使用メモリ 162,952 KB
実行使用メモリ 13,696 KB
最終ジャッジ日時 2024-07-18 17:32:22
合計ジャッジ時間 13,973 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

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 dfs(const vector<int> &s, const vector<int> &A) {
            int N = s.size();
            vector<bool> used(N,false);
            int n = count_if(RANGE(s), [&](int v){return (v>=0);});
            if (n==N) // s が全部埋まった
            {
                REP(i,N) // 整合性チェック
                    if (A[i] != s[s[i]])
                        return false;
                return true;
            }
            int k = -1;
            REP(i,N)
            {
                if (k < 0 && s[i] < 0)
                    k = i;
                if (s[i] >= 0)
                    used[s[i]] = true;
            }
            // O(N^2)
            REP(i,N)
            {
                if (used[i])
                    continue;
                bool ok = true;
                vector<int> t(s); // 上書きするので別に用意

                // k -> i に決め打ちしてためしてみる
                if (k == i) // 自己ループのとき
                {
                    t[k] = i;
                    if (t[t[k]] != A[k]) // 矛盾したらダメ
                        continue;
                }
                else
                {
                    int cur = k;
                    t[cur]  = i;
                    do {
                        if (t[cur] == A[cur])
                        {// 途中で自己ループしていたらダメ
                            ok = false;
                            break;
                        }
                        t[t[cur]] = A[cur];
                        cur = t[cur];
                    } while (cur != k);
                }
                if (ok && dfs(t, A))
                    return true;
            }
            return false;
    }
    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);
            if (dfs(s, A))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
    }
};


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