Submission #1241752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241752		SpyrosAliv	Ancient Books (IOI17_books)	C++20	0 / 100	0 ms	324 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n;

long long minimum_walk(vector<int> p, int s) {
	ll ans = 0;
	n = p.size();
	// s = 0
	int lst = -1;
	vector<int> idx(n, 0);
	for (int i = 0; i < n; i++) idx[p[i]] = i;
	int currPos = 0;
	bool toL = true;
	int carry = p[0];
	idx[carry] = -1;
	for (int i = 0; i < n; i++) {
		if (toL) {
			int goal = -1;
			for (int i = n-1; i >= 0; i--) {
				if (idx[i] != i) {
					goal = i;
					break;
				}
			}
			if (goal == -1) return ans + currPos;
			for (int i = currPos+1; i <= goal; i++) {
				ans++;
				if (p[i] > carry || i == carry) {
					idx[carry] = i;
					idx[p[i]] = -1;
					swap(p[i], carry);
				}
			}
			currPos = goal;
			toL = false;
		}
		else {
			int goal = -1;
			for (int i = 0; i < n; i++) {
				if (idx[i] != i) {
					goal = i;
					break;
				}
			}
			if (goal == -1) return ans + currPos;
			for (int i = currPos - 1; i >= goal; i--) {
				ans++;
				if (p[i] < carry) {
					idx[carry] = i;
					idx[p[i]] = -1;
					swap(p[i], carry);
				}
			}
			currPos = goal;
			toL = true;
		}
	}
	return ans + currPos;
}

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