Submission #828156

#	Time	Username	Problem	Language	Result	Execution time	Memory
828156		tranxuanbach	Ancient Books (IOI17_books)	C++17	50 / 100	110 ms	31492 KiB

books

#include "books.h"

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)a.size())

using ll = long long;

const int N = 1e6 + 5;

int n, s;
int a[N];

bool vis[N];
int cnt_edge[N];
ll pref_cnt_edge[N];

ll ans;

ll minimum_walk(vector <int> _a, int _s){
	n = isz(_a);
	s = _s;
	For(i, 0, n){
		a[i] = _a[i];
	}

	For(i, 0, n){
		if (vis[i]){
			continue;
		}
		ll tans = 0;
		int l = i, r = i;
		{
			int u = i;
			do{
				vis[u] = true;
				l = min(l, u);
				r = max(r, u);
				int v = a[u];
				tans += abs(u - v);
				u = v;
			} while (u != i);
		}
		ans += tans;
		cnt_edge[l]++;
		cnt_edge[r]--;
	}
	For(i, 1, n){
		cnt_edge[i] += cnt_edge[i - 1];
	}
	For(i, 0, n){
		pref_cnt_edge[i] = (i != 0 ? pref_cnt_edge[i - 1] : 0ll) + cnt_edge[i];
	}
	For(i, 0, n - 1){
		if (cnt_edge[i] == 0 and pref_cnt_edge[n - 1] - (i != 0 ? pref_cnt_edge[i - 1] : 0ll) != 0){
			ans += 2;
		}
	}
	return ans;
}

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