結果

問題 No.100 直列あみだくじ
ユーザー codershifth
提出日時 2015-09-01 23:24:28
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,861 bytes
コンパイル時間 1,575 ms
コンパイル使用メモリ 165,508 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-18 17:32:05
合計ジャッジ時間 3,045 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41 WA * 4
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘bool SeriesAmidakuji::dfs(std::vector<int>&, const std::vector<bool>&, const std::vector<int>&)’:
main.cpp:53:26: warning: ‘beg’ may be used uninitialized [-Wmaybe-uninitialized]
   53 |                     s[cur]  = i;
      |                          ^

ソースコード

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(vector<int> &s, const vector<bool> &used, const vector<int> &A) {
            int N = s.size();
            int n = count_if(RANGE(s), [&](int v){return (v>=0);});
            if (n==N)
            {
                REP(i,N) // 整合性チェック
                    if (A[i] != s[s[i]])
                        return false;
                return true;
            }
            int beg;
            REP(i,N)
            {
                if (s[i] < 0)
                {
                    beg = i;
                    break;
                }
            }
            // O(N^2)
            REP(i,N)
            {
                if (used[i])
                    continue;
                vector<bool> w(used);
                bool ok = true;

                // ii -> i に決め打ちしてためしてみる
                if (beg == i) // s[beg] = beg のとき
                {
                    s[beg] = i;
                    if (s[s[beg]] != A[beg])
                        continue;
                    w[i] = true;
                }
                else
                {
                    int cur = beg;
                    s[cur]  = i;
                    w[i] = true;
                    do {
                        if (s[cur] == A[cur])
                        {
                            ok = false;
                            break;
                        }
                        s[s[cur]] = A[cur];
                        w[A[cur]] = true;
                        cur = s[cur];
                    } while (cur != beg);
                }
                if (ok && dfs(s, w, 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);
            vector<bool> used(N,false);
            if (dfs(s, used, A))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<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