Submission #123060

#	Time	Username	Problem	Language	Result	Execution time	Memory
123060		SirCeness	Ancient Books (IOI17_books)	C++14	0 / 100	2 ms	376 KiB

books

#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#define inside sl<=l&&r<=sr
#define outside r<sl||sr<l
using namespace std;
typedef long long ll;

int n;
ll ans = 0;
int elde = -1;
vector<int> arr;

void iter(int a, int b){
	//cout << "iter(" << a << ", " << b << ")" << endl;
	ans += abs(b-a);
	if (a < b){
		for (int cur = a; cur <= b; cur++){
			if (elde == -1){
				if (arr[cur] > cur){
					swap(arr[cur], elde);
				}
			} else {
				if (elde == cur){
					swap(arr[cur], elde);
				} else if (elde < arr[cur]){
					swap(arr[cur], elde);
				}
			}
			//for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << "elde: " << elde << " cur: " << cur << endl;
		}
	} else if (b < a){
		for (int cur = a; cur >= b; cur--){
			if (elde == -1){
				if (arr[cur] < cur){
					swap(arr[cur], elde);
				}
			} else {
				if (elde == cur){
					swap(arr[cur], elde);
				} else if (arr[cur] != -1 && arr[cur] < elde){
					swap(arr[cur], elde);
				}
			}
			//for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << "elde: " << elde << " cur: " << cur << endl;
		}
	}
}

ll solvesol(vector<int> p, int s){
	arr = p;
	n = p.size();
	int l = 0;
	while (p[l] == l && l < n) l++;
	if (l == n) return 0;
	int r = n-1;
	while (p[r] == r) r--;
	
	int last = s;
	
	iter(s, r);
	last = r;
	while (arr[l] == l && l < n) l++;
	if (l == n) return ans + abs(s-last);
	while (arr[r] == r && r >= 0) r--;
	if (r == -1) return ans + abs(s-last);
	iter(last, r);
	last = r;
	
	while (1){
		
		iter(r, l);
		last = l;
		while (arr[l] == l && l < n) l++;
		if (l == n) return ans + abs(s-last);
		while (arr[r] == r && r >= 0) r--;
		if (r == -1) return ans + abs(s-last);
		iter(last, l);
		last = l;
		
		iter(l, r);
		last = r;
		while (arr[l] == l && l < n) l++;
		if (l == n) return ans + abs(s-last);
		while (arr[r] == r && r >= 0) r--;
		if (r == -1) return ans + abs(s-last);
		iter(last, r);
		last = r;
		
	}
	assert(0);
	return -1;
}

ll solvesag(vector<int> p, int s){
	arr = p;
	n = p.size();
	int l = 0;
	while (p[l] == l && l < n) l++;
	if (l == n) return 0;
	int r = n-1;
	while (p[r] == r) r--;
	
	int last = s;
	
	iter(s, l);
	last = l;
	while (arr[l] == l && l < n) l++;
	if (l == n) return ans + abs(s-last);
	while (arr[r] == r && r >= 0) r--;
	if (r == -1) return ans + abs(s-last);
	iter(last, l);
	last = l;
	
	while (1){
		iter(l, r);
		last = r;
		while (arr[l] == l && l < n) l++;
		if (l == n) return ans + abs(s-last);
		while (arr[r] == r && r >= 0) r--;
		if (r == -1) return ans + abs(s-last);
		iter(last, r);
		last = r;
		
		iter(r, l);
		last = l;
		while (arr[l] == l && l < n) l++;
		if (l == n) return ans + abs(s-last);
		while (arr[r] == r && r >= 0) r--;
		if (r == -1) return ans + abs(s-last);
		iter(last, l);
		last = l;
	}
	assert(0);
	return -1;
}

ll minimum_walk(vector<int> p, int s){
	return min(solvesol(p, s), solvesag(p, s));
}

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