답안 #811264

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
811264	2023-08-07T03:26:33 Z	LittleCube	고대 책들 (IOI17_books)	C++17	12 / 100	15 ms	23892 KB

books

#pragma GCC optimize("Ofast,unroll-loops")
#include "books.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int n, reach[1000006], g[1000006], l, r;
vector<int> out[1000006];
long long minimum_walk(vector<int> p, int s)
{
	{
		n = p.size();
		int l = 0, r = n - 1;
		while (l < s && p[l] == l)
			l++;
		while (r > s && p[r] == r)
			r--;
		p = vector<int>(p.begin() + l, p.begin() + r + 1);
		n = p.size();
		s -= l;
		for (auto &i : p)
			i -= l;
	}

	ll ans = 0;

	vector<pii> edge;
	for (int i = 0; i < n; i++)
		reach[i] = i;
	for (int i = 0; i < n; i++)
	{
		ans += abs(p[i] - i);
		int u = min(p[i], i), v = max(p[i], i);
		if (v <= s || u <= s)
			reach[u] = max(reach[u], v);
		else
			edge.emplace_back(pii(u, v));
	}
	for (int i = 1; i < n; i++)
		reach[i] = max(reach[i - 1], reach[i]);
	int last = 0, m = 0;
	for (int i = 0; i < n; i++)
	{
		if (last < i)
			++m;
		g[i] = m;
		last = max(last, reach[i]);
	}
	for (auto &[u, v] : edge)
	{
		u = g[u], v = g[v];
		out[u].emplace_back(v);
		out[v].emplace_back(u);
	}
	int l = g[s], r = g[s];
	while (0 < l || r < m)
	{
		ans += 2;
		int nl = max(0, l - 1), nr = min(m, r + 1);
		while(nl < l || r < nr)
		{
			if(nl < l)
			{
				l--;
				for (auto i : out[l])
					nl = min(i, nl), nr = max(i, nr);
			}
			else 
			{
				r++;
				for (auto i : out[r])
					nl = min(i, nl), nr = max(i, nr);
			}
		}
	}

	return ans;
}

Subtask #1

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	23892 KB	Output is correct
2	Correct	13 ms	23764 KB	Output is correct
3	Correct	13 ms	23764 KB	Output is correct
4	Correct	13 ms	23764 KB	Output is correct
5	Correct	14 ms	23764 KB	Output is correct
6	Correct	13 ms	23800 KB	Output is correct
7	Correct	14 ms	23688 KB	Output is correct
8	Correct	13 ms	23716 KB	Output is correct
9	Correct	13 ms	23796 KB	Output is correct
10	Correct	15 ms	23796 KB	Output is correct
11	Correct	13 ms	23764 KB	Output is correct
12	Correct	13 ms	23764 KB	Output is correct
13	Correct	13 ms	23740 KB	Output is correct
14	Correct	13 ms	23728 KB	Output is correct
15	Correct	13 ms	23764 KB	Output is correct
16	Correct	13 ms	23764 KB	Output is correct
17	Correct	14 ms	23788 KB	Output is correct
18	Correct	14 ms	23792 KB	Output is correct

Subtask #2

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	23892 KB	Output is correct
2	Correct	13 ms	23764 KB	Output is correct
3	Correct	13 ms	23764 KB	Output is correct
4	Correct	13 ms	23764 KB	Output is correct
5	Correct	14 ms	23764 KB	Output is correct
6	Correct	13 ms	23800 KB	Output is correct
7	Correct	14 ms	23688 KB	Output is correct
8	Correct	13 ms	23716 KB	Output is correct
9	Correct	13 ms	23796 KB	Output is correct
10	Correct	15 ms	23796 KB	Output is correct
11	Correct	13 ms	23764 KB	Output is correct
12	Correct	13 ms	23764 KB	Output is correct
13	Correct	13 ms	23740 KB	Output is correct
14	Correct	13 ms	23728 KB	Output is correct
15	Correct	13 ms	23764 KB	Output is correct
16	Correct	13 ms	23764 KB	Output is correct
17	Correct	14 ms	23788 KB	Output is correct
18	Correct	14 ms	23792 KB	Output is correct
19	Incorrect	15 ms	23764 KB	3rd lines differ - on the 1st token, expected: '338572', found: '338586'
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	23892 KB	Output is correct
2	Correct	13 ms	23764 KB	Output is correct
3	Correct	13 ms	23764 KB	Output is correct
4	Correct	13 ms	23764 KB	Output is correct
5	Correct	14 ms	23764 KB	Output is correct
6	Correct	13 ms	23800 KB	Output is correct
7	Correct	14 ms	23688 KB	Output is correct
8	Correct	13 ms	23716 KB	Output is correct
9	Correct	13 ms	23796 KB	Output is correct
10	Correct	15 ms	23796 KB	Output is correct
11	Correct	13 ms	23764 KB	Output is correct
12	Correct	13 ms	23764 KB	Output is correct
13	Correct	13 ms	23740 KB	Output is correct
14	Correct	13 ms	23728 KB	Output is correct
15	Correct	13 ms	23764 KB	Output is correct
16	Correct	13 ms	23764 KB	Output is correct
17	Correct	14 ms	23788 KB	Output is correct
18	Correct	14 ms	23792 KB	Output is correct
19	Incorrect	15 ms	23764 KB	3rd lines differ - on the 1st token, expected: '338572', found: '338586'
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	13 ms	23764 KB	3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	23892 KB	Output is correct
2	Correct	13 ms	23764 KB	Output is correct
3	Correct	13 ms	23764 KB	Output is correct
4	Correct	13 ms	23764 KB	Output is correct
5	Correct	14 ms	23764 KB	Output is correct
6	Correct	13 ms	23800 KB	Output is correct
7	Correct	14 ms	23688 KB	Output is correct
8	Correct	13 ms	23716 KB	Output is correct
9	Correct	13 ms	23796 KB	Output is correct
10	Correct	15 ms	23796 KB	Output is correct
11	Correct	13 ms	23764 KB	Output is correct
12	Correct	13 ms	23764 KB	Output is correct
13	Correct	13 ms	23740 KB	Output is correct
14	Correct	13 ms	23728 KB	Output is correct
15	Correct	13 ms	23764 KB	Output is correct
16	Correct	13 ms	23764 KB	Output is correct
17	Correct	14 ms	23788 KB	Output is correct
18	Correct	14 ms	23792 KB	Output is correct
19	Incorrect	15 ms	23764 KB	3rd lines differ - on the 1st token, expected: '338572', found: '338586'
20	Halted	0 ms	0 KB	-