oj.uz

Submission #43107

# Submission time Handle Problem Language Result Execution time Memory
43107 2018-03-09T08:20:26 Z RayaBurong25_1 Ancient Books (IOI17_books) C++14
0 / 100
 2 ms 764 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 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 += 2LL*(it->first - it2->second.e);
		else if (ss < it->first)
			Ans += 2LL*(it->first - ss);
		it2 = it;
	}
	it = R.end();
	it--;
	if (it != R.begin() && ss > it->second.e)
		Ans += 2LL*(ss - it->second.e);
	return Ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 1 ms 516 KB Output is correct
3 Correct 1 ms 516 KB Output is correct
4 Correct 2 ms 516 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 1 ms 536 KB Output is correct
7 Correct 2 ms 536 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Runtime error 2 ms 728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 1 ms 516 KB Output is correct
3 Correct 1 ms 516 KB Output is correct
4 Correct 2 ms 516 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 1 ms 536 KB Output is correct
7 Correct 2 ms 536 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Runtime error 2 ms 728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 1 ms 516 KB Output is correct
3 Correct 1 ms 516 KB Output is correct
4 Correct 2 ms 516 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 1 ms 536 KB Output is correct
7 Correct 2 ms 536 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Runtime error 2 ms 728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 764 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 1 ms 516 KB Output is correct
3 Correct 1 ms 516 KB Output is correct
4 Correct 2 ms 516 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 1 ms 536 KB Output is correct
7 Correct 2 ms 536 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Runtime error 2 ms 728 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Halted 0 ms 0 KB -