Submission #1043675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043675		Alihan_8	Ancient Books (IOI17_books)	C++17	50 / 100	167 ms	25020 KiB

books

#include "books.h"

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

long long minimum_walk(std::vector<int> p, int s) {
	int n = p.size();
	
	if ( is_sorted(all(p)) ){
		return 0;
	}
	
	i64 ans = 0;
	
	for ( int i = 0; i < n; i++ ){
		ans += abs(i - p[i]);
	}
	
	vector <ar<int,2>> rng;
	
	for ( int i = 0; i < n; i++ ){
		if ( i == p[i] ) continue;
		
		if ( i < p[i] ){
			rng.pb({i, p[i]});
		} else rng.pb({p[i], i});
	}
	
	sort(all(rng));
	
	int mx = 0;
	
	for ( auto &[l, r]: rng ){
		if ( mx < l ){ // new component
			ans += (l - mx) * 2;
		} chmax(mx, r);
	}
	
	return ans;
}

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