Submission #724931

#TimeUsernameProblemLanguageResultExecution timeMemory
724931lukadupliZagonetka (COI18_zagonetka)C++14
0 / 100
265 ms456 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 105; int n, arr[MAXN]; int maybe[MAXN][MAXN], sure[MAXN][MAXN]; int mini[MAXN], maxi[MAXN]; bool query(int* perm, int len){ cout << "query "; for(int i = 0; i < len; i++) cout << perm[i] << ' '; cout << endl; bool ans; cin >> ans; return ans; } bool bio[MAXN]; vector<int> topsort; void dfs(int node){ bio[node] = 1; for(int i = 0; i < n; i++){ if(!bio[i] && (maybe[node][i] || sure[node][i])) dfs(i); } topsort.push_back(node); } vector<pair<int, int>> edgesort; void edfs(int node){ bio[node] = 1; for(int i = 0; i < n; i++){ if(maybe[node][i] || sure[node][i]){ if(!bio[i]) edfs(i); edgesort.push_back({node, i}); } } } void gentopsort(){ memset(bio, 0, sizeof bio); topsort.clear(); for(int i = 0; i < n; i++) if(!bio[i]) dfs(i); reverse(topsort.begin(), topsort.end()); } void genedgesort(){ memset(bio, 0, sizeof bio); edgesort.clear(); for(int i = 0; i < n; i++) if(!bio[i]) edfs(i); reverse(edgesort.begin(), edgesort.end()); } int perm[MAXN]; void genperm(){ gentopsort(); for(int i = 0; i < n; i++) perm[topsort[i]] = i + 1; } void solve_edge(){ genedgesort(); int a, b; for(auto e : edgesort){ if(maybe[e.first][e.second]){ a = e.first; b = e.second; break; } } maybe[a][b] = 0; maybe[b][a] = 1; genperm(); if(!query(perm, n)){ sure[a][b] = 1; } maybe[b][a] = 0; } int last; void dfs1(int node){ for(int nxt = 0; nxt < n; nxt++){ if(sure[node][nxt] == -1 && !mini[nxt]) dfs1(nxt); } mini[node] = ++last; } void dfs2(int node){ for(int nxt = 0; nxt < n; nxt++){ if(sure[node][nxt] == 1 && !maxi[nxt]) dfs2(nxt); } maxi[node] = --last; } int main() { cin >> n; for(int i = 0; i < n; i++) cin >> arr[i]; for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ if(arr[i] < arr[j]) maybe[i][j] = 1; else maybe[j][i] = 1; } } for(int i = 0; i < n * (n - 1) / 2; i++) solve_edge(); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++) if(sure[i][j] == 1) sure[j][i] = -1; } last = 0; for(int i = 0; i < n; i++){ if(!mini[i]) dfs1(i); } last = n + 1; for(int i = 0; i < n; i++){ if(!maxi[i]) dfs2(i); } cout << "end\n"; for(int i = 0; i < n; i++) cout << mini[i] << ' '; cout << '\n'; for(int i = 0; i < n; i++) cout << maxi[i] << ' '; cout << endl; return 0; }

Compilation message (stderr)

zagonetka.cpp: In function 'void solve_edge()':
zagonetka.cpp:82:17: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |     maybe[b][a] = 0;
      |     ~~~~~~~~~~~~^~~
zagonetka.cpp:82:17: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...