Submission #802003

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802003	2023-08-02T09:00:52 Z	Sohsoh84	Giraffes (JOI22_giraffes)	C++17	10 / 100	1943 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--;
			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	682 ms	320 KB	Output is correct
2	Correct	410 ms	340 KB	Output is correct
3	Correct	293 ms	320 KB	Output is correct
4	Correct	1698 ms	316 KB	Output is correct
5	Correct	1627 ms	320 KB	Output is correct
6	Correct	1102 ms	320 KB	Output is correct
7	Correct	289 ms	340 KB	Output is correct
8	Correct	328 ms	320 KB	Output is correct
9	Correct	1943 ms	320 KB	Output is correct
10	Correct	1745 ms	316 KB	Output is correct

Subtask #2

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	682 ms	320 KB	Output is correct
2	Correct	410 ms	340 KB	Output is correct
3	Correct	293 ms	320 KB	Output is correct
4	Correct	1698 ms	316 KB	Output is correct
5	Correct	1627 ms	320 KB	Output is correct
6	Correct	1102 ms	320 KB	Output is correct
7	Correct	289 ms	340 KB	Output is correct
8	Correct	328 ms	320 KB	Output is correct
9	Correct	1943 ms	320 KB	Output is correct
10	Correct	1745 ms	316 KB	Output is correct
11	Correct	1677 ms	324 KB	Output is correct
12	Incorrect	1690 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	682 ms	320 KB	Output is correct
2	Correct	410 ms	340 KB	Output is correct
3	Correct	293 ms	320 KB	Output is correct
4	Correct	1698 ms	316 KB	Output is correct
5	Correct	1627 ms	320 KB	Output is correct
6	Correct	1102 ms	320 KB	Output is correct
7	Correct	289 ms	340 KB	Output is correct
8	Correct	328 ms	320 KB	Output is correct
9	Correct	1943 ms	320 KB	Output is correct
10	Correct	1745 ms	316 KB	Output is correct
11	Correct	1677 ms	324 KB	Output is correct
12	Incorrect	1690 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	682 ms	320 KB	Output is correct
2	Correct	410 ms	340 KB	Output is correct
3	Correct	293 ms	320 KB	Output is correct
4	Correct	1698 ms	316 KB	Output is correct
5	Correct	1627 ms	320 KB	Output is correct
6	Correct	1102 ms	320 KB	Output is correct
7	Correct	289 ms	340 KB	Output is correct
8	Correct	328 ms	320 KB	Output is correct
9	Correct	1943 ms	320 KB	Output is correct
10	Correct	1745 ms	316 KB	Output is correct
11	Correct	1677 ms	324 KB	Output is correct
12	Incorrect	1690 ms	320 KB	Output isn't correct
13	Halted	0 ms	0 KB	-