結果
問題 |
No.1306 Exactly 2 Digits
|
ユーザー |
![]() |
提出日時 | 2020-12-03 01:00:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 517 ms / 2,000 ms |
コード長 | 4,953 bytes |
コンパイル時間 | 2,499 ms |
コンパイル使用メモリ | 224,284 KB |
最終ジャッジ日時 | 2025-01-16 13:44:53 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 123 |
ソースコード
#include <bits/stdc++.h> struct random : std::mt19937 { using std::mt19937::mt19937; using std::mt19937::operator(); static int64_t gen_seed() { return std::chrono::steady_clock::now().time_since_epoch().count(); } random() : std::mt19937(gen_seed()) {} template <class Int> auto operator()(Int a, Int b) -> std::enable_if_t<std::is_integral_v<Int>, Int> { return std::uniform_int_distribution<Int>(a, b)(*this); } template <class Real> auto operator()(Real a, Real b) -> std::enable_if_t<std::is_floating_point_v<Real>, Real> { return std::uniform_real_distribution<Real>(a, b)(*this); } } rng; #pragma region my_template struct Rep { struct I { int i; void operator++() { ++i; } int operator*() const { return i; } bool operator!=(I o) const { return i < *o; } }; const int l_, r_; Rep(int l, int r) : l_(l), r_(r) {} Rep(int n) : Rep(0, n) {} I begin() const { return {l_}; } I end() const { return {r_}; } }; struct Per { struct I { int i; void operator++() { --i; } int operator*() const { return i; } bool operator!=(I o) const { return i > *o; } }; const int l_, r_; Per(int l, int r) : l_(l), r_(r) {} Per(int n) : Per(0, n) {} I begin() const { return {r_ - 1}; } I end() const { return {l_ - 1}; } }; template <class F> struct Fix : private F { Fix(F f) : F(f) {} template <class... Args> decltype(auto) operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); } }; template <class T = int> T scan() { T res; std::cin >> res; return res; } template <class T, class U = T> bool chmin(T& a, U&& b) { return b < a ? a = std::forward<U>(b), true : false; } template <class T, class U = T> bool chmax(T& a, U&& b) { return a < b ? a = std::forward<U>(b), true : false; } #ifndef LOCAL #define DUMP(...) void(0) template <int OnlineJudge, int Local> constexpr int OjLocal = OnlineJudge; #endif using namespace std; #define ALL(c) begin(c), end(c) #pragma endregion int main() { cin.tie(nullptr)->sync_with_stdio(false); cout << fixed << setprecision(20); int n = scan(); int num_queries = 0; auto query = [&](int i, int j) -> array<int, 2> { assert(0 <= i), assert(i < n * (n - 1)); assert(0 <= j), assert(j < n * (n - 1)); ++num_queries; assert(num_queries <= n * (n - 1) / 2 * 3); cout << "? " << i + 1 << ' ' << j + 1 << endl; array<int, 2> res; if (OjLocal<0, 1>) { static vector<int> ans; if (empty(ans)) { ans.resize(n * (n - 1)); iota(ALL(ans), n); shuffle(ALL(ans), rng); DUMP(ans); } res[0] = ans[i] / n - ans[j] / n; res[1] = ans[i] % n - ans[j] % n; sort(ALL(res)); } else { res = {scan(), scan()}; } assert(is_sorted(ALL(res))); return res; }; map<map<int, int>, int> mp; for (int j : Rep(n, n * n)) { map<int, int> cnt; for (int i : Rep(n, n * n)) if (i != j) { ++cnt[i / n - j / n]; ++cnt[i % n - j % n]; } mp[cnt] = j; } assert(int(size(mp)) == n * (n - 1)); vector<array<int, 2>> res(n * (n - 1)); map<int, int> cnt; for (int i : Rep(1, n * (n - 1))) { res[i] = query(i, 0); for (int z : Rep(2)) ++cnt[res[i][z]]; } assert(mp.count(cnt)); vector<int> ans(n * (n - 1)); ans[0] = mp[cnt]; vector<array<int, 2>> pre(n * n); for (int x : Rep(n, n * n)) { pre[x][0] = x / n - ans[0] / n; pre[x][1] = x % n - ans[0] % n; sort(ALL(pre[x])); } vector<vector<int>> pos(n * n); pos[ans[0]] = {0}; for (int i : Rep(1, n * (n - 1))) { for (int x : Rep(n, n * n)) if (x != ans[0] and res[i] == pre[x]) { pos[x].push_back(i); } } DUMP(pos); int off = -1; for (int x : Rep(n, n * n)) if (size(pos[x]) == 1) { ans[pos[x][0]] = x; if (x != ans[0] and x / n - ans[0] / n != x % n - ans[0] % n) off = x; } DUMP(off); int pos_off = find(ALL(ans), off) - begin(ans); assert(pos_off < n * (n - 1)); for (int x : Rep(n, n * n)) if (size(pos[x]) == 2) { bool first = true; for (int i : pos[x]) { array<int, 2> expected; expected[0] = x / n - off / n; expected[1] = x % n - off % n; sort(ALL(expected)); if (not exchange(first, false) or query(i, pos_off) == expected) { ans[i] = x; for (int y : Rep(x + 1, n * n)) if (pos[y] == pos[x]) { int other = pos[x][0] ^ pos[x][1] ^ i; ans[other] = y; pos[y].clear(); break; } break; } } } cout << '!'; for (auto&& e : ans) cout << ' ' << e; cout << endl; }