oj.uz

Submission #69618

# Submission time Handle Problem Language Result Execution time Memory
69618 2018-08-21T10:07:00 Z aquablitz11 Ancient Books (IOI17_books) C++14
0 / 100
 3 ms 496 KB 
#include <bits/stdc++.h>
#include "books.h"
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 1e9;

ll minimum_walk(vector<int> p, int s)
{
    int n = p.size();
    vector<pll> li;
    ll dist = 0;
    for (int i = 0; i < n; ++i) {
        if (p[i] == -1) continue;
        int u = i, cnt = 0;
        ll l = -INF, r = INF;
        do {
            ++cnt;
            if (u <= s) l = max(l, (ll)u);
            if (u >= s) r = min(r, (ll)u);
            int v = p[u];
            dist += abs(u-v);
            p[u] = -1;
            u = v;
        } while (u != i);
        if (cnt > 1)
            li.emplace_back(s-l, r-s);
    }
    sort(li.begin(), li.end());
    ll mx = 0, ans = INF*INF;
    for (int i = li.size()-1; i >= 0; --i) {
        ans = min(ans, li[i].first + mx);
        mx = max(mx, li[i].second);
    }
    ans = min(ans, mx);

	return dist+2*ans;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 496 KB 3rd lines differ - on the 1st token, expected: '3304', found: '4724'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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