Submission #33533

#	Time	Username	Problem	Language	Result	Execution time	Memory
33533		top34051	Ancient Books (IOI17_books)	C++14	0 / 100	0 ms	2044 KiB

books

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

#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1005;
const int inf = 1000005;

int n;
long long val[2][maxn], sz[2];
vector<pii> itv[2];
set<pii> a[2];

void kill(int i) {
    int mx = -1;
    sort(itv[i].begin(),itv[i].end());
    for(auto t : itv[i]) {
        if(t.Y<=mx) continue;
        mx = t.Y;
        a[i].insert({t.Y,t.X}); //t.Y >= t.X
//        printf("%d : {%d, %d}\n",i,t.X,t.Y);
    }
}

pii nxt(int i,int val) {
    auto it = a[i].lower_bound({val,inf});
    if(it==a[i].begin()) return {-1,-1};
    return *(--it);
}

void get(int i) {
    while(!a[i].empty()) {
//        printf("%d: turn %d\n",i,sz[i]);
        auto temp = nxt(i,inf);
        val[i][sz[i]++] = temp.X;
        while(temp.X!=-1) {
//            printf("\terase {%d, %d}\n",temp.Y,temp.X);
            a[i].erase(temp);
            temp = nxt(i,temp.Y);
        }
    }
}

long long minimum_walk(vector<int> p, int s) {
    int i;

    assert(s==0);

    n = p.size();
    for(i=0;i<n;i++) {
        if(i<p[i]) itv[0].push_back({i,p[i]});
        if(i>p[i]) itv[1].push_back({p[i],i});
    }

    for(i=0;i<2;i++) kill(i);
    for(i=0;i<2;i++) get(i);

    long long ans = 0;
    for(i=0;i<max(sz[0],sz[1]);i++) ans += max(val[0][i],val[1][i]);
    return ans*2;
}

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