Submission #1212502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212502		ProtonDecay314	Ancient Books (IOI17_books)	C++20	0 / 100	0 ms	328 KiB

books

#include<bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back

ll minimum_walk(vi p, int s) {
    int n = p.size();

    /*
    prune the rightmost fixed points
    */
    int rm = n - 1;

    while(rm == p[rm]) {
        rm--;
    }

    n = rm + 1; // performing the pruning

    // computing "connection cost"
    // the cost to move between components

    int connection_cost = 0;

    vpi es;
    
    for(int i = 0; i < n; i++) {
        int v1 = i, v2 = p[i];

        if(v1 > v2) swap(v1, v2);

        es.pb({v1, 1});
        es.pb({v2, -1});
        // cerr << v1 << " " << v2 << endl;
    }

    // cerr << "EDGE END" << endl;
    
    sort(es.begin(), es.end());

    // for(int i = 0; i < (n << 1); i++) {
    //     cerr << es[i].first << " " << es[i].second << endl; 
    // }

    // cerr << "ES END" << endl;

    int cur_sum = 0;
    
    for(int i = 0; i < n - 1; i++) {
        cur_sum += es[(i << 1)].second;
        cur_sum += es[(i << 1) | 1].second;
        if(cur_sum == 0) connection_cost++;
    }

    // computing the base sum: the total cost to correct each component
    ll base_sum = 0ll;

    vb vis(n, false);

    for(int i = 0; i < n; i++) {
        if(vis[i]) continue;

        int ci = i;
        vis[ci] = true;
        int mn = ci, mx = ci;

        while(p[ci] != i) {
            ci = p[ci];
            vis[ci] = true;

            mn = min(mn, ci);
            mx = max(mx, ci);
        }

        base_sum += ((ll)mx - (ll)mn) << 1ll;
    }

    cerr << base_sum << " " << (((ll)connection_cost) << 1ll) << endl;

	return base_sum + (((ll)connection_cost) << 1ll);
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30