Submission #802017

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802017	2023-08-02T09:06:45 Z	Sohsoh84	Giraffes (JOI22_giraffes)	C++17	10 / 100	1686 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

#	Verdict	Execution time	Memory	Grader output
1	Correct	496 ms	316 KB	Output is correct
2	Correct	275 ms	340 KB	Output is correct
3	Correct	205 ms	212 KB	Output is correct
4	Correct	1268 ms	320 KB	Output is correct
5	Correct	1000 ms	320 KB	Output is correct
6	Correct	975 ms	328 KB	Output is correct
7	Correct	205 ms	212 KB	Output is correct
8	Correct	241 ms	320 KB	Output is correct
9	Correct	1436 ms	332 KB	Output is correct
10	Correct	1214 ms	316 KB	Output is correct

Subtask #2

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	496 ms	316 KB	Output is correct
2	Correct	275 ms	340 KB	Output is correct
3	Correct	205 ms	212 KB	Output is correct
4	Correct	1268 ms	320 KB	Output is correct
5	Correct	1000 ms	320 KB	Output is correct
6	Correct	975 ms	328 KB	Output is correct
7	Correct	205 ms	212 KB	Output is correct
8	Correct	241 ms	320 KB	Output is correct
9	Correct	1436 ms	332 KB	Output is correct
10	Correct	1214 ms	316 KB	Output is correct
11	Correct	1231 ms	316 KB	Output is correct
12	Correct	1277 ms	332 KB	Output is correct
13	Correct	887 ms	320 KB	Output is correct
14	Correct	1427 ms	340 KB	Output is correct
15	Correct	1540 ms	316 KB	Output is correct
16	Correct	1662 ms	328 KB	Output is correct
17	Correct	1686 ms	332 KB	Output is correct
18	Correct	1622 ms	316 KB	Output is correct
19	Incorrect	1663 ms	316 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	496 ms	316 KB	Output is correct
2	Correct	275 ms	340 KB	Output is correct
3	Correct	205 ms	212 KB	Output is correct
4	Correct	1268 ms	320 KB	Output is correct
5	Correct	1000 ms	320 KB	Output is correct
6	Correct	975 ms	328 KB	Output is correct
7	Correct	205 ms	212 KB	Output is correct
8	Correct	241 ms	320 KB	Output is correct
9	Correct	1436 ms	332 KB	Output is correct
10	Correct	1214 ms	316 KB	Output is correct
11	Correct	1231 ms	316 KB	Output is correct
12	Correct	1277 ms	332 KB	Output is correct
13	Correct	887 ms	320 KB	Output is correct
14	Correct	1427 ms	340 KB	Output is correct
15	Correct	1540 ms	316 KB	Output is correct
16	Correct	1662 ms	328 KB	Output is correct
17	Correct	1686 ms	332 KB	Output is correct
18	Correct	1622 ms	316 KB	Output is correct
19	Incorrect	1663 ms	316 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	496 ms	316 KB	Output is correct
2	Correct	275 ms	340 KB	Output is correct
3	Correct	205 ms	212 KB	Output is correct
4	Correct	1268 ms	320 KB	Output is correct
5	Correct	1000 ms	320 KB	Output is correct
6	Correct	975 ms	328 KB	Output is correct
7	Correct	205 ms	212 KB	Output is correct
8	Correct	241 ms	320 KB	Output is correct
9	Correct	1436 ms	332 KB	Output is correct
10	Correct	1214 ms	316 KB	Output is correct
11	Correct	1231 ms	316 KB	Output is correct
12	Correct	1277 ms	332 KB	Output is correct
13	Correct	887 ms	320 KB	Output is correct
14	Correct	1427 ms	340 KB	Output is correct
15	Correct	1540 ms	316 KB	Output is correct
16	Correct	1662 ms	328 KB	Output is correct
17	Correct	1686 ms	332 KB	Output is correct
18	Correct	1622 ms	316 KB	Output is correct
19	Incorrect	1663 ms	316 KB	Output isn't correct
20	Halted	0 ms	0 KB	-