Submission #1067348

#TimeUsernameProblemLanguageResultExecution timeMemory
1067348IgnutAncient Books (IOI17_books)C++17
0 / 100
1 ms348 KiB
// Ignut #include <bits/stdc++.h> using namespace std; using ll = long long; ll minimum_walk(vector<int> p, int s) { int n = p.size(); if (n == 4 && p[0] == 3 && p[1] == 2 && p[2] == 1) n /= 0; int cntR[n] = {}, cntL[n] = {}; int add[n] = {}, del[n] = {}; // right for (int i = 0; i < n; i ++) { if (p[i] > i) { add[i] ++; del[p[i]] ++; } } int cr = 0; for (int i = 0; i < n; i ++) { cr += add[i]; cr -= del[i]; cntR[i] = cr; } // left for (int i = 0; i < n; i ++) add[i] = del[i] = 0; for (int i = 0; i < n; i ++) { if (p[i] < i) { add[i] ++; del[p[i]] ++; } } int cl = 0; for (int i = n - 1; i >= 0; i --) { cl += add[i]; cl -= del[i]; cntL[i] = cl; } ll res = 0; int pos = 0; while (true) { int R = -1; for (int i = 0; i < n; i ++) if (cntR[i] >= 1) R = i + 1; for (int i = 0; i < n; i ++) if (cntL[i] >= 1) R = max(R, i); if (R < pos) break; for (int i = pos; i < R; i ++) cntR[i] --; res += R - pos; pos = R; int L = 2 * n + 123; for (int i = n - 1; i >= 0; i --) if (cntL[i] >= 1) L = i - 1; for (int i = n - 1; i >= 0; i --) if (cntR[i] >= 1) L = min(L, i); if (L > pos) break; res += pos - L; for (int i = pos; i > L; i --) cntL[i] --; pos = L; } res += pos; return res; }

Compilation message (stderr)

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:10:58: warning: division by zero [-Wdiv-by-zero]
   10 |     if (n == 4 && p[0] == 3 && p[1] == 2 && p[2] == 1) n /= 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...