Submission #802013

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802013	2023-08-02T09:05:21 Z	Sohsoh84	Giraffes (JOI22_giraffes)	C++17	10 / 100	1720 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 {
			if (ind[fl] < l || ind[fl] > r) fl++;
			else if (ind[fr] < l || ind[fr] > r) fr--;
			else if (rng() % 2) fl++;
			else fr--;

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

	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

#	Verdict	Execution time	Memory	Grader output
1	Correct	458 ms	340 KB	Output is correct
2	Correct	302 ms	332 KB	Output is correct
3	Correct	178 ms	340 KB	Output is correct
4	Correct	1213 ms	340 KB	Output is correct
5	Correct	993 ms	320 KB	Output is correct
6	Correct	974 ms	340 KB	Output is correct
7	Correct	195 ms	320 KB	Output is correct
8	Correct	207 ms	336 KB	Output is correct
9	Correct	1408 ms	320 KB	Output is correct
10	Correct	1200 ms	320 KB	Output is correct

Subtask #2

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	458 ms	340 KB	Output is correct
2	Correct	302 ms	332 KB	Output is correct
3	Correct	178 ms	340 KB	Output is correct
4	Correct	1213 ms	340 KB	Output is correct
5	Correct	993 ms	320 KB	Output is correct
6	Correct	974 ms	340 KB	Output is correct
7	Correct	195 ms	320 KB	Output is correct
8	Correct	207 ms	336 KB	Output is correct
9	Correct	1408 ms	320 KB	Output is correct
10	Correct	1200 ms	320 KB	Output is correct
11	Correct	1208 ms	320 KB	Output is correct
12	Correct	1281 ms	340 KB	Output is correct
13	Correct	938 ms	340 KB	Output is correct
14	Correct	1446 ms	332 KB	Output is correct
15	Correct	1601 ms	340 KB	Output is correct
16	Correct	1639 ms	340 KB	Output is correct
17	Correct	1720 ms	340 KB	Output is correct
18	Correct	1625 ms	340 KB	Output is correct
19	Incorrect	1682 ms	212 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	458 ms	340 KB	Output is correct
2	Correct	302 ms	332 KB	Output is correct
3	Correct	178 ms	340 KB	Output is correct
4	Correct	1213 ms	340 KB	Output is correct
5	Correct	993 ms	320 KB	Output is correct
6	Correct	974 ms	340 KB	Output is correct
7	Correct	195 ms	320 KB	Output is correct
8	Correct	207 ms	336 KB	Output is correct
9	Correct	1408 ms	320 KB	Output is correct
10	Correct	1200 ms	320 KB	Output is correct
11	Correct	1208 ms	320 KB	Output is correct
12	Correct	1281 ms	340 KB	Output is correct
13	Correct	938 ms	340 KB	Output is correct
14	Correct	1446 ms	332 KB	Output is correct
15	Correct	1601 ms	340 KB	Output is correct
16	Correct	1639 ms	340 KB	Output is correct
17	Correct	1720 ms	340 KB	Output is correct
18	Correct	1625 ms	340 KB	Output is correct
19	Incorrect	1682 ms	212 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	458 ms	340 KB	Output is correct
2	Correct	302 ms	332 KB	Output is correct
3	Correct	178 ms	340 KB	Output is correct
4	Correct	1213 ms	340 KB	Output is correct
5	Correct	993 ms	320 KB	Output is correct
6	Correct	974 ms	340 KB	Output is correct
7	Correct	195 ms	320 KB	Output is correct
8	Correct	207 ms	336 KB	Output is correct
9	Correct	1408 ms	320 KB	Output is correct
10	Correct	1200 ms	320 KB	Output is correct
11	Correct	1208 ms	320 KB	Output is correct
12	Correct	1281 ms	340 KB	Output is correct
13	Correct	938 ms	340 KB	Output is correct
14	Correct	1446 ms	332 KB	Output is correct
15	Correct	1601 ms	340 KB	Output is correct
16	Correct	1639 ms	340 KB	Output is correct
17	Correct	1720 ms	340 KB	Output is correct
18	Correct	1625 ms	340 KB	Output is correct
19	Incorrect	1682 ms	212 KB	Output isn't correct
20	Halted	0 ms	0 KB	-