Submission #643572

#TimeUsernameProblemLanguageResultExecution timeMemory
643572gun_ganZagonetka (COI18_zagonetka)C++17
9 / 100
108 ms464 KiB
#include <bits/stdc++.h> using namespace std; const int N = 105; int n, a[N], m, deg[N], mn[N], mx[N], Deg[N], order[N]; vector<int> g[N]; vector<int> toposort() { vector<int> d(n + 1); for(int i = 1; i <= n; i++) { for(auto u : g[i]) { // cout << i << " -> " << u << endl; d[u]++; } } queue<int> q; for(int i = 1; i <= n; i++) { if(!d[i]) q.push(i); // cout << d[i] << " "; } // cout << endl; vector<int> ret(n + 1); int cnt = 0; while(!q.empty()) { int v = q.front(); q.pop(); ret[v] = ++cnt; for(auto u : g[v]) { d[u]--; if(d[u] == 0) { q.push(u); } } } assert(cnt == n); return ret; } bool ask(int l, int r) { // swap(a[order[l]], a[order[r]]); // for(int i = 1; i <= n; i++) cout << a[i] << " "; // swap(a[order[l]], a[order[r]]); auto v = toposort(); cout << "query "; for(int i = 1; i <= n; i++) cout << v[i] << " "; cout << endl; int x; cin >> x; return x; } int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; if(n <= 6) { vector<int> p, mx, mn; for(int i = 1; i <= n; i++) p.push_back(i); do { cout << "query "; for(int i = 0; i < n; i++) { cout << p[i] << " "; } cout << endl; int x; cin >> x; if(x) { if(mx.empty()) { mx = p; } else { if(p > mx) mx = p; } if(mn.empty()) mn = p; else if(p < mn) mn = p; } } while(next_permutation(p.begin(), p.end())); cout << "end\n"; for(auto i : mn) cout << i << " "; cout << '\n'; for(auto i : mx) cout << i << " "; cout << endl; return 0; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(a[j] > a[order[i - 1]] && (a[order[i]] == 0 || a[order[i]] > a[j])) { order[i] = j; } } } for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { g[order[i]].push_back(order[j]); } } // for(int i = 1; i <= n; i++) cerr << order[i] << " "; cout << '\n'; vector<pair<int,int>> edge; for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { // cout << i << " " << j << endl; // cout << order[i] << " " << order[j] << endl; auto it = find(g[order[i]].begin(), g[order[i]].end(), order[j]); g[order[i]].erase(it); g[order[j]].push_back(order[i]); if(!ask(i, j)) { auto it = find(g[order[j]].begin(), g[order[j]].end(), order[i]); g[order[j]].erase(it); g[order[i]].push_back(order[j]); edge.push_back({order[i], order[j]}); break; } else { auto it = find(g[order[j]].begin(), g[order[j]].end(), order[i]); g[order[j]].erase(it); } } } assert(edge.size() == 1); // for(int i = 1; i <= n; i++) { // for(auto v : g[i]) { // cout << i << " -> " << v << '\n'; // } // } // cout << edge[0].first << " " << edge[0].second << '\n'; for(int i = 1; i <= n; i++) g[i].clear(); g[edge[0].first].push_back(edge[0].second); deg[edge[0].second]++; Deg[edge[0].second]++; priority_queue<int> q; for(int i = 1; i <= n; i++) if(!deg[i]) q.push(i); int cnt = 0; while(!q.empty()) { int v = q.top(); q.pop(); mx[v] = ++cnt; for(auto u : g[v]) { deg[u]--; if(deg[u] == 0) { q.push(u); } } } for(int i = 1; i <= n; i++) if(!Deg[i]) q.push(-i); cnt = 0; while(!q.empty()) { int v = q.top(); q.pop(); v = -v; mn[v] = ++cnt; for(auto u : g[v]) { Deg[u]--; if(Deg[u] == 0) { q.push(-u); } } } cout << "end\n"; for(int i = 1; i <= n; i++) cout << mn[i] << " "; cout << '\n'; for(int i = 1; i <= n; i++) cout << mx[i] << " "; cout << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...