oj.uz

Submission #33533

# Submission time Handle Problem Language Result Execution time Memory
33533 2017-10-29T15:41:22 Z top34051 Ancient Books (IOI17_books) C++14
0 / 100
 0 ms 2044 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2040 KB Output is correct
2 Correct 0 ms 2040 KB Output is correct
3 Incorrect 0 ms 2040 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2040 KB Output is correct
2 Correct 0 ms 2040 KB Output is correct
3 Incorrect 0 ms 2040 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2040 KB Output is correct
2 Correct 0 ms 2040 KB Output is correct
3 Incorrect 0 ms 2040 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 2044 KB Execution killed because of forbidden syscall gettid (186)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2040 KB Output is correct
2 Correct 0 ms 2040 KB Output is correct
3 Incorrect 0 ms 2040 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
4 Halted 0 ms 0 KB -