Submission #921051

#	Time	Username	Problem	Language	Result	Execution time	Memory
921051		simuyu	Ancient Books (IOI17_books)	C++14	0 / 100	0 ms	348 KiB

books

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30