oj.uz

Submission #811264

# Submission time Handle Problem Language Result Execution time Memory
811264 2023-08-07T03:26:33 Z LittleCube Ancient Books (IOI17_books) C++17
12 / 100
 15 ms 23892 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -