Submission #917954

#	Time	Username	Problem	Language	Result	Execution time	Memory
917954		nightfal	Ancient Books (IOI17_books)	C++14	100 / 100	102 ms	20048 KiB

books

#include <cstdio>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <tuple>
#include <climits>

using namespace std;

bool isSubtask3(int s) {return s==0;}
bool isSubtask4(int n) {return n<=1000;}

pair<int,int> extend(int l, int r, vector<int>& lmost, vector<int>& rmost) {
    while(l > min(lmost[l],lmost[r]) || r < max(rmost[l],rmost[r])) {
        l=min(l,min(lmost[l],lmost[r])); 
        r=max(r,max(rmost[r],rmost[l]));
    }
    return make_pair(l,r);
} 

long long fulltask(vector<int> p, int s) {

    int n = p.size();

    int start; for(start = 0; start < s; start++) if(start!=p[start]) break;
    int end; for(end = n-1; end > s; end--) if(end!=p[end]) break;

    long long distBooks=0;
    for(int i=start; i<=end; i++) distBooks += abs(p[i]-i);

    int l = min(s,p[s]), r=max(s,p[s]); 
    vector<int> lmost(n), rmost(n); lmost[s] = min(s,p[s]); rmost[s] = max(s,p[s]);
    for(int i=s-1; i>=start; i--) {lmost[i] = min(lmost[i+1],p[i]); rmost[i] = max(rmost[i+1],p[i]);}
    for(int i=s+1; i<=end ; i++)  {lmost[i] = min(lmost[i-1],p[i]); rmost[i] = max(rmost[i-1],p[i]);}
    tie(l,r) = extend(l,r,lmost,rmost);

    long long distFree=0, rMoves=0, lMoves=0;

    while(start<l || r<end) {
        int l2, r2;
        if(r<end && (l<=start || rMoves < lMoves)) {
            r++; rMoves++;
            tie(l2,r2) = extend(l,r,lmost,rmost);
            if (l2<l) {distFree += rMoves; rMoves = lMoves = 0;}
        }
        else {
            l--; lMoves++;
            tie(l2,r2) = extend(l,r,lmost,rmost);
            if (r<r2) {distFree += lMoves; rMoves = lMoves = 0;}
        }
        l = l2; r = r2;
    }
    distFree += rMoves + lMoves;
    // printf("totalMoves=%d, jumps=%d\n",totalMoves,jumps);
    return distFree*2+distBooks;
}

long long minimum_walk(std::vector<int> p, int s) {
    // if (isSubtask3(s)) return subtask3(p);
    // if (isSubtask4(s)) return subtask4(p,s);
    return fulltask(p,s);
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30