Submission #801994

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
801994	2023-08-02T08:57:13 Z	Sohsoh84	Giraffes (JOI22_giraffes)	C++17	32 / 100	3559 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];
bool P_val[MAXN];

inline int rand_perm() {
	int l = 1, r = n;
	int fl = 1, fr = n;
	int ans = n;
	
	fill(P_val, P_val + n + 5, false);


	for (int i = 1; i <= n; i++) {
		if (P[l] == fl) {
			ans--;
			l++;
			fl++;
			P_val[fl] = true;
		} else if (P[l] == fr) {
			ans--;
			l++;
			fr--;
			P_val[fr] = true;
		} else if (P[r] == fl) {
			ans--;
			r--;
			fl++;
			P_val[fl] = true;
		} else if (P[r] == fr) {
			ans--;
			r--;
			fr--;
			P_val[fr] = true;
		} else {
	//		if (P_val[fl]) fl++;
	//		else if (P_val[fr]) fr--;
			if (rng() % 2) fl++;
			else fr--;

	//		if (P[l] < fl || P[l] > fr) P_val[P[l]] = true, l++;
	//		else if (P[r] < fl || P[r] > fr) P_val[P[r]] = true, r--;
			if (rng() % 2)
				P_val[P[l]] = true, l++;
			else
				P_val[P[r]] = true, 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];

	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	539 ms	316 KB	Output is correct
2	Correct	345 ms	320 KB	Output is correct
3	Correct	200 ms	340 KB	Output is correct
4	Correct	2066 ms	384 KB	Output is correct
5	Correct	2445 ms	340 KB	Output is correct
6	Correct	1891 ms	316 KB	Output is correct
7	Correct	179 ms	212 KB	Output is correct
8	Correct	240 ms	324 KB	Output is correct
9	Correct	2718 ms	320 KB	Output is correct
10	Correct	2322 ms	320 KB	Output is correct

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	539 ms	316 KB	Output is correct
2	Correct	345 ms	320 KB	Output is correct
3	Correct	200 ms	340 KB	Output is correct
4	Correct	2066 ms	384 KB	Output is correct
5	Correct	2445 ms	340 KB	Output is correct
6	Correct	1891 ms	316 KB	Output is correct
7	Correct	179 ms	212 KB	Output is correct
8	Correct	240 ms	324 KB	Output is correct
9	Correct	2718 ms	320 KB	Output is correct
10	Correct	2322 ms	320 KB	Output is correct
11	Correct	2645 ms	320 KB	Output is correct
12	Correct	2459 ms	320 KB	Output is correct
13	Correct	1860 ms	340 KB	Output is correct
14	Correct	2784 ms	316 KB	Output is correct
15	Correct	3075 ms	320 KB	Output is correct
16	Correct	3057 ms	320 KB	Output is correct
17	Correct	3282 ms	320 KB	Output is correct
18	Correct	3091 ms	316 KB	Output is correct
19	Correct	3127 ms	340 KB	Output is correct
20	Correct	2958 ms	316 KB	Output is correct

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	539 ms	316 KB	Output is correct
2	Correct	345 ms	320 KB	Output is correct
3	Correct	200 ms	340 KB	Output is correct
4	Correct	2066 ms	384 KB	Output is correct
5	Correct	2445 ms	340 KB	Output is correct
6	Correct	1891 ms	316 KB	Output is correct
7	Correct	179 ms	212 KB	Output is correct
8	Correct	240 ms	324 KB	Output is correct
9	Correct	2718 ms	320 KB	Output is correct
10	Correct	2322 ms	320 KB	Output is correct
11	Correct	2645 ms	320 KB	Output is correct
12	Correct	2459 ms	320 KB	Output is correct
13	Correct	1860 ms	340 KB	Output is correct
14	Correct	2784 ms	316 KB	Output is correct
15	Correct	3075 ms	320 KB	Output is correct
16	Correct	3057 ms	320 KB	Output is correct
17	Correct	3282 ms	320 KB	Output is correct
18	Correct	3091 ms	316 KB	Output is correct
19	Correct	3127 ms	340 KB	Output is correct
20	Correct	2958 ms	316 KB	Output is correct
21	Correct	3371 ms	320 KB	Output is correct
22	Incorrect	3559 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	539 ms	316 KB	Output is correct
2	Correct	345 ms	320 KB	Output is correct
3	Correct	200 ms	340 KB	Output is correct
4	Correct	2066 ms	384 KB	Output is correct
5	Correct	2445 ms	340 KB	Output is correct
6	Correct	1891 ms	316 KB	Output is correct
7	Correct	179 ms	212 KB	Output is correct
8	Correct	240 ms	324 KB	Output is correct
9	Correct	2718 ms	320 KB	Output is correct
10	Correct	2322 ms	320 KB	Output is correct
11	Correct	2645 ms	320 KB	Output is correct
12	Correct	2459 ms	320 KB	Output is correct
13	Correct	1860 ms	340 KB	Output is correct
14	Correct	2784 ms	316 KB	Output is correct
15	Correct	3075 ms	320 KB	Output is correct
16	Correct	3057 ms	320 KB	Output is correct
17	Correct	3282 ms	320 KB	Output is correct
18	Correct	3091 ms	316 KB	Output is correct
19	Correct	3127 ms	340 KB	Output is correct
20	Correct	2958 ms	316 KB	Output is correct
21	Correct	3371 ms	320 KB	Output is correct
22	Incorrect	3559 ms	340 KB	Output isn't correct
23	Halted	0 ms	0 KB	-