Submission #799267

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
799267	2023-07-31T11:29:06 Z	LittleCube	Ancient Books (IOI17_books)	C++17	22 / 100	2000 ms	239932 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;

vector<int> seg[4000005];
int n, rp[1000005], dn[1000005], d0[1000005], l, r;

void init()
{
	for (int i = 1; i <= 4 * n; i++)
		seg[i].clear();
}

void insert(int mL, int mR, int val, int i = 1, int L = 0, int R = n - 1)
{
	if (mL <= L && R <= mR)
		seg[i].emplace_back(val);
	else if (R < mL || mR < L)
		return;
	else
	{
		int mid = (L + R) / 2;
		insert(mL, mR, val, i << 1, L, mid);
		insert(mL, mR, val, i << 1 | 1, mid + 1, R);
	}
}

vector<int> query(int pos)
{
	vector<int> v;
	int i = 1, L = 0, R = n - 1;
	while (1)
	{
		while (!seg[i].empty())
		{
			v.emplace_back(seg[i].back());
			seg[i].pop_back();
		}
		if (L == R)
			break;
		int mid = (L + R) / 2;
		if (pos <= mid)
			R = mid, i = i << 1;
		else
			L = mid + 1, i = i << 1 | 1;
	}
	return v;
}

long long minimum_walk(std::vector<int> p, int s)
{
	n = p.size();
	l = 0, r = n - 1;
	while (l < n && p[l] == l)
		l++;
	if (l == n)
		return 0;
	while (r && p[r] == r)
		r--;

	ll ans = 0;
	if (s < l)
	{
		ans += 2 * (l - s);
		s = l;
	}
	if (r < s)
	{
		ans += 2 * (s - r);
		s = r;
	}
	for (int i = 0; i < n; i++)
		ans += abs(p[i] - i);
	for (int i = 0; i < n; i++)
		rp[p[i]] = i;

	cerr << "calc n\n";
	// calc n
	{
		for (int i = 0; i < n; i++)
			dn[i] = -1;
		for (int i = 0; i < n; i++)
		{
			int l = min({i, p[i], rp[i]}), r = max({i, p[i], rp[i]});
			insert(l, r, i);
		}
		vector<int> cur, nxt = {r};
		dn[r] = 0;
		int d = 0;
		while (!nxt.empty())
		{
			swap(nxt, cur);
			nxt.clear();
			for (int i = 0; i < cur.size(); i++)
			{
				vector<int> v = query(cur[i]);
				for (int j : v)
					if (dn[j] == -1)
						dn[j] = d, cur.emplace_back(j);
			}
			d++;
			for (int i : cur)
			{
				if (i - 1 >= 0 && dn[i - 1] == -1)
					dn[i - 1] = d, nxt.emplace_back(i - 1);
				if (i + 1 <= n && dn[i + 1] == -1)
					dn[i + 1] = d, nxt.emplace_back(i + 1);
			}
		}
	}

	// calc 0
	{
		init();
		for (int i = 0; i < n; i++)
			d0[i] = -1;
		for (int i = 0; i < n; i++)
		{
			int l = min({i, p[i], rp[i]}), r = max({i, p[i], rp[i]});
			insert(l, r, i);
		}
		vector<int> cur, nxt = {l};
		d0[l] = 0;
		int d = 0;
		while (!nxt.empty())
		{
			swap(nxt, cur);
			nxt.clear();
			for (int i = 0; i < cur.size(); i++)
			{
				vector<int> v = query(cur[i]);
				for (int j : v)
					if (d0[j] == -1)
						d0[j] = d, cur.emplace_back(j);
			}
			d++;
			for (int i : cur)
			{
				if (i - 1 >= 0 && d0[i - 1] == -1)
					d0[i - 1] = d, nxt.emplace_back(i - 1);
				if (i + 1 <= n && d0[i + 1] == -1)
					d0[i + 1] = d, nxt.emplace_back(i + 1);
			}
		}
	}

	int sec = 1e9;

	// check next nearest
	auto check = [&](int t)
	{
		int cl, cr, nl, nr, d, d0n = 1e9;
		cl = cr = nl = nr = t;
		d = abs(t - s);
		auto getin = [&](int i)
		{
			cl = min({cl, i, p[i], rp[i]}), cr = max({cr, i, p[i], rp[i]});
			d0n = min(d0n, d0[i] + dn[i]);
		};
		while (l < cl || cr < r)
		{
			while (cl <= nl || nr <= cr)
			{
				if (cl <= nl)
					getin(nl--);
				if (nr <= cr)
					getin(nr++);
			}
			sec = min(sec, d + d0n);
			d++;
			cl = max(l, cl - 1);
			cr = min(r, cr + 1);
		}
	};

	for (int i = s; i < n; i++)
		if (p[i] != i)
		{
			check(i);
			break;
		}

	for (int i = s; i >= 0; i--)
		if (p[i] != i)
		{
			check(i);
			break;
		}
	return ans + 2 * sec;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |    for (int i = 0; i < cur.size(); i++)
      |                    ~~^~~~~~~~~~~~
books.cpp:135:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |    for (int i = 0; i < cur.size(); i++)
      |                    ~~^~~~~~~~~~~~

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	94240 KB	Output is correct
2	Correct	52 ms	94160 KB	Output is correct
3	Correct	50 ms	94184 KB	Output is correct
4	Correct	63 ms	94220 KB	Output is correct
5	Correct	50 ms	94160 KB	Output is correct
6	Correct	48 ms	94216 KB	Output is correct
7	Correct	48 ms	94216 KB	Output is correct
8	Correct	52 ms	94152 KB	Output is correct
9	Correct	51 ms	94216 KB	Output is correct
10	Correct	50 ms	94156 KB	Output is correct
11	Correct	50 ms	94204 KB	Output is correct
12	Correct	51 ms	94228 KB	Output is correct
13	Correct	52 ms	94220 KB	Output is correct
14	Correct	52 ms	94220 KB	Output is correct
15	Correct	52 ms	94204 KB	Output is correct
16	Correct	51 ms	94156 KB	Output is correct
17	Correct	53 ms	94128 KB	Output is correct
18	Correct	53 ms	94240 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	94240 KB	Output is correct
2	Correct	52 ms	94160 KB	Output is correct
3	Correct	50 ms	94184 KB	Output is correct
4	Correct	63 ms	94220 KB	Output is correct
5	Correct	50 ms	94160 KB	Output is correct
6	Correct	48 ms	94216 KB	Output is correct
7	Correct	48 ms	94216 KB	Output is correct
8	Correct	52 ms	94152 KB	Output is correct
9	Correct	51 ms	94216 KB	Output is correct
10	Correct	50 ms	94156 KB	Output is correct
11	Correct	50 ms	94204 KB	Output is correct
12	Correct	51 ms	94228 KB	Output is correct
13	Correct	52 ms	94220 KB	Output is correct
14	Correct	52 ms	94220 KB	Output is correct
15	Correct	52 ms	94204 KB	Output is correct
16	Correct	51 ms	94156 KB	Output is correct
17	Correct	53 ms	94128 KB	Output is correct
18	Correct	53 ms	94240 KB	Output is correct
19	Correct	52 ms	94284 KB	Output is correct
20	Correct	63 ms	94324 KB	Output is correct
21	Correct	55 ms	94156 KB	Output is correct
22	Correct	53 ms	94292 KB	Output is correct
23	Correct	53 ms	94192 KB	Output is correct
24	Correct	52 ms	94220 KB	Output is correct
25	Correct	59 ms	94192 KB	Output is correct
26	Correct	60 ms	94188 KB	Output is correct
27	Correct	52 ms	94212 KB	Output is correct
28	Correct	58 ms	94236 KB	Output is correct
29	Correct	66 ms	94276 KB	Output is correct

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	94240 KB	Output is correct
2	Correct	52 ms	94160 KB	Output is correct
3	Correct	50 ms	94184 KB	Output is correct
4	Correct	63 ms	94220 KB	Output is correct
5	Correct	50 ms	94160 KB	Output is correct
6	Correct	48 ms	94216 KB	Output is correct
7	Correct	48 ms	94216 KB	Output is correct
8	Correct	52 ms	94152 KB	Output is correct
9	Correct	51 ms	94216 KB	Output is correct
10	Correct	50 ms	94156 KB	Output is correct
11	Correct	50 ms	94204 KB	Output is correct
12	Correct	51 ms	94228 KB	Output is correct
13	Correct	52 ms	94220 KB	Output is correct
14	Correct	52 ms	94220 KB	Output is correct
15	Correct	52 ms	94204 KB	Output is correct
16	Correct	51 ms	94156 KB	Output is correct
17	Correct	53 ms	94128 KB	Output is correct
18	Correct	53 ms	94240 KB	Output is correct
19	Correct	52 ms	94284 KB	Output is correct
20	Correct	63 ms	94324 KB	Output is correct
21	Correct	55 ms	94156 KB	Output is correct
22	Correct	53 ms	94292 KB	Output is correct
23	Correct	53 ms	94192 KB	Output is correct
24	Correct	52 ms	94220 KB	Output is correct
25	Correct	59 ms	94192 KB	Output is correct
26	Correct	60 ms	94188 KB	Output is correct
27	Correct	52 ms	94212 KB	Output is correct
28	Correct	58 ms	94236 KB	Output is correct
29	Correct	66 ms	94276 KB	Output is correct
30	Execution timed out	2094 ms	239932 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	94360 KB	Output is correct
2	Correct	52 ms	94236 KB	Output is correct
3	Correct	57 ms	94212 KB	Output is correct
4	Incorrect	50 ms	94204 KB	3rd lines differ - on the 1st token, expected: '2094', found: '2098'
5	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	94240 KB	Output is correct
2	Correct	52 ms	94160 KB	Output is correct
3	Correct	50 ms	94184 KB	Output is correct
4	Correct	63 ms	94220 KB	Output is correct
5	Correct	50 ms	94160 KB	Output is correct
6	Correct	48 ms	94216 KB	Output is correct
7	Correct	48 ms	94216 KB	Output is correct
8	Correct	52 ms	94152 KB	Output is correct
9	Correct	51 ms	94216 KB	Output is correct
10	Correct	50 ms	94156 KB	Output is correct
11	Correct	50 ms	94204 KB	Output is correct
12	Correct	51 ms	94228 KB	Output is correct
13	Correct	52 ms	94220 KB	Output is correct
14	Correct	52 ms	94220 KB	Output is correct
15	Correct	52 ms	94204 KB	Output is correct
16	Correct	51 ms	94156 KB	Output is correct
17	Correct	53 ms	94128 KB	Output is correct
18	Correct	53 ms	94240 KB	Output is correct
19	Correct	52 ms	94284 KB	Output is correct
20	Correct	63 ms	94324 KB	Output is correct
21	Correct	55 ms	94156 KB	Output is correct
22	Correct	53 ms	94292 KB	Output is correct
23	Correct	53 ms	94192 KB	Output is correct
24	Correct	52 ms	94220 KB	Output is correct
25	Correct	59 ms	94192 KB	Output is correct
26	Correct	60 ms	94188 KB	Output is correct
27	Correct	52 ms	94212 KB	Output is correct
28	Correct	58 ms	94236 KB	Output is correct
29	Correct	66 ms	94276 KB	Output is correct
30	Execution timed out	2094 ms	239932 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-