Submission #239093

#	Time	Username	Problem	Language	Result	Execution time	Memory
239093		lyc	Ancient Books (IOI17_books)	C++14	50 / 100	218 ms	17656 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cout << #x << " :: " << x << endl;
#define _ << " " <<
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

const int mxN = 1e6+5;
int N, L, R;
int go[mxN][2];

void ext(int& l, int& r) {
    int x = l, y = r;
    do {
        FOR(j,0,1){
            if (l >= x && go[l][j] != -1) x = min(x,go[l][j]), y = max(y,go[l][j]);
            if (r <= y && go[r][j] != -1) x = min(x,go[r][j]), y = max(y,go[r][j]);
        }
        --l, ++r;
    } while (x <= l || r <= y);
    l = x, r = y;
}

long long minimum_walk(std::vector<int> p, int s) {
    N = SZ(p);
    long long lb = 0;
    L = N-1, R = 0;
    memset(go,-1,sizeof go);
    FOR(i,0,N-1){
        if (i != p[i]) {
            lb += abs(p[i]-i);
            L = min({L,i,p[i]}), R = max({R,i,p[i]});
            FOR(j,0,1) if (go[i][j] == -1) { go[i][j] = p[i]; break; }
            FOR(j,0,1) if (go[p[i]][j] == -1) { go[p[i]][j] = i; break; }
        }
    }
    long long add = 0;
    int l = s, r = s;
    for (;;) {
        ext(l,r);
        if (l <= L && r >= R) break;
        add += 2;
        if (l > 0) --l;
        if (r < N-1) ++r;
    }
    //TRACE(lb _ add);
	return lb + add;
}

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