답안 #799274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
799274	2023-07-31T11:34:06 Z	LittleCube	고대 책들 (IOI17_books)	C++17	22 / 100	2000 ms	240160 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);
		}
	};

	check(s);

	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

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	94156 KB	Output is correct
2	Correct	45 ms	94120 KB	Output is correct
3	Correct	45 ms	94184 KB	Output is correct
4	Correct	53 ms	94192 KB	Output is correct
5	Correct	51 ms	94184 KB	Output is correct
6	Correct	47 ms	94160 KB	Output is correct
7	Correct	47 ms	94220 KB	Output is correct
8	Correct	45 ms	94124 KB	Output is correct
9	Correct	47 ms	94116 KB	Output is correct
10	Correct	47 ms	94244 KB	Output is correct
11	Correct	46 ms	94164 KB	Output is correct
12	Correct	47 ms	94208 KB	Output is correct
13	Correct	46 ms	94144 KB	Output is correct
14	Correct	47 ms	94140 KB	Output is correct
15	Correct	45 ms	94164 KB	Output is correct
16	Correct	46 ms	94204 KB	Output is correct
17	Correct	45 ms	94144 KB	Output is correct
18	Correct	45 ms	94212 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	94156 KB	Output is correct
2	Correct	45 ms	94120 KB	Output is correct
3	Correct	45 ms	94184 KB	Output is correct
4	Correct	53 ms	94192 KB	Output is correct
5	Correct	51 ms	94184 KB	Output is correct
6	Correct	47 ms	94160 KB	Output is correct
7	Correct	47 ms	94220 KB	Output is correct
8	Correct	45 ms	94124 KB	Output is correct
9	Correct	47 ms	94116 KB	Output is correct
10	Correct	47 ms	94244 KB	Output is correct
11	Correct	46 ms	94164 KB	Output is correct
12	Correct	47 ms	94208 KB	Output is correct
13	Correct	46 ms	94144 KB	Output is correct
14	Correct	47 ms	94140 KB	Output is correct
15	Correct	45 ms	94164 KB	Output is correct
16	Correct	46 ms	94204 KB	Output is correct
17	Correct	45 ms	94144 KB	Output is correct
18	Correct	45 ms	94212 KB	Output is correct
19	Correct	45 ms	94240 KB	Output is correct
20	Correct	47 ms	94348 KB	Output is correct
21	Correct	45 ms	94200 KB	Output is correct
22	Correct	46 ms	94284 KB	Output is correct
23	Correct	45 ms	94284 KB	Output is correct
24	Correct	47 ms	94224 KB	Output is correct
25	Correct	47 ms	94236 KB	Output is correct
26	Correct	53 ms	94232 KB	Output is correct
27	Correct	46 ms	94284 KB	Output is correct
28	Correct	46 ms	94284 KB	Output is correct
29	Correct	46 ms	94216 KB	Output is correct

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	94156 KB	Output is correct
2	Correct	45 ms	94120 KB	Output is correct
3	Correct	45 ms	94184 KB	Output is correct
4	Correct	53 ms	94192 KB	Output is correct
5	Correct	51 ms	94184 KB	Output is correct
6	Correct	47 ms	94160 KB	Output is correct
7	Correct	47 ms	94220 KB	Output is correct
8	Correct	45 ms	94124 KB	Output is correct
9	Correct	47 ms	94116 KB	Output is correct
10	Correct	47 ms	94244 KB	Output is correct
11	Correct	46 ms	94164 KB	Output is correct
12	Correct	47 ms	94208 KB	Output is correct
13	Correct	46 ms	94144 KB	Output is correct
14	Correct	47 ms	94140 KB	Output is correct
15	Correct	45 ms	94164 KB	Output is correct
16	Correct	46 ms	94204 KB	Output is correct
17	Correct	45 ms	94144 KB	Output is correct
18	Correct	45 ms	94212 KB	Output is correct
19	Correct	45 ms	94240 KB	Output is correct
20	Correct	47 ms	94348 KB	Output is correct
21	Correct	45 ms	94200 KB	Output is correct
22	Correct	46 ms	94284 KB	Output is correct
23	Correct	45 ms	94284 KB	Output is correct
24	Correct	47 ms	94224 KB	Output is correct
25	Correct	47 ms	94236 KB	Output is correct
26	Correct	53 ms	94232 KB	Output is correct
27	Correct	46 ms	94284 KB	Output is correct
28	Correct	46 ms	94284 KB	Output is correct
29	Correct	46 ms	94216 KB	Output is correct
30	Execution timed out	2085 ms	240160 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	51 ms	94284 KB	Output is correct
2	Correct	51 ms	94248 KB	Output is correct
3	Correct	51 ms	94216 KB	Output is correct
4	Correct	51 ms	94184 KB	Output is correct
5	Correct	51 ms	94224 KB	Output is correct
6	Correct	52 ms	94284 KB	Output is correct
7	Correct	51 ms	94252 KB	Output is correct
8	Correct	52 ms	94228 KB	Output is correct
9	Correct	52 ms	94192 KB	Output is correct
10	Correct	51 ms	94160 KB	Output is correct
11	Incorrect	52 ms	94228 KB	3rd lines differ - on the 1st token, expected: '446014', found: '446016'
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	94156 KB	Output is correct
2	Correct	45 ms	94120 KB	Output is correct
3	Correct	45 ms	94184 KB	Output is correct
4	Correct	53 ms	94192 KB	Output is correct
5	Correct	51 ms	94184 KB	Output is correct
6	Correct	47 ms	94160 KB	Output is correct
7	Correct	47 ms	94220 KB	Output is correct
8	Correct	45 ms	94124 KB	Output is correct
9	Correct	47 ms	94116 KB	Output is correct
10	Correct	47 ms	94244 KB	Output is correct
11	Correct	46 ms	94164 KB	Output is correct
12	Correct	47 ms	94208 KB	Output is correct
13	Correct	46 ms	94144 KB	Output is correct
14	Correct	47 ms	94140 KB	Output is correct
15	Correct	45 ms	94164 KB	Output is correct
16	Correct	46 ms	94204 KB	Output is correct
17	Correct	45 ms	94144 KB	Output is correct
18	Correct	45 ms	94212 KB	Output is correct
19	Correct	45 ms	94240 KB	Output is correct
20	Correct	47 ms	94348 KB	Output is correct
21	Correct	45 ms	94200 KB	Output is correct
22	Correct	46 ms	94284 KB	Output is correct
23	Correct	45 ms	94284 KB	Output is correct
24	Correct	47 ms	94224 KB	Output is correct
25	Correct	47 ms	94236 KB	Output is correct
26	Correct	53 ms	94232 KB	Output is correct
27	Correct	46 ms	94284 KB	Output is correct
28	Correct	46 ms	94284 KB	Output is correct
29	Correct	46 ms	94216 KB	Output is correct
30	Execution timed out	2085 ms	240160 KB	Time limit exceeded
31	Halted	0 ms	0 KB	-

답안 #799274

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 28.0

Subtask #4 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
0 / 20.0

Subtask #5
0 / 30.0