結果
問題 |
No.3256 Permutation Equation
|
ユーザー |
![]() |
提出日時 | 2025-09-06 16:45:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,875 bytes |
コンパイル時間 | 839 ms |
コンパイル使用メモリ | 66,672 KB |
実行使用メモリ | 7,828 KB |
最終ジャッジ日時 | 2025-09-06 16:45:48 |
合計ジャッジ時間 | 11,014 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 WA * 25 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:44:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 44 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:45:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 45 | for (int i = 0; i < n; i++) scanf("%d", ps + i), ps[i]--; | ~~~~~^~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*- * * 3256.cc: No.3256 Permutation Equation - yukicoder */ #include<cstdio> #include<vector> #include<algorithm> using namespace std; /* constant */ const int MAX_N = 200000; /* typedef */ using vi = vector<int>; using vvi = vector<vi>; /* global variables */ int ps[MAX_N], ss[MAX_N]; bool used[MAX_N]; int rs[MAX_N], qs[MAX_N]; /* subroutines */ bool cmpv(const vi &a, const vi &b) { return a.size() < b.size(); } bool check(int n) { for (int i = 0; i < n; i++) if (ps[i] != qs[(qs[i] + 1) % n]) { puts("NG"); return false; } puts("GOOD"); return true; } /* main */ int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", ps + i), ps[i]--; for (int i = 0; i < n; i++) ss[i] = (ps[i] + 1) % n; vvi cvs; for (int st = 0; st < n; st++) if (! used[st]) { vi v; for (int u = st; ! used[u]; u = ss[u]) used[u] = true, v.push_back(u); cvs.push_back(v); } sort(cvs.begin(), cvs.end(), cmpv); int m = cvs.size(); for (int i = 0; i < m;) { int j = i, lj = cvs[j].size(); while (i < m && lj == cvs[i].size()) i++; if (lj & 1) { for (; j < i; j++) { auto &cv = cvs[j]; for (int k = 0, u = 0; k < lj; k++) { int v = (u + 2) % lj; rs[cv[u]] = cv[v]; u = v; } } } else { if ((i - j) & 1) { puts("No"); return 0; } for (; j < i; j += 2) { auto &cv0 = cvs[j], &cv1 = cvs[j + 1]; for (int k = 0, u0 = 0, u1 = 0; k < lj * 2; k++) { if (! (k & 1)) { // u0->u1 rs[cv0[u0]] = cv1[u1]; u0 = (u0 + 1) % lj; } else { // u1->u0 rs[cv1[u1]] = cv0[u0]; u1 = (u1 + 1) % lj; } } } } } for (int i = 0; i < n; i++) qs[i] = (rs[i] + n - 1) % n; puts("Yes"); for (int i = 0; i < n; i++) printf("%d%c", qs[i] + 1, (i + 1 < n) ? ' ' : '\n'); //check(n); return 0; }