Submission #802032

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802032	2023-08-02T09:14:51 Z	Sohsoh84	Giraffes (JOI22_giraffes)	C++17	10 / 100	1697 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[tfl] < l || ind[tfl] > r) tfl++;
			else if (ind[tfr] < l || ind[tfr] > r) tfr--;
			else {
				int x = rng() % 2;
				if (x) 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

#	Verdict	Execution time	Memory	Grader output
1	Correct	523 ms	340 KB	Output is correct
2	Correct	267 ms	320 KB	Output is correct
3	Correct	211 ms	320 KB	Output is correct
4	Correct	1275 ms	316 KB	Output is correct
5	Correct	1004 ms	320 KB	Output is correct
6	Correct	979 ms	320 KB	Output is correct
7	Correct	224 ms	316 KB	Output is correct
8	Correct	254 ms	320 KB	Output is correct
9	Correct	1438 ms	320 KB	Output is correct
10	Correct	1194 ms	316 KB	Output is correct

Subtask #2

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	523 ms	340 KB	Output is correct
2	Correct	267 ms	320 KB	Output is correct
3	Correct	211 ms	320 KB	Output is correct
4	Correct	1275 ms	316 KB	Output is correct
5	Correct	1004 ms	320 KB	Output is correct
6	Correct	979 ms	320 KB	Output is correct
7	Correct	224 ms	316 KB	Output is correct
8	Correct	254 ms	320 KB	Output is correct
9	Correct	1438 ms	320 KB	Output is correct
10	Correct	1194 ms	316 KB	Output is correct
11	Correct	1217 ms	320 KB	Output is correct
12	Correct	1287 ms	320 KB	Output is correct
13	Correct	948 ms	316 KB	Output is correct
14	Correct	1438 ms	340 KB	Output is correct
15	Correct	1575 ms	320 KB	Output is correct
16	Correct	1674 ms	320 KB	Output is correct
17	Correct	1697 ms	320 KB	Output is correct
18	Correct	1611 ms	320 KB	Output is correct
19	Incorrect	1623 ms	340 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	523 ms	340 KB	Output is correct
2	Correct	267 ms	320 KB	Output is correct
3	Correct	211 ms	320 KB	Output is correct
4	Correct	1275 ms	316 KB	Output is correct
5	Correct	1004 ms	320 KB	Output is correct
6	Correct	979 ms	320 KB	Output is correct
7	Correct	224 ms	316 KB	Output is correct
8	Correct	254 ms	320 KB	Output is correct
9	Correct	1438 ms	320 KB	Output is correct
10	Correct	1194 ms	316 KB	Output is correct
11	Correct	1217 ms	320 KB	Output is correct
12	Correct	1287 ms	320 KB	Output is correct
13	Correct	948 ms	316 KB	Output is correct
14	Correct	1438 ms	340 KB	Output is correct
15	Correct	1575 ms	320 KB	Output is correct
16	Correct	1674 ms	320 KB	Output is correct
17	Correct	1697 ms	320 KB	Output is correct
18	Correct	1611 ms	320 KB	Output is correct
19	Incorrect	1623 ms	340 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	523 ms	340 KB	Output is correct
2	Correct	267 ms	320 KB	Output is correct
3	Correct	211 ms	320 KB	Output is correct
4	Correct	1275 ms	316 KB	Output is correct
5	Correct	1004 ms	320 KB	Output is correct
6	Correct	979 ms	320 KB	Output is correct
7	Correct	224 ms	316 KB	Output is correct
8	Correct	254 ms	320 KB	Output is correct
9	Correct	1438 ms	320 KB	Output is correct
10	Correct	1194 ms	316 KB	Output is correct
11	Correct	1217 ms	320 KB	Output is correct
12	Correct	1287 ms	320 KB	Output is correct
13	Correct	948 ms	316 KB	Output is correct
14	Correct	1438 ms	340 KB	Output is correct
15	Correct	1575 ms	320 KB	Output is correct
16	Correct	1674 ms	320 KB	Output is correct
17	Correct	1697 ms	320 KB	Output is correct
18	Correct	1611 ms	320 KB	Output is correct
19	Incorrect	1623 ms	340 KB	Output isn't correct
20	Halted	0 ms	0 KB	-