oj.uz

답안 #1039122

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039122 2024-07-30T13:14:29 Z Soumya1 고대 책들 (IOI17_books) C++17
0 / 100
 1 ms 348 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
long long minimum_walk(std::vector<int> p, int s) {
	long long ans = 0;
	int n = p.size();
	for (int i = 0; i < n; i++) {
		ans += abs(i - p[i]);
	}
	vector<bool> vis(n);
	vector<int> mn(n, n), mx(n);
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;
		int cur = i;
		vector<int> all;
		while (!vis[cur]) {
			all.push_back(cur);
			vis[cur] = true;
			mn[i] = min(mn[i], cur);
			mx[i] = max(mx[i], cur);
			cur = p[cur];
		}
		for (int j : all) mn[j] = mn[i], mx[j] = mx[i];
	}
	int L = mn[s], R = mx[s], l = s, r = s;
	auto simulate = [&]() {
		while (L < l || r < R) {
			if (L < l) {
				L = min(L, mn[l]);
				R = max(R, mx[l]);
				l--;
			} else {
				L = min(L, mn[r]);
				R = max(R, mx[r]);
				r++;
			}
		}
	};
	simulate();
	while (true) {
		bool first = false;
		int right_cost = 0;
		int m = r;
		for (int i = r + 1; i < n; i++) {
			if (mn[i] < l) {
				right_cost++;
				first = true;
				break;
			}
			if (mn[i] > m) right_cost++;
			m = max(m, mx[i]); 
		}
		bool second = false;
		int left_cost = 0;
		m = l;
		for (int i = l - 1; i >= 0; i--) {
			if (mx[i] > r) {
				left_cost++;
				second = true;
				break;
			}
			if (mx[i] < m) left_cost++;
			m = min(m, mn[i]);
		}
		if (!first) {
			ans += 2 * (left_cost + right_cost);
			break;
		}
		if (left_cost < right_cost) {
			ans += 2 * left_cost;
			for (int i = l + 1; i < n; i++) {
				L = min(L, mn[i]), R = max(R, mx[i]);
				if (mn[i] < l) break;
			}
			simulate();
		} else {
			ans += 2 * right_cost;
			for (int i = r - 1; i >= 0; i--) {
				L = min(L, mn[i]), R = max(R, mx[i]);
				if (mx[i] > r) break;
			}
			simulate();
		}
	}
	return ans;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:53:8: warning: variable 'second' set but not used [-Wunused-but-set-variable]
   53 |   bool second = false;
      |        ^~~~~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB 3rd lines differ - on the 1st token, expected: '5920', found: '5924'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 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 -