답안 #43100 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43100	2018-03-09T08:08:18 Z	RayaBurong25_1	고대 책들 (IOI17_books)	C++14	12 / 100	2 ms	784 KB

books

#include "books.h"
#include <vector>
#include <map>
typedef struct range range;
struct range
{
	int e;
	long long m;
};
// bool operator<(range a, range b)
// {
// 	return a.s < b.s;
// }
int vis[1000005];
int abs(int a)
{
	return (a < 0)?-a:a;
}
int min(int a, int b)
{
	return (a < b)?a:b;
}
int max(int a, int b)
{
	return (a > b)?a:b;
}
long long minimum_walk(std::vector<int> p, int ss) {
	std::map<int, range> R;
	int i, n = p.size();
	int s, e;
	long long m;
	for (i = 0; i < n; i++)
	{
		if (!vis[i])
		{
			s = i;
			e = i;
			m = 0;
			while (!vis[i])
			{
				vis[i] = 1;
				m += abs(p[i] - i);
				i = p[i];
				s = min(s, i);
				e = max(e, i);
			}
			// printf("%d %d %lld\n", s, e, m);
			if (m != 0)
				R.insert(std::make_pair(s, range{e, m}));
		}
	}
	std::map<int, range>::iterator it, it2;
	for (it = R.begin(); it != R.end();)
	{
		if (it != R.begin() && it->second.e < it2->second.e)
		{
			it2->second.m += it->second.m;
			it = R.erase(it);
		}
		else if (it != R.begin() && it2->second.e > it->first)
		{
			it2->second.m += it->second.m;
			it2->second.e = it->second.e;
			it = R.erase(it);
		}
		else
		{
			it2 = it;
			it++;
		}
	}
	long long Ans = 0;
	for (it = R.begin(); it != R.end(); it++)
	{
		// printf("%d %d %lld\n", it->first, it->second.e, it->second.m);
		Ans += it->second.m;
		if (it != R.begin())
			Ans += it->first - it2->second.e;
		else
			Ans += 2*it->first;
		it2 = it;
	}
	return Ans;
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	352 KB	Output is correct
3	Correct	2 ms	352 KB	Output is correct
4	Correct	1 ms	404 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	2 ms	460 KB	Output is correct
7	Correct	1 ms	536 KB	Output is correct
8	Correct	1 ms	556 KB	Output is correct
9	Correct	1 ms	648 KB	Output is correct
10	Correct	2 ms	648 KB	Output is correct
11	Correct	1 ms	648 KB	Output is correct
12	Correct	1 ms	648 KB	Output is correct
13	Correct	2 ms	648 KB	Output is correct
14	Correct	1 ms	684 KB	Output is correct
15	Correct	1 ms	684 KB	Output is correct
16	Correct	2 ms	684 KB	Output is correct
17	Correct	2 ms	684 KB	Output is correct
18	Correct	2 ms	684 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	352 KB	Output is correct
3	Correct	2 ms	352 KB	Output is correct
4	Correct	1 ms	404 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	2 ms	460 KB	Output is correct
7	Correct	1 ms	536 KB	Output is correct
8	Correct	1 ms	556 KB	Output is correct
9	Correct	1 ms	648 KB	Output is correct
10	Correct	2 ms	648 KB	Output is correct
11	Correct	1 ms	648 KB	Output is correct
12	Correct	1 ms	648 KB	Output is correct
13	Correct	2 ms	648 KB	Output is correct
14	Correct	1 ms	684 KB	Output is correct
15	Correct	1 ms	684 KB	Output is correct
16	Correct	2 ms	684 KB	Output is correct
17	Correct	2 ms	684 KB	Output is correct
18	Correct	2 ms	684 KB	Output is correct
19	Correct	2 ms	736 KB	Output is correct
20	Correct	2 ms	772 KB	Output is correct
21	Correct	1 ms	772 KB	Output is correct
22	Incorrect	2 ms	780 KB	3rd lines differ - on the 1st token, expected: '2082', found: '1435'
23	Halted	0 ms	0 KB	-

Subtask #3
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	352 KB	Output is correct
3	Correct	2 ms	352 KB	Output is correct
4	Correct	1 ms	404 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	2 ms	460 KB	Output is correct
7	Correct	1 ms	536 KB	Output is correct
8	Correct	1 ms	556 KB	Output is correct
9	Correct	1 ms	648 KB	Output is correct
10	Correct	2 ms	648 KB	Output is correct
11	Correct	1 ms	648 KB	Output is correct
12	Correct	1 ms	648 KB	Output is correct
13	Correct	2 ms	648 KB	Output is correct
14	Correct	1 ms	684 KB	Output is correct
15	Correct	1 ms	684 KB	Output is correct
16	Correct	2 ms	684 KB	Output is correct
17	Correct	2 ms	684 KB	Output is correct
18	Correct	2 ms	684 KB	Output is correct
19	Correct	2 ms	736 KB	Output is correct
20	Correct	2 ms	772 KB	Output is correct
21	Correct	1 ms	772 KB	Output is correct
22	Incorrect	2 ms	780 KB	3rd lines differ - on the 1st token, expected: '2082', found: '1435'
23	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	784 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	2 ms	248 KB	Output is correct
2	Correct	2 ms	352 KB	Output is correct
3	Correct	2 ms	352 KB	Output is correct
4	Correct	1 ms	404 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	2 ms	460 KB	Output is correct
7	Correct	1 ms	536 KB	Output is correct
8	Correct	1 ms	556 KB	Output is correct
9	Correct	1 ms	648 KB	Output is correct
10	Correct	2 ms	648 KB	Output is correct
11	Correct	1 ms	648 KB	Output is correct
12	Correct	1 ms	648 KB	Output is correct
13	Correct	2 ms	648 KB	Output is correct
14	Correct	1 ms	684 KB	Output is correct
15	Correct	1 ms	684 KB	Output is correct
16	Correct	2 ms	684 KB	Output is correct
17	Correct	2 ms	684 KB	Output is correct
18	Correct	2 ms	684 KB	Output is correct
19	Correct	2 ms	736 KB	Output is correct
20	Correct	2 ms	772 KB	Output is correct
21	Correct	1 ms	772 KB	Output is correct
22	Incorrect	2 ms	780 KB	3rd lines differ - on the 1st token, expected: '2082', found: '1435'
23	Halted	0 ms	0 KB	-

답안 #43100

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 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
0 / 10.0

Subtask #3
0 / 28.0

Subtask #4
0 / 20.0

Subtask #5
0 / 30.0