Submission #799266

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
799266	2023-07-31T11:28:27 Z	LittleCube	Ancient Books (IOI17_books)	C++17	22 / 100	2000 ms	246644 KB

books

#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:99:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |    for (int i = 0; i < cur.size(); i++)
      |                    ~~^~~~~~~~~~~~
books.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |    for (int i = 0; i < cur.size(); i++)
      |                    ~~^~~~~~~~~~~~

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	94176 KB	Output is correct
2	Correct	57 ms	94152 KB	Output is correct
3	Correct	47 ms	94220 KB	Output is correct
4	Correct	49 ms	94124 KB	Output is correct
5	Correct	47 ms	94124 KB	Output is correct
6	Correct	47 ms	94156 KB	Output is correct
7	Correct	46 ms	94120 KB	Output is correct
8	Correct	58 ms	94192 KB	Output is correct
9	Correct	47 ms	94128 KB	Output is correct
10	Correct	47 ms	94156 KB	Output is correct
11	Correct	47 ms	94216 KB	Output is correct
12	Correct	47 ms	94164 KB	Output is correct
13	Correct	49 ms	94148 KB	Output is correct
14	Correct	51 ms	94156 KB	Output is correct
15	Correct	48 ms	94256 KB	Output is correct
16	Correct	49 ms	94224 KB	Output is correct
17	Correct	48 ms	94144 KB	Output is correct
18	Correct	51 ms	94244 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	94176 KB	Output is correct
2	Correct	57 ms	94152 KB	Output is correct
3	Correct	47 ms	94220 KB	Output is correct
4	Correct	49 ms	94124 KB	Output is correct
5	Correct	47 ms	94124 KB	Output is correct
6	Correct	47 ms	94156 KB	Output is correct
7	Correct	46 ms	94120 KB	Output is correct
8	Correct	58 ms	94192 KB	Output is correct
9	Correct	47 ms	94128 KB	Output is correct
10	Correct	47 ms	94156 KB	Output is correct
11	Correct	47 ms	94216 KB	Output is correct
12	Correct	47 ms	94164 KB	Output is correct
13	Correct	49 ms	94148 KB	Output is correct
14	Correct	51 ms	94156 KB	Output is correct
15	Correct	48 ms	94256 KB	Output is correct
16	Correct	49 ms	94224 KB	Output is correct
17	Correct	48 ms	94144 KB	Output is correct
18	Correct	51 ms	94244 KB	Output is correct
19	Correct	48 ms	94352 KB	Output is correct
20	Correct	49 ms	94336 KB	Output is correct
21	Correct	58 ms	94156 KB	Output is correct
22	Correct	49 ms	94188 KB	Output is correct
23	Correct	50 ms	94300 KB	Output is correct
24	Correct	49 ms	94184 KB	Output is correct
25	Correct	49 ms	94220 KB	Output is correct
26	Correct	51 ms	94272 KB	Output is correct
27	Correct	49 ms	94312 KB	Output is correct
28	Correct	52 ms	94324 KB	Output is correct
29	Correct	49 ms	94220 KB	Output is correct

Subtask #3

0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	94176 KB	Output is correct
2	Correct	57 ms	94152 KB	Output is correct
3	Correct	47 ms	94220 KB	Output is correct
4	Correct	49 ms	94124 KB	Output is correct
5	Correct	47 ms	94124 KB	Output is correct
6	Correct	47 ms	94156 KB	Output is correct
7	Correct	46 ms	94120 KB	Output is correct
8	Correct	58 ms	94192 KB	Output is correct
9	Correct	47 ms	94128 KB	Output is correct
10	Correct	47 ms	94156 KB	Output is correct
11	Correct	47 ms	94216 KB	Output is correct
12	Correct	47 ms	94164 KB	Output is correct
13	Correct	49 ms	94148 KB	Output is correct
14	Correct	51 ms	94156 KB	Output is correct
15	Correct	48 ms	94256 KB	Output is correct
16	Correct	49 ms	94224 KB	Output is correct
17	Correct	48 ms	94144 KB	Output is correct
18	Correct	51 ms	94244 KB	Output is correct
19	Correct	48 ms	94352 KB	Output is correct
20	Correct	49 ms	94336 KB	Output is correct
21	Correct	58 ms	94156 KB	Output is correct
22	Correct	49 ms	94188 KB	Output is correct
23	Correct	50 ms	94300 KB	Output is correct
24	Correct	49 ms	94184 KB	Output is correct
25	Correct	49 ms	94220 KB	Output is correct
26	Correct	51 ms	94272 KB	Output is correct
27	Correct	49 ms	94312 KB	Output is correct
28	Correct	52 ms	94324 KB	Output is correct
29	Correct	49 ms	94220 KB	Output is correct
30	Execution timed out	2079 ms	246644 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	94284 KB	Output is correct
2	Correct	52 ms	94260 KB	Output is correct
3	Correct	49 ms	94244 KB	Output is correct
4	Incorrect	53 ms	94256 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	46 ms	94176 KB	Output is correct
2	Correct	57 ms	94152 KB	Output is correct
3	Correct	47 ms	94220 KB	Output is correct
4	Correct	49 ms	94124 KB	Output is correct
5	Correct	47 ms	94124 KB	Output is correct
6	Correct	47 ms	94156 KB	Output is correct
7	Correct	46 ms	94120 KB	Output is correct
8	Correct	58 ms	94192 KB	Output is correct
9	Correct	47 ms	94128 KB	Output is correct
10	Correct	47 ms	94156 KB	Output is correct
11	Correct	47 ms	94216 KB	Output is correct
12	Correct	47 ms	94164 KB	Output is correct
13	Correct	49 ms	94148 KB	Output is correct
14	Correct	51 ms	94156 KB	Output is correct
15	Correct	48 ms	94256 KB	Output is correct
16	Correct	49 ms	94224 KB	Output is correct
17	Correct	48 ms	94144 KB	Output is correct
18	Correct	51 ms	94244 KB	Output is correct
19	Correct	48 ms	94352 KB	Output is correct
20	Correct	49 ms	94336 KB	Output is correct
21	Correct	58 ms	94156 KB	Output is correct
22	Correct	49 ms	94188 KB	Output is correct
23	Correct	50 ms	94300 KB	Output is correct
24	Correct	49 ms	94184 KB	Output is correct
25	Correct	49 ms	94220 KB	Output is correct
26	Correct	51 ms	94272 KB	Output is correct
27	Correct	49 ms	94312 KB	Output is correct
28	Correct	52 ms	94324 KB	Output is correct
29	Correct	49 ms	94220 KB	Output is correct
30	Execution timed out	2079 ms	246644 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-