oj.uz

Submission #54188

# Submission time Handle Problem Language Result Execution time Memory
54188 2018-07-02T17:01:07 Z radoslav11 Ancient Books (IOI17_books) C++14
0 / 100
 3 ms 564 KB 
#include <bits/stdc++.h>
#include "books.h"
//#include "Lgrader.cpp"

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

int n;
int p[MAXN];
bool used[MAXN];

pair<int, int> dfs(int u)
{
	used[u] = true;
	pair<int, int> ret = {u, u};

	if(!used[p[u]])
	{
		pair<int, int> oth = dfs(p[u]);
		chkmax(ret.second, oth.second);
		chkmin(ret.first, oth.first);
	}

	return ret;
}

long long minimum_walk(std::vector<int> p, int s) 
{
	if(s != 0) return -1;

	n = p.size();
	for(int i = 0; i < n; i++)
		::p[i] = p[i];

	int64_t answer = 0;
	for(int i = 0; i < n; i++)
		answer += abs(i - p[i]);

	vector<pair<int, int> > li;
	for(int i = 0; i < n; i++)
		if(i != p[i] && !used[i])
			li.push_back(dfs(i));			

	sort(li.begin(), li.end());
	
	vector<pair<int, int> > tmp;
	for(int i = 0; i < n; i++)
		if(tmp.empty() || tmp.back().second < li[i].first) tmp.push_back(li[i]);
		else chkmax(tmp[tmp.size() - 1].second, li[i].second);

	int last = 0;
	for(auto it: li)
	{
		answer += 2 * (it.first - last);
		last = it.second;
	}

	return answer;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 30.0

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