Submission #949593

#	Time	Username	Problem	Language	Result	Execution time	Memory
949593		qin	Ancient Books (IOI17_books)	C++17	50 / 100	96 ms	20964 KiB

books

#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define vv vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
ll minimum_walk(vv<int> p, int s){
		int n = ssize(p);
		vv<int> vis(n, 0);
		int l = 0;
		ll result = 0;
		vv<pii> st;
		for(int i = 0; i < n; ++i) if(!vis[i]){
				//~ printf("%d\n", i);
				int mx = i; vis[i] = ++l; result += abs(i-p[i]);
				for(int u = p[i]; u != i; u = p[u]) vis[u] = l, mx = max(mx, u), result += abs(u-p[u]);
				if(st.empty()) {if(mx != i) st.emplace_back(i, mx);}
				else{
						if(i < st.back().se) st.back().se = max(st.back().se, mx);
						else if(mx != i) st.emplace_back(i, mx);
				}
				//~ printf("%d %lld\n", i, result);
		}
		//~ printf("a\n");
		for(int i = 1; i < ssize(st); ++i) result += 2*(st[i].fi-st[i-1].se);
		if(ssize(st) && st[0].fi != 0) result += 2*st[0].fi;
		return result;
}
#ifdef LOCAL
int main(){
		int T = 1;
		for(++T; --T; ){
				int n, s; scanf("%d%d", &n, &s);
				vv<int> p(n);
				for(int i = 0; i < n; ++i) scanf("%d", &p[i]);
				ll result = minimum_walk(p, s);
				printf("%lld\n", result);
		}
		return 0;
}
#endif

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