| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 915164 | nightfal | Ancient Books (IOI17_books) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstdlib>
using namespace std;
bool isSubtask3(int s) {return s==0;}
long long subtask3(vector<int> p, int s = 0, int e = n, int dir = 1) {
int n = p.size(), last = s;
long long total = 0;
for(int i=s; dir==1 && e<i || dir==-1 && i<e; i += dir) {
if (i==p[i]) continue;
if (dir*(i-last) > 0) total += abs(i-last)*2;
total += abs(p[i]-i);
last = dir==1? max(last,p[i]):min(last,p[i]);
}
return total;
}
long long fulltask(vector<int> p, int s) {
int n = p.size(), left = s-1, right = s, leftmost = s-1, rightmost = s;
long long total=0, sumL=0, sumR=0, moveL=1, moveR=0;
while(0<=left || right<=n-1) {
printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
printf("left=%d, right=%d, leftmost=%d, rightmost=%d\n\n",left,right,leftmost,rightmost);
if(right <= n-1 && (moveR < moveL || moveR == moveL && right <= rightmost)) {
if(rightmost < right) moveR++;
sumR += abs(p[right]-right);
rightmost = max(rightmost,right);
rightmost = max(rightmost,p[right]);
leftmost = min(leftmost, p[right]);
if (leftmost <= left) {moveL = 0; total+=sumR+moveR; moveR=0; sumR=0;}
right++;
}
else if(0 <= left && (moveR >= moveL || moveR == moveL && right > rightmost)) {
if (left < leftmost) moveL++;
sumL += abs(p[left]-left);
leftmost = min(leftmost,left);
leftmost = min(leftmost, p[left]);
rightmost = min(rightmost,p[left]);
if (right <= rightmost) {moveR = 0; total+=sumL+moveL; moveL=0; sumL=0;}
left--;
}
}
printf("total=%d, sumL=%d, sumR=%d, moveL=%d, moveR=%d\n",total,sumL,sumR,moveL,moveR);
printf("left=%d, right%d, leftmost=%d, rightmost=%d\n",left,right,leftmost,rightmost);
if(sumL) total += sumL + moveL; // ??
if(sumR) total += sumR + moveR; // ??
return total;
}
long long minimum_walk(std::vector<int> p, int s) {
// if (isSubtask3(s))
return subtask3(p);
// return fulltask(p,s);
}