結果
問題 | No.1306 Exactly 2 Digits |
ユーザー | Pachicobue |
提出日時 | 2020-12-03 20:06:27 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 134 ms / 2,000 ms |
コード長 | 2,680 bytes |
コンパイル時間 | 1,809 ms |
コンパイル使用メモリ | 175,452 KB |
実行使用メモリ | 24,372 KB |
平均クエリ数 | 1236.78 |
最終ジャッジ日時 | 2023-09-24 08:36:10 |
合計ジャッジ時間 | 16,311 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 27 ms
23,820 KB |
testcase_01 | AC | 26 ms
23,640 KB |
testcase_02 | AC | 25 ms
23,352 KB |
testcase_03 | AC | 25 ms
24,336 KB |
testcase_04 | AC | 25 ms
23,628 KB |
testcase_05 | AC | 26 ms
23,988 KB |
testcase_06 | AC | 26 ms
23,628 KB |
testcase_07 | AC | 25 ms
23,364 KB |
testcase_08 | AC | 26 ms
23,616 KB |
testcase_09 | AC | 25 ms
23,592 KB |
testcase_10 | AC | 26 ms
23,364 KB |
testcase_11 | AC | 25 ms
23,340 KB |
testcase_12 | AC | 26 ms
23,652 KB |
testcase_13 | AC | 26 ms
24,312 KB |
testcase_14 | AC | 26 ms
23,616 KB |
testcase_15 | AC | 26 ms
24,012 KB |
testcase_16 | AC | 26 ms
23,652 KB |
testcase_17 | AC | 25 ms
24,216 KB |
testcase_18 | AC | 25 ms
24,024 KB |
testcase_19 | AC | 25 ms
23,976 KB |
testcase_20 | AC | 25 ms
24,036 KB |
testcase_21 | AC | 25 ms
24,324 KB |
testcase_22 | AC | 25 ms
23,604 KB |
testcase_23 | AC | 28 ms
23,796 KB |
testcase_24 | AC | 26 ms
24,348 KB |
testcase_25 | AC | 26 ms
23,976 KB |
testcase_26 | AC | 25 ms
24,216 KB |
testcase_27 | AC | 26 ms
23,688 KB |
testcase_28 | AC | 26 ms
23,520 KB |
testcase_29 | AC | 26 ms
24,324 KB |
testcase_30 | AC | 26 ms
23,340 KB |
testcase_31 | AC | 27 ms
24,024 KB |
testcase_32 | AC | 26 ms
24,228 KB |
testcase_33 | AC | 26 ms
24,336 KB |
testcase_34 | AC | 26 ms
23,652 KB |
testcase_35 | AC | 26 ms
23,496 KB |
testcase_36 | AC | 26 ms
23,628 KB |
testcase_37 | AC | 27 ms
24,240 KB |
testcase_38 | AC | 27 ms
23,520 KB |
testcase_39 | AC | 28 ms
23,604 KB |
testcase_40 | AC | 27 ms
23,352 KB |
testcase_41 | AC | 26 ms
23,472 KB |
testcase_42 | AC | 27 ms
23,796 KB |
testcase_43 | AC | 27 ms
23,604 KB |
testcase_44 | AC | 28 ms
23,628 KB |
testcase_45 | AC | 28 ms
23,628 KB |
testcase_46 | AC | 28 ms
23,388 KB |
testcase_47 | AC | 30 ms
24,312 KB |
testcase_48 | AC | 31 ms
24,024 KB |
testcase_49 | AC | 32 ms
23,808 KB |
testcase_50 | AC | 32 ms
23,640 KB |
testcase_51 | AC | 34 ms
23,928 KB |
testcase_52 | AC | 35 ms
24,288 KB |
testcase_53 | AC | 37 ms
23,400 KB |
testcase_54 | AC | 35 ms
23,340 KB |
testcase_55 | AC | 38 ms
23,796 KB |
testcase_56 | AC | 40 ms
23,328 KB |
testcase_57 | AC | 39 ms
24,336 KB |
testcase_58 | AC | 43 ms
23,508 KB |
testcase_59 | AC | 42 ms
23,976 KB |
testcase_60 | AC | 48 ms
23,520 KB |
testcase_61 | AC | 53 ms
24,036 KB |
testcase_62 | AC | 52 ms
23,664 KB |
testcase_63 | AC | 55 ms
23,388 KB |
testcase_64 | AC | 53 ms
23,796 KB |
testcase_65 | AC | 56 ms
24,372 KB |
testcase_66 | AC | 60 ms
23,988 KB |
testcase_67 | AC | 62 ms
23,352 KB |
testcase_68 | AC | 63 ms
23,808 KB |
testcase_69 | AC | 66 ms
24,300 KB |
testcase_70 | AC | 68 ms
23,376 KB |
testcase_71 | AC | 68 ms
24,324 KB |
testcase_72 | AC | 69 ms
24,348 KB |
testcase_73 | AC | 68 ms
23,316 KB |
testcase_74 | AC | 81 ms
24,324 KB |
testcase_75 | AC | 76 ms
23,352 KB |
testcase_76 | AC | 89 ms
24,036 KB |
testcase_77 | AC | 89 ms
24,300 KB |
testcase_78 | AC | 96 ms
23,340 KB |
testcase_79 | AC | 106 ms
23,532 KB |
testcase_80 | AC | 107 ms
23,532 KB |
testcase_81 | AC | 91 ms
23,604 KB |
testcase_82 | AC | 110 ms
23,976 KB |
testcase_83 | AC | 114 ms
23,988 KB |
testcase_84 | AC | 120 ms
23,352 KB |
testcase_85 | AC | 129 ms
24,024 KB |
testcase_86 | AC | 108 ms
23,628 KB |
testcase_87 | AC | 110 ms
24,288 KB |
testcase_88 | AC | 134 ms
23,340 KB |
testcase_89 | AC | 114 ms
23,340 KB |
testcase_90 | AC | 101 ms
23,964 KB |
testcase_91 | AC | 112 ms
24,252 KB |
testcase_92 | AC | 102 ms
23,412 KB |
testcase_93 | AC | 118 ms
23,820 KB |
testcase_94 | AC | 104 ms
23,184 KB |
testcase_95 | AC | 107 ms
24,324 KB |
testcase_96 | AC | 98 ms
24,024 KB |
testcase_97 | AC | 98 ms
24,216 KB |
testcase_98 | AC | 97 ms
23,628 KB |
testcase_99 | AC | 110 ms
23,508 KB |
testcase_100 | AC | 112 ms
23,628 KB |
testcase_101 | AC | 120 ms
23,628 KB |
testcase_102 | AC | 101 ms
23,400 KB |
testcase_103 | AC | 107 ms
23,616 KB |
testcase_104 | AC | 109 ms
24,336 KB |
testcase_105 | AC | 107 ms
23,340 KB |
testcase_106 | AC | 98 ms
24,024 KB |
testcase_107 | AC | 109 ms
24,252 KB |
testcase_108 | AC | 99 ms
24,036 KB |
testcase_109 | AC | 121 ms
23,520 KB |
testcase_110 | AC | 102 ms
23,400 KB |
testcase_111 | AC | 104 ms
24,372 KB |
testcase_112 | AC | 94 ms
24,036 KB |
testcase_113 | AC | 125 ms
23,340 KB |
testcase_114 | AC | 128 ms
23,364 KB |
testcase_115 | AC | 109 ms
23,376 KB |
testcase_116 | AC | 132 ms
23,964 KB |
testcase_117 | AC | 114 ms
23,376 KB |
testcase_118 | AC | 118 ms
23,400 KB |
testcase_119 | AC | 103 ms
23,388 KB |
testcase_120 | AC | 94 ms
23,808 KB |
testcase_121 | AC | 116 ms
23,640 KB |
testcase_122 | AC | 113 ms
24,312 KB |
コンパイルメッセージ
main.cpp: ラムダ関数内: main.cpp:35:14: 警告: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 35 | auto [p, q] = d; | ^
ソースコード
#include <bits/stdc++.h> int main() { int N; std::cin >> N; const int L = N * N - N; using pii = std::pair<int, int>; auto ask = [&](const int i, const int j) { std::cout << "? " << i + 1 << " " << j + 1 << std::endl; int p, q; std::cin >> p >> q; return std::make_pair(p, q); }; auto fin = [&](const std::vector<int>& ans) { std::cout << "!"; for (const int e : ans) { std::cout << " " << e; } std::cout << std::endl; }; auto diff = [&](const int m, const int n) { // m-n int p = m / N - n / N, q = m % N - n % N; if (p > q) { std::swap(p, q); } return std::make_pair(p, q); }; std::vector<pii> ds(L, {0, 0}); // ds[i] = as[i]-as[0] for (int i = 1; i < L; i++) { ds[i] = ask(i, 0); } std::vector<int> as(L, -1); const int mi = std::min_element(ds.begin(), ds.end()) - ds.begin(); const int Mi = std::max_element(ds.begin(), ds.end()) - ds.begin(); as[mi] = N, as[Mi] = N * N - 1; auto getcand = [&](const int n, const pii d) { // n, n-c auto [p, q] = d; std::vector<int> ans; const int a = n / N, b = n % N; if (1 <= a - p and a - p < N and 0 <= b - q and b - q < N) { ans.push_back((a - p) * N + (b - q)); } if (p != q) { std::swap(p, q); if (1 <= a - p and a - p < N and 0 <= b - q and b - q < N) { ans.push_back((a - p) * N + (b - q)); } } return ans; }; auto decide = [&](const int m, const pii& md, const int n, const pii& nd) { // m,m-c,n,n-c std::vector<int> ans; const auto cs = getcand(m, md); for (const int c : cs) { if (diff(n, c) == nd) { ans.push_back(c); } } return ans[0]; }; as[0] = decide(N, ds[mi], N * N - 1, ds[Mi]); int ref = Mi; { const int p = as[0] / N, q = as[0] % N; if (p == q) { ref = mi; } } std::vector<bool> used(N * N, false); used[N] = used[as[0]] = used[N * N - 1] = true; for (int i = 1; i < L; i++) { const auto cs = getcand(as[0], pii{-ds[i].second, -ds[i].first}); if (cs.size() == 1) { as[i] = cs[0]; } else if (cs.size() == 2) { if (used[cs[0]]) { as[i] = cs[1]; } else if (used[cs[1]]) { as[i] = cs[0]; } else { const auto d = ask(ref, i); as[i] = decide(as[0], pii{-ds[i].second, -ds[i].first}, as[ref], d); } } else { while (true) {} } used[as[i]] = true; } fin(as); return 0; }