Submission #790691

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
790691	2023-07-23T06:14:36 Z	ymm	Ancient Books (IOI17_books)	C++17	42 / 100	102 ms	24000 KB

books

#include "books.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 1e6+10;
bool vis[N];
int mn[N], mx[N];
int n;

void Do(const vector<int> &p, int i) {
	int x = i, y = i;
	vector<int> vec;
	while (!vis[i]) {
		vec.push_back(i);
		vis[i] = 1;
		x = min(x, i);
		y = max(y, i);
		i = p[i];
	}
	for (int j : vec) {
		mn[j] = x;
		mx[j] = y+1;
	}
}

int l, r, pl, pr;

void go() {
	while (l < pl || pr < r) {
		while (l < pl) {
			--pl;
			l = min(l, mn[pl]);
			r = max(r, mx[pl]);
		}
		while (pr < r) {
			l = min(l, mn[pr]);
			r = max(r, mx[pr]);
			++pr;
		}
	}
}
pii try_left() {
	int cl = l;
	int ans = 0;
	LoopR (i,0,l) {
		while (i < cl) {
			++ans;
			--cl;
		}
		if (mx[i] > r)
			return {ans, i};
		cl = min(cl, mn[i]);
	}
	return {INT_MAX, -1};
}
pii try_right() {
	int cr = r;
	int ans = 0;
	Loop (i,r,n) {
		while (cr <= i) {
			++ans;
			++cr;
		}
		if (mn[i] < l)
			return {ans, i};
		cr = max(cr, mx[i]);
	}
	return {INT_MAX, n};
}

void trim(vector<int> &p, int &s) {
	int p0 = 0, p1 = p.size()-1;
	while (p0 < s && p[p0] == p0)
		++p0;
	while (s < p1 && p[p1] == p1)
		--p1;
	vector<int> ans(p1-p0+1);
	Loop (i,p0,p1+1)
		ans[i-p0] = p[i]-p0;
	p = ans;
	s = s-p0;
}


long long minimum_walk(std::vector<int> p, int s) {
	trim(p, s);
	n = p.size();
	Loop (i,0,n) {
		if (!vis[i])
			Do(p, i);
	}
	int ans = 0;
	l = s;
	r = s+1;
	pl = s;
	pr = s;
	go();
	for (;;) {
		auto [x, xi] = try_left();
		auto [y, yi] = try_right();
		//cerr << x << ' ' << y << '\n';
		if (x == INT_MAX && y == INT_MAX)
			break;
		if (x < y) {
			ans += x;
			l = xi;
		} else {
			ans += y;
			r = yi+1;
		}
		go();
	}
	while (0 < l) {
		--l;
		++ans;
		go();
	}
	while (r < n) {
		++r;
		++ans;
		go();
	}
	ans *= 2;
	Loop (i,0,n)
		ans += abs(i - p[i]);
	return ans;
}

Subtask #1
12.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct
6	Correct	212 KB	Output is correct
7	Correct	212 KB	Output is correct
8	Correct	212 KB	Output is correct
9	Correct	212 KB	Output is correct
10	Correct	212 KB	Output is correct
11	Correct	212 KB	Output is correct
12	Correct	212 KB	Output is correct
13	Correct	212 KB	Output is correct
14	Correct	224 KB	Output is correct
15	Correct	212 KB	Output is correct
16	Correct	212 KB	Output is correct
17	Correct	212 KB	Output is correct
18	Correct	212 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	224 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	2 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	0 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	1 ms	288 KB	Output is correct

Subtask #3
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	224 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	2 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	0 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	1 ms	288 KB	Output is correct
30	Incorrect	102 ms	24000 KB	3rd lines differ - on the 1st token, expected: '333035179244', found: '-1972269844'
31	Halted	0 ms	0 KB	-

Subtask #4
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct

Subtask #5
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	224 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	2 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	0 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	1 ms	288 KB	Output is correct
30	Incorrect	102 ms	24000 KB	3rd lines differ - on the 1st token, expected: '333035179244', found: '-1972269844'
31	Halted	0 ms	0 KB	-

Submission #790691

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 20.0 / 20.0

Subtask #5 0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
20.0 / 20.0

Subtask #5
0 / 30.0