結果
問題 |
No.1306 Exactly 2 Digits
|
ユーザー |
![]() |
提出日時 | 2020-12-03 02:06:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 169 ms / 2,000 ms |
コード長 | 2,311 bytes |
コンパイル時間 | 3,765 ms |
コンパイル使用メモリ | 211,212 KB |
最終ジャッジ日時 | 2025-01-16 14:06:20 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 123 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; int m = n * (n - 1); vector<int> dx(m), dy(m); for (int i = 1; i < m; i++) { cout << "? " << i + 1 << " " << 1 << endl; cin >> dx.at(i) >> dy.at(i); } int dxmax = *max_element(dx.begin(), dx.end()), dymax = *max_element(dy.begin(), dy.end()), dxmin = *min_element(dx.begin(), dx.end()), dymin = *min_element(dy.begin(), dy.end()); if (dxmax - dxmin < n - 1) { swap(dxmax, dymax); swap(dxmin, dymin); for (int i = 0; i < m; i++) { swap(dx.at(i), dy.at(i)); } } assert(dxmax - dxmin == n - 1); assert(dymax - dymin == n - 2); map<pair<int, int>, bool> twoway; vector index(n, vector(n - 1, -1)); for (int i = 0; i < m; i++) { if (index.at(dx.at(i) - dxmin).at(dy.at(i) - dymin) != -1) { twoway[{dx.at(i), dy.at(i)}] = true; swap(dx.at(i), dy.at(i)); twoway[{dx.at(i), dy.at(i)}] = true; } index.at(dx.at(i) - dxmin).at(dy.at(i) - dymin) = i; } int base = -1; for (int i = 0; i < m; i++) { if (dxmin != dymin and dx.at(i) == dxmin and dy.at(i) == dymin) { base = i; break; } if (dxmin == dymin and dx.at(i) == dxmax and dy.at(i) == dymax) { base = i; break; } } vector<bool> visited(m); for (int i = 0; i < m; i++) { if (visited.at(i)) continue; if (not twoway[{dx.at(i), dy.at(i)}]) continue; int co_i = index.at(dy.at(i) - dxmin).at(dx.at(i) - dymin); cout << "? " << i + 1 << " " << base + 1 << endl; int dxbase, dybase; cin >> dxbase >> dybase; if (dx.at(i) != dxbase + dx.at(base)) { swap(dx.at(i), dy.at(i)); } if (dx.at(i) != dxbase + dx.at(base)) { swap(dxbase, dybase); } if (dx.at(i) != dxbase + dx.at(base)) { swap(dx.at(i), dy.at(i)); } dx.at(co_i) = dy.at(i); dy.at(co_i) = dx.at(i); visited.at(co_i) = true; } cout << "!"; for (int i = 0; i < m; i++) { cout << " " << n * (dy.at(i) - dymin) + (dx.at(i) - dxmin) + n; } cout << endl; }