oj.uz

Submission #1080499

# Submission time Handle Problem Language Result Execution time Memory
1080499 2024-08-29T10:33:44 Z Elias Ancient Books (IOI17_books) C++17
0 / 100
 1 ms 424 KB 
#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>

using namespace std;

#ifdef _DEBUG
long long minimum_walk(std::vector<int> p, int s);
#else
#include "books.h"
#endif

int n;

#define ll long long

struct Group
{
	int l = 10000000, r = -1;
};

bool operator<(Group a, Group b) {
	return a.l < b.l;
}

long long minimum_walk(std::vector<int> p, int s)
{
	n = p.size();
	vector<int> visited(p.size());

	vector<Group> groups;

	ll cost = 0;
	for (int i = 0; i < n; i++)
	{
		int index = i;
		if (visited[i])
			continue;

		Group group;

		do
		{
			visited[index] = 1;
			group.l = min(group.l, index);
			group.r = max(group.r, index);

			int new_index = p[index];
			cost += abs<ll>(index - new_index);
			index = new_index;
		} while (index != i);

		groups.push_back(group);
	}

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

	int ending = 0;

	ll extra_cost = 0;

	for (auto [l, r] : groups) {
		if (l <= ending) {
			ending = max(ending, r);
		} else {
			extra_cost += 2;
			ending = max(ending, r);
		}
	}

	return cost + extra_cost;
}

#ifdef _DEBUG

using namespace std;

int main()
{
	int n, s;
	assert(2 == scanf("%d %d", &n, &s));

	vector<int> p((unsigned)n);
	for (int i = 0; i < n; i++)
		assert(1 == scanf("%d", &p[(unsigned)i]));

	long long res = minimum_walk(p, s);
	printf("%lld\n", res);
	return 0;
}

#endif

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 0 ms 348 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 424 KB Output is correct
5 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
6 Halted 0 ms 0 KB -