結果
問題 | No.261 ぐるぐるぐるぐる!あみだくじ! |
ユーザー | kroton |
提出日時 | 2015-07-31 23:13:32 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 2,384 bytes |
コンパイル時間 | 583 ms |
コンパイル使用メモリ | 67,368 KB |
実行使用メモリ | 4,384 KB |
最終ジャッジ日時 | 2023-09-24 23:01:38 |
合計ジャッジ時間 | 2,598 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 2 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | AC | 2 ms
4,376 KB |
testcase_14 | AC | 2 ms
4,380 KB |
testcase_15 | AC | 2 ms
4,384 KB |
testcase_16 | AC | 2 ms
4,380 KB |
testcase_17 | AC | 2 ms
4,376 KB |
testcase_18 | AC | 2 ms
4,380 KB |
testcase_19 | AC | 2 ms
4,376 KB |
testcase_20 | AC | 2 ms
4,376 KB |
testcase_21 | AC | 2 ms
4,380 KB |
testcase_22 | AC | 3 ms
4,376 KB |
testcase_23 | AC | 2 ms
4,380 KB |
testcase_24 | AC | 2 ms
4,376 KB |
testcase_25 | AC | 2 ms
4,376 KB |
testcase_26 | AC | 2 ms
4,380 KB |
testcase_27 | AC | 2 ms
4,380 KB |
testcase_28 | AC | 2 ms
4,380 KB |
testcase_29 | AC | 2 ms
4,376 KB |
testcase_30 | AC | 2 ms
4,376 KB |
testcase_31 | AC | 2 ms
4,380 KB |
testcase_32 | AC | 2 ms
4,380 KB |
testcase_33 | AC | 2 ms
4,376 KB |
testcase_34 | AC | 2 ms
4,376 KB |
testcase_35 | AC | 2 ms
4,376 KB |
testcase_36 | AC | 2 ms
4,376 KB |
testcase_37 | AC | 2 ms
4,380 KB |
testcase_38 | AC | 2 ms
4,380 KB |
testcase_39 | AC | 2 ms
4,376 KB |
ソースコード
// O(Q * N * log hoge)くらい? #include <iostream> #include <vector> #include <cstring> using namespace std; typedef long long ll; inline ll mod_inverse(ll a, ll m){ ll b = m, u = 1, v = 0; while (b) { ll t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return (u % m + m) % m; } inline ll gcd(ll a, ll b){ if(b == 0){ return a; } return gcd(b, a % b); } pair<ll, ll> linear_congruence(const vector<ll>& A, const vector<ll>& B, const vector<ll>& M){ ll x = 0, m = 1; for(int i=0;i<(int)A.size();i++){ ll a = A[i] * m, b = B[i] - A[i] * x, d = gcd(M[i], a); if(b % d != 0){ return make_pair(0, -1); } ll t = b / d * mod_inverse(a / d, M[i] / d) % (M[i] / d); x = x + m * t; m *= M[i] / d; } return make_pair((x % m + m) % m, m); } int nxt[100]; int group_id[100], id[100]; int size[100]; void dfs(int now, int gid, int sz){ if(group_id[now] == gid){ size[gid] = sz; return; } group_id[now] = gid; id[now] = sz; dfs(nxt[now], gid, sz + 1); } int main(){ memset(group_id, -1, sizeof(group_id)); int N, K; cin >> N >> K; for(int i=0;i<N;i++)nxt[i] = i; for(int i=0;i<K;i++){ int X, Y; cin >> X >> Y; swap(nxt[X-1], nxt[Y-1]); } int gid = 0; for(int i=0;i<N;i++){ if(group_id[i] == -1){ dfs(i, gid, 0); ++gid; } } int Q; cin >> Q; while(Q--){ vector<int> A(N); for(int i=0;i<N;i++){ cin >> A[i]; --A[i]; } bool valid = true; vector<ll> B(N), M(N); for(int i=0;i<N;i++){ if(group_id[i] != group_id[A[i]]){ valid = false; break; } int sz = size[group_id[i]]; B[i] = (id[A[i]] - id[i] + sz) % sz; M[i] = sz; } if(!valid){ cout << -1 << endl; continue; } auto res = linear_congruence(vector<ll>(N, 1), B, M); if(res.second == -1){ cout << -1 << endl; } else { if(res.first == 0){ cout << res.second << endl; } else { cout << res.first << endl; } } } return 0; }