oj.uz

Submission #33535

# Submission time Handle Problem Language Result Execution time Memory
33535 2017-10-29T15:51:14 Z top34051 Ancient Books (IOI17_books) C++14
0 / 100
 0 ms 17652 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 = 1000005;
const int inf = 1000005;

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

bool cmp(pii x,pii y) {
    if(x.Y==y.Y) return x.X>y.X;
    return x.Y>y.Y;
}

bool cmp2(long long x,long long y) {
    return x>y;
}

void get(int i) {
    sort(p[i].begin(),p[i].end(),cmp);
    for(auto t : p[i]) {
        auto it = a[i].lower_bound(t.Y);
        if(it==a[i].end()) val[i][sz[i]++] = t.Y;
        else a[i].erase(it);
        a[i].insert(t.X);
    }
    sort(&val[i][0],&val[i][sz[i]],cmp2);
}

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

    assert(s==0);

    n = pos.size();
    for(i=0;i<n;i++) {
        if(i<pos[i]) p[0].push_back({i,pos[i]});
        if(i>pos[i]) p[1].push_back({pos[i],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 17648 KB Output is correct
2 Correct 0 ms 17648 KB Output is correct
3 Incorrect 0 ms 17648 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 17648 KB Output is correct
2 Correct 0 ms 17648 KB Output is correct
3 Incorrect 0 ms 17648 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 17648 KB Output is correct
2 Correct 0 ms 17648 KB Output is correct
3 Incorrect 0 ms 17648 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 17652 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 17648 KB Output is correct
2 Correct 0 ms 17648 KB Output is correct
3 Incorrect 0 ms 17648 KB 3rd lines differ - on the 1st token, expected: '8', found: '10'
4 Halted 0 ms 0 KB -