oj.uz

Submission #620009

# Submission time Handle Problem Language Result Execution time Memory
620009 2022-08-02T18:43:32 Z Ozy Ancient Books (IOI17_books) C++17
0 / 100
 1 ms 340 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 1000000

lli n,ini,fin,res,last,activos,a,act;
lli vis[MAX+2];
vector<pair<lli,lli> > eventos;

long long minimum_walk(std::vector<int> p, int s) {

    n = p.size();
    res = 0;

    rep(i,0,n-1) {
        if (vis[i]) continue;
        if (p[i] == i) continue;
        vis[i] = 1;

        ini = i;
        fin = i;
        act = p[i];
        res += abs(i - act);

        while (act != i) {
            vis[act] = 1;
            ini = min(ini,act);
            fin = max(fin,act);
            res += abs(p[act] - act);
            act = p[act];
        }
        eventos.push_back({ini,0});
        eventos.push_back({fin,1});
    }
    sort(eventos.begin(), eventos.end());

    last = eventos[0].first;
    activos = 0;
    for (auto e : eventos) {

        if (activos == 0) {
            a = e.first - last;
            a *= 2;
            res += a;
        }

        last = e.first;
        if (e.second) activos--;
        else activos++;
    }

    a = eventos.size();
    if (s < eventos[0].first) {
        a = abs(eventos[0].first - s);
        a *= 2;
        res += a;
    }
    if (s > eventos[a-1].first) {
        a = abs(s - eventos[a-1].first);
        a *= 2;
        res += a;
    }

    return res;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Runtime error 1 ms 340 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Runtime error 1 ms 340 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Runtime error 1 ms 340 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Runtime error 1 ms 340 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -