Submission #802025

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802025	2023-08-02T09:10:19 Z	Sohsoh84	Giraffes (JOI22_giraffes)	C++17	32 / 100	3125 ms	384 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--;
		*/	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	270 ms	320 KB	Output is correct
2	Correct	176 ms	320 KB	Output is correct
3	Correct	120 ms	340 KB	Output is correct
4	Correct	1579 ms	320 KB	Output is correct
5	Correct	1541 ms	316 KB	Output is correct
6	Correct	1367 ms	340 KB	Output is correct
7	Correct	160 ms	320 KB	Output is correct
8	Correct	167 ms	340 KB	Output is correct
9	Correct	1951 ms	320 KB	Output is correct
10	Correct	1501 ms	320 KB	Output is correct

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	270 ms	320 KB	Output is correct
2	Correct	176 ms	320 KB	Output is correct
3	Correct	120 ms	340 KB	Output is correct
4	Correct	1579 ms	320 KB	Output is correct
5	Correct	1541 ms	316 KB	Output is correct
6	Correct	1367 ms	340 KB	Output is correct
7	Correct	160 ms	320 KB	Output is correct
8	Correct	167 ms	340 KB	Output is correct
9	Correct	1951 ms	320 KB	Output is correct
10	Correct	1501 ms	320 KB	Output is correct
11	Correct	1797 ms	324 KB	Output is correct
12	Correct	1763 ms	316 KB	Output is correct
13	Correct	1264 ms	316 KB	Output is correct
14	Correct	2016 ms	320 KB	Output is correct
15	Correct	2290 ms	340 KB	Output is correct
16	Correct	2352 ms	340 KB	Output is correct
17	Correct	2387 ms	384 KB	Output is correct
18	Correct	2470 ms	320 KB	Output is correct
19	Correct	2313 ms	320 KB	Output is correct
20	Correct	2101 ms	340 KB	Output is correct

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	270 ms	320 KB	Output is correct
2	Correct	176 ms	320 KB	Output is correct
3	Correct	120 ms	340 KB	Output is correct
4	Correct	1579 ms	320 KB	Output is correct
5	Correct	1541 ms	316 KB	Output is correct
6	Correct	1367 ms	340 KB	Output is correct
7	Correct	160 ms	320 KB	Output is correct
8	Correct	167 ms	340 KB	Output is correct
9	Correct	1951 ms	320 KB	Output is correct
10	Correct	1501 ms	320 KB	Output is correct
11	Correct	1797 ms	324 KB	Output is correct
12	Correct	1763 ms	316 KB	Output is correct
13	Correct	1264 ms	316 KB	Output is correct
14	Correct	2016 ms	320 KB	Output is correct
15	Correct	2290 ms	340 KB	Output is correct
16	Correct	2352 ms	340 KB	Output is correct
17	Correct	2387 ms	384 KB	Output is correct
18	Correct	2470 ms	320 KB	Output is correct
19	Correct	2313 ms	320 KB	Output is correct
20	Correct	2101 ms	340 KB	Output is correct
21	Correct	2904 ms	336 KB	Output is correct
22	Incorrect	3125 ms	340 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #4

0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	270 ms	320 KB	Output is correct
2	Correct	176 ms	320 KB	Output is correct
3	Correct	120 ms	340 KB	Output is correct
4	Correct	1579 ms	320 KB	Output is correct
5	Correct	1541 ms	316 KB	Output is correct
6	Correct	1367 ms	340 KB	Output is correct
7	Correct	160 ms	320 KB	Output is correct
8	Correct	167 ms	340 KB	Output is correct
9	Correct	1951 ms	320 KB	Output is correct
10	Correct	1501 ms	320 KB	Output is correct
11	Correct	1797 ms	324 KB	Output is correct
12	Correct	1763 ms	316 KB	Output is correct
13	Correct	1264 ms	316 KB	Output is correct
14	Correct	2016 ms	320 KB	Output is correct
15	Correct	2290 ms	340 KB	Output is correct
16	Correct	2352 ms	340 KB	Output is correct
17	Correct	2387 ms	384 KB	Output is correct
18	Correct	2470 ms	320 KB	Output is correct
19	Correct	2313 ms	320 KB	Output is correct
20	Correct	2101 ms	340 KB	Output is correct
21	Correct	2904 ms	336 KB	Output is correct
22	Incorrect	3125 ms	340 KB	Output isn't correct
23	Halted	0 ms	0 KB	-