oj.uz

Submission #921051

# Submission time Handle Problem Language Result Execution time Memory
921051 2024-02-03T09:12:44 Z simuyu Ancient Books (IOI17_books) C++14
0 / 100
 0 ms 348 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

long long minimum_walk(std::vector<int> p, int s) {
    if (s != 0) return 0; // save time

    // get each cycle length and min.
    int n = p.size();
    bool settled[n];
    for (int i=0; i<n; i++) settled[i] = false;

    ll allmax = 0;
    ll currmin;
    ll cyclesum = 0;
    for (ll ii=0; ii<n; ii++) {
        if (settled[ii]) continue;
        // now, find this cycle.
        ll i = p[ii];
        //ll prev = ii;
        currmin = i;

        settled[i] = true;
        cyclesum += abs(ii-i);
        currmin = min(ii, i);

        while (i != ii) {
            //cout << i << ' ' << p[i] << " -> ";
            // do stuff within cycle
            settled[i] = true;
            cyclesum += abs(i-p[i]);
            i = p[i];
            currmin = min(currmin, i);
            //cout << i << ' ' << p[i] << ": " << cyclesum << endl;
        }
        //cout << i << ' ' << ii << endl;
        settled[ii] = true;
        cyclesum += abs(ii-i);
        currmin = min(currmin, ii);

        allmax = max(currmin, allmax);
    }

    //cout << "CYCLESUM: " << cyclesum << ", ALLMAX: " << allmax << endl;

	return cyclesum + 2*allmax;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

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