답안 #802031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802031	2023-08-02T09:11:46 Z	Sohsoh84	Giraffes (JOI22_giraffes)	C++17	10 / 100	1881 ms	340 KB

giraffes

// Wounds should become scars but I'm cracked instead U+1FAE0
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, T[MAXN], P[MAXN], F[MAXN], ind[MAXN];

inline int rand_perm() {
	int l = 1, r = n;
	int fl = 1, fr = n;
	int ans = n;
	
	for (int i = 1; i <= n; i++) {
		if (P[l] == fl) {
			ans--;
			l++;
			fl++;
		} else if (P[l] == fr) {
			ans--;
			l++;
			fr--;
		} else if (P[r] == fl) {
			ans--;
			r--;
			fl++;
		} else if (P[r] == fr) {
			ans--;
			r--;
			fr--;
		} else {
			int tfl = fl;
			int tfr = fr;

			if (ind[fl] < l || ind[fl] > r) tfl++;
		//	else if (ind[fr] < l || ind[fr] > r) tfr--;
			else if (rng() % 2) tfl++;
			else tfr--;

			if (P[l] < fl || P[l] > fr) l++;
			else if (P[r] < fl || P[r] > fr) r--;
			else if (rng() % 2) l++;
			else r--;

			fl = tfl;
			fr = tfr;
		}
	}

	return ans;
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> P[i];
		ind[P[i]] = i;
	}

	int fuck = 10000000 * 13 / n;

	int ans = n;
	while (fuck--) {
		ans = min(ans, rand_perm());
	}

	cout << ans << endl;
	return 0;
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	217 ms	320 KB	Output is correct
2	Correct	178 ms	316 KB	Output is correct
3	Correct	136 ms	320 KB	Output is correct
4	Correct	1227 ms	320 KB	Output is correct
5	Correct	1041 ms	316 KB	Output is correct
6	Correct	1006 ms	320 KB	Output is correct
7	Correct	157 ms	320 KB	Output is correct
8	Correct	177 ms	340 KB	Output is correct
9	Correct	1564 ms	332 KB	Output is correct
10	Correct	1162 ms	340 KB	Output is correct

Subtask #2

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	217 ms	320 KB	Output is correct
2	Correct	178 ms	316 KB	Output is correct
3	Correct	136 ms	320 KB	Output is correct
4	Correct	1227 ms	320 KB	Output is correct
5	Correct	1041 ms	316 KB	Output is correct
6	Correct	1006 ms	320 KB	Output is correct
7	Correct	157 ms	320 KB	Output is correct
8	Correct	177 ms	340 KB	Output is correct
9	Correct	1564 ms	332 KB	Output is correct
10	Correct	1162 ms	340 KB	Output is correct
11	Correct	1479 ms	320 KB	Output is correct
12	Correct	1282 ms	340 KB	Output is correct
13	Correct	986 ms	340 KB	Output is correct
14	Correct	1529 ms	320 KB	Output is correct
15	Correct	1647 ms	316 KB	Output is correct
16	Correct	1705 ms	316 KB	Output is correct
17	Correct	1881 ms	340 KB	Output is correct
18	Correct	1734 ms	340 KB	Output is correct
19	Incorrect	1863 ms	332 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	217 ms	320 KB	Output is correct
2	Correct	178 ms	316 KB	Output is correct
3	Correct	136 ms	320 KB	Output is correct
4	Correct	1227 ms	320 KB	Output is correct
5	Correct	1041 ms	316 KB	Output is correct
6	Correct	1006 ms	320 KB	Output is correct
7	Correct	157 ms	320 KB	Output is correct
8	Correct	177 ms	340 KB	Output is correct
9	Correct	1564 ms	332 KB	Output is correct
10	Correct	1162 ms	340 KB	Output is correct
11	Correct	1479 ms	320 KB	Output is correct
12	Correct	1282 ms	340 KB	Output is correct
13	Correct	986 ms	340 KB	Output is correct
14	Correct	1529 ms	320 KB	Output is correct
15	Correct	1647 ms	316 KB	Output is correct
16	Correct	1705 ms	316 KB	Output is correct
17	Correct	1881 ms	340 KB	Output is correct
18	Correct	1734 ms	340 KB	Output is correct
19	Incorrect	1863 ms	332 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 41.0

#	결과	실행 시간	메모리	Grader output
1	Correct	217 ms	320 KB	Output is correct
2	Correct	178 ms	316 KB	Output is correct
3	Correct	136 ms	320 KB	Output is correct
4	Correct	1227 ms	320 KB	Output is correct
5	Correct	1041 ms	316 KB	Output is correct
6	Correct	1006 ms	320 KB	Output is correct
7	Correct	157 ms	320 KB	Output is correct
8	Correct	177 ms	340 KB	Output is correct
9	Correct	1564 ms	332 KB	Output is correct
10	Correct	1162 ms	340 KB	Output is correct
11	Correct	1479 ms	320 KB	Output is correct
12	Correct	1282 ms	340 KB	Output is correct
13	Correct	986 ms	340 KB	Output is correct
14	Correct	1529 ms	320 KB	Output is correct
15	Correct	1647 ms	316 KB	Output is correct
16	Correct	1705 ms	316 KB	Output is correct
17	Correct	1881 ms	340 KB	Output is correct
18	Correct	1734 ms	340 KB	Output is correct
19	Incorrect	1863 ms	332 KB	Output isn't correct
20	Halted	0 ms	0 KB	-