Submission #307233

#TimeUsernameProblemLanguageResultExecution timeMemory
307233VEGAnnComparing Plants (IOI20_plants)C++14
0 / 100
4064 ms384 KiB
#include "plants.h" #include <bits/stdc++.h> #define PB push_back #define sz(x) ((int)x.size()) using namespace std; const int N = 5010; const int oo = 2e9; queue<int> q; vector<int> vc; int per[N], mrk[N], tt = 0; bool sml[N][N], g[N][N]; void init(int k, vector<int> r) { int n = sz(r); for (int it = n - 1; it >= 0; it--){ vc.clear(); for (int i = 0; i < n; i++) if (r[i] == 0) vc.PB(i); if (sz(vc) == 0){ while (1) {} } int cand = -1, mx = -1; for (int it = 0; it < sz(vc); it++){ int cur = vc[it]; int pre = vc[(it + sz(vc) - 1) % sz(vc)]; if (pre < cur){ if (cur - pre > mx){ mx = cur - pre; cand = cur; break; } } else { if (cur - pre + n > mx){ mx = cur - pre + n; cand = cur; break; } } } per[cand] = it; r[cand] = oo; for (int i = 1, loc = cand; i < k; i++){ loc = (loc + n - 1) % n; r[loc]--; if (r[loc] < oo / 2) g[cand][loc] = 1; } for (int i = 1, loc = cand; i < k; i++){ loc = (loc + 1) % n; if (r[loc] < oo / 2) g[cand][loc] = 1; } } for (int i = 0; i < n; i++){ tt++; q.push(i); mrk[i] = tt; while (sz(q)){ int v = q.front(); q.pop(); sml[i][v] = 1; for (int u = 0; u < n; u++) if (g[v][u] && mrk[u] < tt){ mrk[u] = tt; q.push(u); } } } return; } int compare_plants(int x, int y) { if (sml[x][y]) return 1; if (sml[y][x]) return -1; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...