Submission #276944

#TimeUsernameProblemLanguageResultExecution timeMemory
276944PlurmZagonetka (COI18_zagonetka)C++11
0 / 100
3058 ms256 KiB
#include <bits/stdc++.h> using namespace std; int n; int query(vector<int> v){ cout << "query"; for (int i = 0; i < n; i++) cout << " " << v[i]; cout << endl; int result; cin >> result; return result; } void answer(vector<int> lo, vector<int> hi){ cout << "end" << endl; for(int i = 0; i < n; i++) cout << lo[i] << " "; cout << endl; for(int i = 0; i < n; i++) cout << hi[i] << " "; cout << endl; } int revmap[128]; // u <-- v iff u < v req. vector<int> g[128]; // No SCC (guaranteed) vector<int> rg[128]; // Reversed void dfstopo(int u, int lim, vector<int>& ord, vector<bool>& found){ if(found[u]) return; found[u] = true; for(int v : g[u]){ if(v < lim) continue; dfstopo(v, lim, ord, found); } ord.push_back(u); } void dfshigher(int u, vector<bool>& found){ if(found[u]) return; found[u] = true; for(int v : rg[u]){ dfshigher(v, found); } } void dfsless(int u, int lim, vector<bool>& found){ if(found[u]) return; found[u] = true; for(int v : g[u]){ if(v < lim) continue; dfsless(v, lim, found); } } /** * Determines whether x < y is a required order or not? */ bool customLess(int x, int y){ vector<bool> found; found.reserve(n+1); for(int i = 0; i <= n; i++) found.push_back(false); dfsless(y, x, found); return found[x]; } /** * Get topological ordering (any) with start as source, going down until vertex value less than lim. */ vector<int> getTopo(int start, int lim){ vector<int> ord; vector<bool> found; found.reserve(n+1); for(int i = 0; i <= n; i++) found.push_back(false); dfstopo(start, lim, ord, found); return ord; } vector<int> getLower(int start){ vector<int> ord; vector<bool> found; found.reserve(n+1); for(int i = 0; i <= n; i++) found.push_back(false); dfsless(start, 0, found); for(int i = 0; i <= n; i++) if(found[i]) ord.push_back(i); return ord; } vector<int> getHigher(int start){ vector<int> ord; vector<bool> found; found.reserve(n+1); for(int i = 0; i <= n; i++) found.push_back(false); dfshigher(start, found); for(int i = n; i >= 0; i--) if(found[i]) ord.push_back(i); return ord; } vector<int> p; vector<int> minSolve(){ vector<int> pluggedval; for(int i = 0; i < n; i++) pluggedval.push_back(-1); for(int i = 1; i <= n;){ // Plugging i into p[i-1] if(pluggedval[i-1] != -1) continue; int rnk = p[i-1]; vector<int> concern = getLower(rnk); for(int u : concern){ if(pluggedval[revmap[u]] == -1){ pluggedval[revmap[u]] = i++; } } } return pluggedval; } vector<int> maxSolve(){ vector<int> pluggedval; for(int i = 0; i < n; i++) pluggedval.push_back(-1); for(int i = n; i > 0;){ // Plugging i into p[n-i] if(pluggedval[n-i] != -1) continue; int rnk = p[n-i]; vector<int> concern = getHigher(rnk); for(int u : concern){ if(pluggedval[revmap[u]] == -1){ pluggedval[revmap[u]] = i--; } } } return pluggedval; } int main() { cin >> n; for(int i = 0; i < n; i++){ int x; cin >> x; p.push_back(x); revmap[x] = i; } for(int itv = 1; itv <= n; itv++){ for(int i = 1; i+itv <= n; i++){ int j = i+itv; if(customLess(i, j)){ ;// do nothing because i < j already }else{ vector<int> topo = getTopo(j, i); int cnt = i; for(int u : topo){ p[revmap[u]] = cnt++; } sort(topo.begin(), topo.end()); for(int k = i; k <= j; k++){ if(!binary_search(topo.begin(), topo.end(), k)){ p[revmap[k]] = cnt++; } } int req = query(p) == 0; for(int k = i; k <= j; k++){ p[revmap[k]] = k; } if(req) g[j].push_back(i); } } } for(int i = 1; i <= n; i++){ for(int j : g[i]) rg[j].push_back(i); } vector<int> lo = minSolve(); vector<int> hi = maxSolve(); answer(lo, hi); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...