結果
問題 | No.282 おもりと天秤(2) |
ユーザー | minami |
提出日時 | 2019-03-30 11:35:12 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,992 ms / 5,000 ms |
コード長 | 2,706 bytes |
コンパイル時間 | 2,164 ms |
コンパイル使用メモリ | 183,524 KB |
実行使用メモリ | 24,312 KB |
平均クエリ数 | 267.12 |
最終ジャッジ日時 | 2023-09-24 02:09:36 |
合計ジャッジ時間 | 22,355 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 28 ms
23,604 KB |
testcase_01 | AC | 30 ms
24,024 KB |
testcase_02 | AC | 26 ms
23,520 KB |
testcase_03 | AC | 25 ms
23,520 KB |
testcase_04 | AC | 25 ms
23,520 KB |
testcase_05 | AC | 29 ms
23,388 KB |
testcase_06 | AC | 31 ms
23,676 KB |
testcase_07 | AC | 26 ms
24,252 KB |
testcase_08 | AC | 32 ms
23,532 KB |
testcase_09 | AC | 24 ms
23,796 KB |
testcase_10 | AC | 474 ms
24,300 KB |
testcase_11 | AC | 1,843 ms
23,388 KB |
testcase_12 | AC | 930 ms
24,000 KB |
testcase_13 | AC | 1,144 ms
23,376 KB |
testcase_14 | AC | 1,619 ms
24,132 KB |
testcase_15 | AC | 1,818 ms
23,424 KB |
testcase_16 | AC | 115 ms
24,240 KB |
testcase_17 | AC | 1,114 ms
24,252 KB |
testcase_18 | AC | 1,523 ms
23,388 KB |
testcase_19 | AC | 1,522 ms
23,388 KB |
testcase_20 | AC | 1,947 ms
23,424 KB |
testcase_21 | AC | 1,849 ms
23,640 KB |
testcase_22 | AC | 1,992 ms
24,264 KB |
testcase_23 | AC | 25 ms
24,312 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; #ifdef _DEBUG #include "dump.hpp" #else #define dump(...) #endif //#define int long long #define rep(i,a,b) for(int i=(a);i<(b);i++) #define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--) #define all(c) begin(c),end(c) const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f; const int MOD = 1'000'000'007; template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; } template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; } using Weight = int; struct Edge { int s, d; Weight w; Edge() {}; Edge(int s, int d, Weight w) : s(s), d(d), w(w) {}; }; bool operator<(const Edge &e1, const Edge &e2) { return e1.w < e2.w; } bool operator>(const Edge &e1, const Edge &e2) { return e2 < e1; } inline ostream &operator<<(ostream &os, const Edge &e) { return (os << '(' << e.s << ", " << e.d << ", " << e.w << ')'); } using Edges = vector<Edge>; using Graph = vector<Edges>; using Array = vector<Weight>; using Matrix = vector<Array>; void addArc(Graph &g, int s, int d, Weight w = 1) { g[s].emplace_back(s, d, w); } void addEdge(Graph &g, int a, int b, Weight w = 1) { addArc(g, a, b, w); addArc(g, b, a, w); } vector<int> topologicalSort(const Graph &g) { int n = g.size(), k = 0; vector<int> ord(n), indeg(n); for (auto &es : g) for (auto &e : es) indeg[e.d]++; queue<int> q; for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i); while (q.size()) { int v = q.front(); q.pop(); ord[k++] = v; for (auto &e : g[v]) if (--indeg[e.d] == 0) q.push(e.d); } return *max_element(indeg.begin(), indeg.end()) == 0 ? ord : vector<int>(); } signed main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; Graph g(N); vector<vector<bool>> d(N, vector<bool>(N)); rep(t, 0, 2000) { vector<bool> used(N); vector<int> query; rep(i, 0, N) { rep(j, i + 1, N) { if (d[i][j] || used[i] || used[j])continue; used[i] = true; used[j] = true; query.emplace_back(i + 1); query.emplace_back(j + 1); d[i][j] = true; } } if (query.size() == 0) break; rep(i, query.size(), 2 * N) query.emplace_back(0); cout << "? "; cout << query[0]; rep(i, 1, query.size()) { cout << " " << query[i]; } cout << endl; vector<char> r(N); rep(i, 0, N) { cin >> r[i]; } rep(i, 0, N) { int u = query[2 * i] - 1, v = query[2 * i + 1] - 1; if (r[i] == '>') { addArc(g, v, u); } else if (r[i] == '<') { addArc(g, u, v); } } } auto res = topologicalSort(g); cout << "! "; cout << res[0] + 1; rep(i, 1, res.size()) { cout << " " << res[i] + 1; } cout << endl; return 0; }