Submission #801991

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
801991	2023-08-02T08:56:22 Z	Sohsoh84	Giraffes (JOI22_giraffes)	C++17	10 / 100	1519 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];
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--;
			else 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--;
			else 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	761 ms	320 KB	Output is correct
2	Correct	449 ms	340 KB	Output is correct
3	Correct	274 ms	316 KB	Output is correct
4	Correct	1458 ms	316 KB	Output is correct
5	Correct	1140 ms	320 KB	Output is correct
6	Correct	789 ms	316 KB	Output is correct
7	Correct	264 ms	316 KB	Output is correct
8	Correct	327 ms	340 KB	Output is correct
9	Correct	1519 ms	320 KB	Output is correct
10	Correct	1237 ms	340 KB	Output is correct

Subtask #2

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	761 ms	320 KB	Output is correct
2	Correct	449 ms	340 KB	Output is correct
3	Correct	274 ms	316 KB	Output is correct
4	Correct	1458 ms	316 KB	Output is correct
5	Correct	1140 ms	320 KB	Output is correct
6	Correct	789 ms	316 KB	Output is correct
7	Correct	264 ms	316 KB	Output is correct
8	Correct	327 ms	340 KB	Output is correct
9	Correct	1519 ms	320 KB	Output is correct
10	Correct	1237 ms	340 KB	Output is correct
11	Correct	1257 ms	320 KB	Output is correct
12	Incorrect	1267 ms	320 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	761 ms	320 KB	Output is correct
2	Correct	449 ms	340 KB	Output is correct
3	Correct	274 ms	316 KB	Output is correct
4	Correct	1458 ms	316 KB	Output is correct
5	Correct	1140 ms	320 KB	Output is correct
6	Correct	789 ms	316 KB	Output is correct
7	Correct	264 ms	316 KB	Output is correct
8	Correct	327 ms	340 KB	Output is correct
9	Correct	1519 ms	320 KB	Output is correct
10	Correct	1237 ms	340 KB	Output is correct
11	Correct	1257 ms	320 KB	Output is correct
12	Incorrect	1267 ms	320 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	761 ms	320 KB	Output is correct
2	Correct	449 ms	340 KB	Output is correct
3	Correct	274 ms	316 KB	Output is correct
4	Correct	1458 ms	316 KB	Output is correct
5	Correct	1140 ms	320 KB	Output is correct
6	Correct	789 ms	316 KB	Output is correct
7	Correct	264 ms	316 KB	Output is correct
8	Correct	327 ms	340 KB	Output is correct
9	Correct	1519 ms	320 KB	Output is correct
10	Correct	1237 ms	340 KB	Output is correct
11	Correct	1257 ms	320 KB	Output is correct
12	Incorrect	1267 ms	320 KB	Output isn't correct
13	Halted	0 ms	0 KB	-