oj.uz

Submission #43112

# Submission time Handle Problem Language Result Execution time Memory
43112 2018-03-09T08:33:46 Z RayaBurong25_1 Ancient Books (IOI17_books) C++14
0 / 100
 2 ms 592 KB 
#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 still[1000005];
long long abs(long long a)
{
	return (a < 0)?-a:a;
}
long long min(long long a, long long b)
{
	return (a < b)?a:b;
}
long long max(long long a, long long 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}));
			else
				still[i] = 1;
		}
	}
	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 (i = 0; i < n; i++)
	// 	printf("%d ", still[i]);
	// printf("\n");
	if (still[ss])
	{
		for (i = ss; i >= 0 && still[i]; i--);
		if (i >= 0) Ans = 2LL*(ss - i);
		else Ans = 1e18;
		// printf("i%d\n", i);
		for (i = ss; i < n && still[i]; i++);
		if (i < n) Ans = min(Ans, 2LL*(i - ss));
		// printf("i%d\n", i);
	}
	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 += 2LL*(it->first - it2->second.e);
		it2 = it;
	}
	return Ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 1 ms 480 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 1 ms 480 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Incorrect 2 ms 592 KB 3rd lines differ - on the 1st token, expected: '0', found: '1000000000000000000'
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 1 ms 480 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 1 ms 480 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Incorrect 2 ms 592 KB 3rd lines differ - on the 1st token, expected: '0', found: '1000000000000000000'
10 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 1 ms 480 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 1 ms 480 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Incorrect 2 ms 592 KB 3rd lines differ - on the 1st token, expected: '0', found: '1000000000000000000'
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 592 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 1 ms 480 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 1 ms 480 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 592 KB Output is correct
9 Incorrect 2 ms 592 KB 3rd lines differ - on the 1st token, expected: '0', found: '1000000000000000000'
10 Halted 0 ms 0 KB -