Submission #917855

#	Time	Username	Problem	Language	Result	Execution time	Memory
917855		nightfal	Ancient Books (IOI17_books)	C++14	50 / 100	103 ms	42580 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;}

long long subtask3(vector<int> p, int s = 0, int e = -1 , int dir = 1) {
    int n = p.size(), last = s;
    if (e==-1) e = n-1;
    long long total = 0;

    for(int i=s; dir==1 && i<=e || 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 cal(vector<int> p, int l, int r, int lmost, int rmost, vector<vector<long long>>& dp) {
    if (dp[l][r]!=LLONG_MAX) return dp[l][r];
    int n = p.size(); 
    long long temp1=LLONG_MAX, temp2=LLONG_MAX;
    if (l>0) {
        temp1 = abs(p[l-1]-(l-1)); if(l-1 < lmost) temp1 += 2;
        int lmostN = min(lmost,min(l-1,p[l-1])), rmostN = max(rmost,p[l-1]);
        temp1 += cal(p,l-1,r,lmostN,rmostN,dp); 
    }
    if (r<n-1) {
        temp2 = abs(p[r+1]-(r+1)); if(r+1 > rmost) temp2 += 2;
        int lmostN = min(lmost,p[r+1]), rmostN = max(rmost,max(r+1,p[r+1]));
        temp2 += cal(p,l,r+1,lmostN,rmostN,dp); 
    }
    dp[l][r] = min(temp1,temp2);
    return dp[l][r];
}

long long subtask4(vector<int> p, int s) {
    int n = p.size();
    // long long move = 0;
    
    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;
    for(int i = 0; i <= end-start; i++) p[i] = p[i+start]-start;
    s -= start; n = end-start+1; p.resize(n); 
    vector<vector<long long>> dp(n,vector<long long>(n,LLONG_MAX));
    dp[0][n-1]=0;

    int l=s, r=s, lmost = min(s,p[s]), rmost = max(s,p[s]);
    return cal(p,l,r,lmost,rmost,dp)+abs(p[s]-s);
}

tuple<int,int,long long> extend(vector<int> p, int l, int r, int lmost, int rmost, int move) {
    int n = p.size();
    while(l> lmost || r < rmost) {
        int idx;
        if (l > max(lmost,0)) idx == --l;
        else if (r < min(rmost,n-1)) idx == ++r;
        move += abs(p[idx]-idx);
        lmost = min(lmost,p[idx]); 
        rmost = max(rmost,p[idx]);
    }
    return make_tuple(l,r,move);
} 

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;
    for(int i = 0; i <= end-start; i++) p[i] = p[i+start]-start;
    s -= start; n = end-start+1; p.resize(n); 
    // printf("s=%d, n=%d\n",s,n);

    int l=s, lStart=s, r=s, rStart=s;
    long long total=abs(p[s]-s), moveL=0, moveR=0, totalMove=0;

    vector<long long> sumL(n), sumR(n);
    for(int i=s-1; i>=0; i--) sumL[i] = sumL[i+1] + abs(p[i]-i);
    for(int i=s+1; i<n ; i++) sumR[i] = sumR[i-1] + abs(p[i]-i);

    vector<int> lmost(n), rmost(n); 
    lmost[s] = min(s,p[s]), rmost[s] = max(s,p[s]);
    for(int i=s-1; i>=0; i--) {lmost[i] = min(lmost[i+1],p[i]); rmost[i] = max(rmost[i+1],p[i]);}
    for(int i=s+1; i<n ; i++) {lmost[i] = min(lmost[i-1],p[i]); rmost[i] = max(rmost[i-1],p[i]);}

    while(0<l || r<n-1) {
        // printf("total=%d, moveL=%d, moveR=%d\n",total,moveL,moveR);
        // printf("l=%d, r=%d, lStart=%d, rStart=%d, lmost[%d]=%d, rmost[%d]=%d\n",l,r,lStart,rStart,l,lmost[l],r,rmost[r]);

        if(r < n-1 && (l <= 0 || moveR < moveL || moveR == moveL && r < rmost[r])) {
            if(rmost[r] <= r) moveR++;
            r++;
            // printf("r=%d, moveR=%d, lStart=%d, lmost[%d]=%d\n",r,moveR,lStart,r,lmost[r]);
            if (lmost[r] < lStart) {
                total+=sumR[r]-sumR[rStart]+sumL[lmost[r]]-sumL[lStart]+moveR*2; 
                totalMove += 2*moveR;
                // printf("total=%d, sumR[%d]=%d, sumL[lmost[%d]]=%d, sumL[lStart]=%d\n",total, r, sumR[r], r, sumL[lmost[r]], sumL[lStart]);
                moveR=0; moveL=0; 
                rStart=r; l=lStart=lmost[r];
                // printf("l=%d, r=%d, lStart=%d, rStart=%d\n",l,r,lStart,rStart);
            }
        } 
        else if(0 < l && (r >= n-1 || moveR > moveL || moveR == moveL && r >= rmost[r])) {
            if (l <= lmost[l]) moveL++;
            l--;
            // printf("l=%d, moveL=%d, rStart=%d, rmost[%d]=%d\n",l,moveL,rStart,l,rmost[l]);
            if (rStart < rmost[l]) {
                total+=sumL[l]-sumL[lStart]+sumR[rmost[l]]-sumR[rStart]+moveL*2; 
                totalMove += 2*moveL;
                // printf("total=%d, sumL[%d]=%d, sumR[rmost[%d]]=%d, sumR[rStart]=%d\n",total, l, sumL[l], l, sumR[rmost[l]], sumR[rStart]);
                moveR=0; moveL=0; 
                lStart=l, r=rStart=rmost[l];
                // printf("l=%d, r=%d, lStart=%d, rStart=%d\n",l,r,lStart,rStart);
            }            
        }
        // printf("\n");
    }
    // printf("total=%d, moveL=%d, moveR=%d\n",total,moveL,moveR);
    // printf("l=%d, r=%d, lmost[%d]=%d, rmost[%d]=%d\n",l,r,l,lmost[l],r,rmost[r]);
 
    // total += sumL + moveL*2; 
    // total += sumR + moveR*2;
    totalMove += 2*(moveL+moveR);
    // printf("totalMove=%d, sumL[0]=%d, sumR[%d]=%d \n",totalMove,sumL[0],n-1,sumR[n-1]);
    return totalMove+sumL[0]+sumR[n-1]+abs(p[s]-s);
}

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);
}

Compilation message (stderr)

books.cpp: In function 'long long int subtask3(std::vector<int>, int, int, int)':
books.cpp:18:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   18 |     for(int i=s; dir==1 && i<=e || dir==-1 && i>=e; i += dir) {
      |                  ~~~~~~~^~~~~~~
books.cpp: In function 'std::tuple<int, int, long long int> extend(std::vector<int>, int, int, int, int, int)':
books.cpp:64:35: warning: value computed is not used [-Wunused-value]
   64 |         if (l > max(lmost,0)) idx == --l;
      |                               ~~~~^~~~~~
books.cpp:65:42: warning: value computed is not used [-Wunused-value]
   65 |         else if (r < min(rmost,n-1)) idx == ++r;
      |                                      ~~~~^~~~~~
books.cpp: In function 'long long int fulltask(std::vector<int>, int)':
books.cpp:99:66: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   99 |         if(r < n-1 && (l <= 0 || moveR < moveL || moveR == moveL && r < rmost[r])) {
books.cpp:112:71: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  112 |         else if(0 < l && (r >= n-1 || moveR > moveL || moveR == moveL && r >= rmost[r])) {
books.cpp: In function 'std::tuple<int, int, long long int> extend(std::vector<int>, int, int, int, int, int)':
books.cpp:66:26: warning: 'idx' is used uninitialized in this function [-Wuninitialized]
   66 |         move += abs(p[idx]-idx);
      |                          ^

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