답안 #65779 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65779	2018-08-08T18:02:52 Z	MatheusLealV	고대 책들 (IOI17_books)	C++17	22 / 100	2000 ms	71852 KB

books

#include "books.h"
#define N 1000005
#define f first
#define ss second
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

ll ans = 0;

ll n, maior[N], menor[N], qtd = 0, ok[N], en;

int pai[N], peso[N];

int find(int x)
{
	if(x == pai[x]) return x;

	return pai[x] = find(pai[x]);
}

void join(int a, int b)
{
	a = find(a), b = find(b);

	//cout<<"JOIN "<<a<<" "<<b<<"\n";

	if(a == b) return;

	if(peso[a] > peso[b]) pai[b] = a;

	else if(peso[a] < peso[b]) pai[a] = b;

	else pai[a] = b, peso[b] ++;
}

vector<int> g;

void dfs(ll x, ll &mx, ll &mn)
{
	mx = max(mx, maior[x]);

	if(ok[x]) return;

	ok[x] = 1;

	dfs(g[x], mx, mn);
}

ll minimum_walk(vector<int> p, int s)
{
	n = p.size();

	g = p;

	for(ll i = 0; i < n; i++) ans += abs(i - p[i]);

	for(int i = 0; i < n; i++) maior[i] = menor[i] = i;

	for(ll i = n - 1; i >= 0; i--)
	{
		if(p[i] != i)
		{
			en = i;

			break;
		}
	}

	vector<pii> sweep;

	for(int i = 0; i <= en; i++)
	{
		if(ok[i]) continue;

		dfs(i, maior[i], menor[i]);

		//cout<<"COLOCA "<<menor[i]<<" "<<maior[i]<<"\n";

		sweep.push_back({menor[i], maior[i]});
	}

	sort(sweep.begin(), sweep.end());

	for(int i = 0; i < (int)sweep.size(); i++) pai[i] = i;

	for(int i = 0; i < (int)sweep.size(); i++)
	{
		auto b = sweep[i];

		for(int j = 0; j < i; j++)
		{
			auto a = sweep[j];

			if(a.f <= b.f and b.f <= a.ss) join(i, i - 1);
		}

	}

	set<int> q;

	for(int i = 0; i < (int)sweep.size(); i++)
	{
		q.insert(find(i));
	}

	ll qtd = q.size();

	//cout<<q.size()<<"\n";

	return ans + 2*(qtd - 1);
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	2 ms	492 KB	Output is correct
3	Correct	3 ms	572 KB	Output is correct
4	Correct	3 ms	572 KB	Output is correct
5	Correct	2 ms	668 KB	Output is correct
6	Correct	2 ms	668 KB	Output is correct
7	Correct	3 ms	668 KB	Output is correct
8	Correct	2 ms	668 KB	Output is correct
9	Correct	2 ms	668 KB	Output is correct
10	Correct	3 ms	716 KB	Output is correct
11	Correct	3 ms	716 KB	Output is correct
12	Correct	3 ms	716 KB	Output is correct
13	Correct	2 ms	716 KB	Output is correct
14	Correct	2 ms	716 KB	Output is correct
15	Correct	2 ms	716 KB	Output is correct
16	Correct	3 ms	716 KB	Output is correct
17	Correct	3 ms	716 KB	Output is correct
18	Correct	3 ms	716 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	2 ms	492 KB	Output is correct
3	Correct	3 ms	572 KB	Output is correct
4	Correct	3 ms	572 KB	Output is correct
5	Correct	2 ms	668 KB	Output is correct
6	Correct	2 ms	668 KB	Output is correct
7	Correct	3 ms	668 KB	Output is correct
8	Correct	2 ms	668 KB	Output is correct
9	Correct	2 ms	668 KB	Output is correct
10	Correct	3 ms	716 KB	Output is correct
11	Correct	3 ms	716 KB	Output is correct
12	Correct	3 ms	716 KB	Output is correct
13	Correct	2 ms	716 KB	Output is correct
14	Correct	2 ms	716 KB	Output is correct
15	Correct	2 ms	716 KB	Output is correct
16	Correct	3 ms	716 KB	Output is correct
17	Correct	3 ms	716 KB	Output is correct
18	Correct	3 ms	716 KB	Output is correct
19	Correct	2 ms	716 KB	Output is correct
20	Correct	2 ms	716 KB	Output is correct
21	Correct	2 ms	720 KB	Output is correct
22	Correct	3 ms	728 KB	Output is correct
23	Correct	3 ms	728 KB	Output is correct
24	Correct	2 ms	732 KB	Output is correct
25	Correct	2 ms	736 KB	Output is correct
26	Correct	3 ms	740 KB	Output is correct
27	Correct	2 ms	740 KB	Output is correct
28	Correct	3 ms	748 KB	Output is correct
29	Correct	2 ms	784 KB	Output is correct

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	376 KB	Output is correct
2	Correct	2 ms	492 KB	Output is correct
3	Correct	3 ms	572 KB	Output is correct
4	Correct	3 ms	572 KB	Output is correct
5	Correct	2 ms	668 KB	Output is correct
6	Correct	2 ms	668 KB	Output is correct
7	Correct	3 ms	668 KB	Output is correct
8	Correct	2 ms	668 KB	Output is correct
9	Correct	2 ms	668 KB	Output is correct
10	Correct	3 ms	716 KB	Output is correct
11	Correct	3 ms	716 KB	Output is correct
12	Correct	3 ms	716 KB	Output is correct
13	Correct	2 ms	716 KB	Output is correct
14	Correct	2 ms	716 KB	Output is correct
15	Correct	2 ms	716 KB	Output is correct
16	Correct	3 ms	716 KB	Output is correct
17	Correct	3 ms	716 KB	Output is correct
18	Correct	3 ms	716 KB	Output is correct
19	Correct	2 ms	716 KB	Output is correct
20	Correct	2 ms	716 KB	Output is correct
21	Correct	2 ms	720 KB	Output is correct
22	Correct	3 ms	728 KB	Output is correct
23	Correct	3 ms	728 KB	Output is correct
24	Correct	2 ms	732 KB	Output is correct
25	Correct	2 ms	736 KB	Output is correct
26	Correct	3 ms	740 KB	Output is correct
27	Correct	2 ms	740 KB	Output is correct
28	Correct	3 ms	748 KB	Output is correct
29	Correct	2 ms	784 KB	Output is correct
30	Correct	419 ms	42768 KB	Output is correct
31	Correct	338 ms	49656 KB	Output is correct
32	Correct	153 ms	49656 KB	Output is correct
33	Execution timed out	2074 ms	71852 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	71852 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	4 ms	376 KB	Output is correct
2	Correct	2 ms	492 KB	Output is correct
3	Correct	3 ms	572 KB	Output is correct
4	Correct	3 ms	572 KB	Output is correct
5	Correct	2 ms	668 KB	Output is correct
6	Correct	2 ms	668 KB	Output is correct
7	Correct	3 ms	668 KB	Output is correct
8	Correct	2 ms	668 KB	Output is correct
9	Correct	2 ms	668 KB	Output is correct
10	Correct	3 ms	716 KB	Output is correct
11	Correct	3 ms	716 KB	Output is correct
12	Correct	3 ms	716 KB	Output is correct
13	Correct	2 ms	716 KB	Output is correct
14	Correct	2 ms	716 KB	Output is correct
15	Correct	2 ms	716 KB	Output is correct
16	Correct	3 ms	716 KB	Output is correct
17	Correct	3 ms	716 KB	Output is correct
18	Correct	3 ms	716 KB	Output is correct
19	Correct	2 ms	716 KB	Output is correct
20	Correct	2 ms	716 KB	Output is correct
21	Correct	2 ms	720 KB	Output is correct
22	Correct	3 ms	728 KB	Output is correct
23	Correct	3 ms	728 KB	Output is correct
24	Correct	2 ms	732 KB	Output is correct
25	Correct	2 ms	736 KB	Output is correct
26	Correct	3 ms	740 KB	Output is correct
27	Correct	2 ms	740 KB	Output is correct
28	Correct	3 ms	748 KB	Output is correct
29	Correct	2 ms	784 KB	Output is correct
30	Correct	419 ms	42768 KB	Output is correct
31	Correct	338 ms	49656 KB	Output is correct
32	Correct	153 ms	49656 KB	Output is correct
33	Execution timed out	2074 ms	71852 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

답안 #65779

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