結果
問題 | No.1306 Exactly 2 Digits |
ユーザー | t33f |
提出日時 | 2020-12-06 13:43:58 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 137 ms / 2,000 ms |
コード長 | 4,941 bytes |
コンパイル時間 | 1,487 ms |
コンパイル使用メモリ | 122,960 KB |
実行使用メモリ | 24,384 KB |
平均クエリ数 | 1236.78 |
最終ジャッジ日時 | 2023-09-24 09:17:14 |
合計ジャッジ時間 | 14,994 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 28 ms
23,376 KB |
testcase_01 | AC | 24 ms
23,388 KB |
testcase_02 | AC | 24 ms
23,748 KB |
testcase_03 | AC | 23 ms
23,532 KB |
testcase_04 | AC | 25 ms
24,252 KB |
testcase_05 | AC | 24 ms
23,796 KB |
testcase_06 | AC | 24 ms
24,120 KB |
testcase_07 | AC | 24 ms
24,240 KB |
testcase_08 | AC | 25 ms
23,292 KB |
testcase_09 | AC | 25 ms
23,520 KB |
testcase_10 | AC | 25 ms
24,276 KB |
testcase_11 | AC | 24 ms
24,216 KB |
testcase_12 | AC | 24 ms
23,256 KB |
testcase_13 | AC | 24 ms
23,544 KB |
testcase_14 | AC | 25 ms
24,276 KB |
testcase_15 | AC | 25 ms
23,508 KB |
testcase_16 | AC | 26 ms
24,228 KB |
testcase_17 | AC | 25 ms
23,664 KB |
testcase_18 | AC | 26 ms
24,204 KB |
testcase_19 | AC | 25 ms
24,252 KB |
testcase_20 | AC | 24 ms
23,292 KB |
testcase_21 | AC | 24 ms
23,388 KB |
testcase_22 | AC | 23 ms
24,228 KB |
testcase_23 | AC | 24 ms
23,352 KB |
testcase_24 | AC | 24 ms
23,892 KB |
testcase_25 | AC | 24 ms
23,652 KB |
testcase_26 | AC | 24 ms
23,292 KB |
testcase_27 | AC | 25 ms
23,112 KB |
testcase_28 | AC | 24 ms
23,652 KB |
testcase_29 | AC | 24 ms
23,604 KB |
testcase_30 | AC | 25 ms
23,904 KB |
testcase_31 | AC | 24 ms
23,412 KB |
testcase_32 | AC | 26 ms
23,508 KB |
testcase_33 | AC | 25 ms
23,292 KB |
testcase_34 | AC | 25 ms
23,532 KB |
testcase_35 | AC | 25 ms
23,640 KB |
testcase_36 | AC | 25 ms
24,240 KB |
testcase_37 | AC | 24 ms
24,012 KB |
testcase_38 | AC | 24 ms
23,520 KB |
testcase_39 | AC | 25 ms
23,508 KB |
testcase_40 | AC | 25 ms
23,244 KB |
testcase_41 | AC | 25 ms
23,532 KB |
testcase_42 | AC | 26 ms
23,388 KB |
testcase_43 | AC | 26 ms
23,916 KB |
testcase_44 | AC | 27 ms
23,424 KB |
testcase_45 | AC | 26 ms
24,228 KB |
testcase_46 | AC | 28 ms
23,244 KB |
testcase_47 | AC | 28 ms
23,256 KB |
testcase_48 | AC | 29 ms
23,292 KB |
testcase_49 | AC | 30 ms
23,628 KB |
testcase_50 | AC | 32 ms
23,796 KB |
testcase_51 | AC | 33 ms
24,240 KB |
testcase_52 | AC | 35 ms
24,216 KB |
testcase_53 | AC | 37 ms
24,240 KB |
testcase_54 | AC | 34 ms
23,784 KB |
testcase_55 | AC | 37 ms
24,228 KB |
testcase_56 | AC | 39 ms
23,532 KB |
testcase_57 | AC | 41 ms
23,892 KB |
testcase_58 | AC | 42 ms
23,652 KB |
testcase_59 | AC | 40 ms
23,496 KB |
testcase_60 | AC | 49 ms
23,832 KB |
testcase_61 | AC | 50 ms
23,628 KB |
testcase_62 | AC | 51 ms
23,904 KB |
testcase_63 | AC | 54 ms
23,400 KB |
testcase_64 | AC | 52 ms
24,024 KB |
testcase_65 | AC | 57 ms
23,712 KB |
testcase_66 | AC | 60 ms
24,360 KB |
testcase_67 | AC | 63 ms
23,808 KB |
testcase_68 | AC | 63 ms
24,228 KB |
testcase_69 | AC | 67 ms
24,240 KB |
testcase_70 | AC | 65 ms
24,000 KB |
testcase_71 | AC | 70 ms
23,724 KB |
testcase_72 | AC | 70 ms
24,036 KB |
testcase_73 | AC | 70 ms
23,700 KB |
testcase_74 | AC | 79 ms
24,288 KB |
testcase_75 | AC | 75 ms
23,256 KB |
testcase_76 | AC | 89 ms
24,240 KB |
testcase_77 | AC | 93 ms
23,640 KB |
testcase_78 | AC | 99 ms
24,264 KB |
testcase_79 | AC | 104 ms
23,412 KB |
testcase_80 | AC | 109 ms
23,652 KB |
testcase_81 | AC | 90 ms
23,280 KB |
testcase_82 | AC | 111 ms
23,412 KB |
testcase_83 | AC | 115 ms
23,904 KB |
testcase_84 | AC | 123 ms
24,000 KB |
testcase_85 | AC | 132 ms
23,508 KB |
testcase_86 | AC | 107 ms
23,532 KB |
testcase_87 | AC | 114 ms
24,336 KB |
testcase_88 | AC | 137 ms
24,384 KB |
testcase_89 | AC | 119 ms
23,796 KB |
testcase_90 | AC | 101 ms
24,228 KB |
testcase_91 | AC | 113 ms
24,204 KB |
testcase_92 | AC | 102 ms
23,784 KB |
testcase_93 | AC | 121 ms
23,916 KB |
testcase_94 | AC | 102 ms
24,228 KB |
testcase_95 | AC | 107 ms
23,712 KB |
testcase_96 | AC | 99 ms
23,304 KB |
testcase_97 | AC | 99 ms
23,532 KB |
testcase_98 | AC | 96 ms
23,364 KB |
testcase_99 | AC | 109 ms
23,292 KB |
testcase_100 | AC | 111 ms
23,904 KB |
testcase_101 | AC | 120 ms
23,916 KB |
testcase_102 | AC | 104 ms
24,216 KB |
testcase_103 | AC | 110 ms
23,892 KB |
testcase_104 | AC | 111 ms
23,508 KB |
testcase_105 | AC | 112 ms
23,496 KB |
testcase_106 | AC | 98 ms
24,228 KB |
testcase_107 | AC | 108 ms
23,364 KB |
testcase_108 | AC | 102 ms
23,796 KB |
testcase_109 | AC | 121 ms
23,532 KB |
testcase_110 | AC | 100 ms
23,412 KB |
testcase_111 | AC | 106 ms
24,000 KB |
testcase_112 | AC | 97 ms
23,268 KB |
testcase_113 | AC | 130 ms
23,496 KB |
testcase_114 | AC | 131 ms
23,640 KB |
testcase_115 | AC | 109 ms
24,372 KB |
testcase_116 | AC | 135 ms
24,276 KB |
testcase_117 | AC | 115 ms
23,292 KB |
testcase_118 | AC | 121 ms
23,652 KB |
testcase_119 | AC | 106 ms
24,024 KB |
testcase_120 | AC | 96 ms
24,024 KB |
testcase_121 | AC | 116 ms
23,700 KB |
testcase_122 | AC | 112 ms
24,204 KB |
ソースコード
#include <numeric> #include <random> #include <map> #include <algorithm> #include <cassert> #include <vector> #include <iostream> using namespace std; bool interactive = true; pair<int, int> diff(int x, int y, int n) { int p = x / n - y / n, q = x % n - y % n; if (p > q) swap(p, q); return {p, q}; } int n = -1; int qcount = 0; vector<int> ans; template<typename T> void random_shuffle(vector<T> &a) { mt19937 mt{ random_device{}() }; for (int i = a.size() - 1; i >= 1; i--) { uniform_int_distribution<int> dist(0, i); int j = dist(mt); if (i != j) swap(a[i], a[j]); } } void initialize_ans(int size) { n = size; ans.resize(n * n - n); iota(ans.begin(), ans.end(), n); random_shuffle(ans); // ans = {3, 5, 6, 8, 4, 7}; cerr << "initialize with size = " << size << endl; cerr << "ans ="; for (int x : ans) cerr << ' ' << x; cerr << endl; } int getsize() { int tmp; cin >> tmp; if (cin.eof()) { interactive = false; initialize_ans(10); return n; } return n = tmp; } pair<int, int> query(int i, int j) { if (!interactive) { ++qcount; assert(qcount <= (n * n - n) / 2 * 3); auto [p, q] = diff(ans[i], ans[j], n); cerr << "? " << i << ' ' << j << endl; cerr << p << ' ' << q << endl; return {p, q}; } else { cout << "? " << i+1 << ' ' << j+1 << endl; int x, y; cin >> x >> y; return {x, y}; } } void answer(vector<int>& r) { if (!interactive) { cerr << '!'; for (int x : r) cerr << ' ' << x; cerr << endl; assert(r.size() == n * n - n); for (int i = 0; i < r.size(); i++) { assert(r[i] == ans[i]); } } else { cout << '!'; for (int x : r) cout << ' ' << x; cout << endl; } } int main() { int n = getsize(); vector<pair<int, int> > res(n*n-n); vector<int> ans(n*n-n, 0); for (int i = 1; i < n * n - n; i++) { res[i] = query(0, i); } auto sum = [](pair<int, int> x) { return x.first + x.second; }; auto cmp = [sum](pair<int, int> x, pair<int, int> y) { return sum(x) < sum(y); }; int idx10 = max_element(res.begin(), res.end(), cmp) - res.begin(); if (sum(res[idx10]) < 0) idx10 = 0; int idxnn = min_element(res.begin(), res.end(), cmp) - res.begin(); if (sum(res[idxnn]) > 0) idxnn = 0; // cerr << idx10 << ' ' << idxnn << endl; if (idx10 == 0) ans[0] = n; else if (idxnn == 0) ans[0] = n * n - 1; else { for (int x = n; x < n * n; x++) if (diff(x, n, n) == res[idx10] && diff(x, n * n - 1, n) == res [idxnn]) { assert(ans[0] == 0); ans[0] = x; } } // cerr << "a[0] = " << ans[0] << endl; map<pair<int, int>, vector<int> > idx_of; for (int i = 1; i < n * n - n; i++) idx_of[res[i]].push_back(i); for (auto &[k, v] : idx_of) { auto [p, q] = k; // cerr << p << ' ' << q << " =>"; // for (int x : v) cerr << ' ' << x; // cerr << endl; } for (auto &[k, v] : idx_of) { auto [p, q] = k; int a0 = ans[0] / n - p, a1 = ans[0] % n - q, b0 = ans[0] / n - q, b1 = ans[0] % n - p; auto ok = [n](int x) { return 0 <= x && x < n; }; int a = ok(a0) && ok(a1) ? (ans[0] / n - p) * n + (ans[0] % n - q) : -1, b = ok(b0) && ok(b1) ? (ans[0] / n - q) * n + (ans[0] % n - p) : -1; if (v.size() == 1) { const int i = v[0]; // cerr << p << ' ' << q << ' ' << i << ' ' << a << ' ' << b << endl; if (n <= a && a < n * n) { assert(k == diff(ans[0], a, n)); ans[i] = a; } else { assert(n <= b && b < n * n); assert(k == diff(ans[0], b, n)); ans[i] = b; } assert(k == diff(ans[0], ans[i], n)); } else { assert(v.size() == 2); int i = v[0], j = v[1]; // cerr << p << ' ' << q << ' ' << i << ' ' << j << endl; assert(n <= a && a < n * n); assert(n <= b && b < n * n); assert(a != b); assert(k == diff(ans[0], a, n)); assert(k == diff(ans[0], b, n)); if (diff(a, n, n) != diff(b, n, n)) { if (query(i, idx10) == diff(a, n, n)) { ans[i] = a; ans[j] = b; } else { ans[j] = a; ans[i] = b; } } else { assert(diff(a, n * n - 1, n) != diff(b, n * n - 1, n)); if (query(i, idxnn) == diff(a, n * n - 1, n)) { ans[i] = a; ans[j] = b; } else { ans[j] = a; ans[i] = b; } } } } answer(ans); }