답안 #802005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
802005	2023-08-02T09:01:32 Z	Sohsoh84	Giraffes (JOI22_giraffes)	C++17	32 / 100	3127 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--;
			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

#	결과	실행 시간	메모리	Grader output
1	Correct	659 ms	340 KB	Output is correct
2	Correct	413 ms	316 KB	Output is correct
3	Correct	298 ms	320 KB	Output is correct
4	Correct	1770 ms	320 KB	Output is correct
5	Correct	1638 ms	316 KB	Output is correct
6	Correct	1499 ms	316 KB	Output is correct
7	Correct	213 ms	340 KB	Output is correct
8	Correct	227 ms	320 KB	Output is correct
9	Correct	2049 ms	340 KB	Output is correct
10	Correct	1550 ms	320 KB	Output is correct

Subtask #2

22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	659 ms	340 KB	Output is correct
2	Correct	413 ms	316 KB	Output is correct
3	Correct	298 ms	320 KB	Output is correct
4	Correct	1770 ms	320 KB	Output is correct
5	Correct	1638 ms	316 KB	Output is correct
6	Correct	1499 ms	316 KB	Output is correct
7	Correct	213 ms	340 KB	Output is correct
8	Correct	227 ms	320 KB	Output is correct
9	Correct	2049 ms	340 KB	Output is correct
10	Correct	1550 ms	320 KB	Output is correct
11	Correct	1787 ms	316 KB	Output is correct
12	Correct	1819 ms	340 KB	Output is correct
13	Correct	1266 ms	316 KB	Output is correct
14	Correct	2021 ms	340 KB	Output is correct
15	Correct	2340 ms	320 KB	Output is correct
16	Correct	2415 ms	316 KB	Output is correct
17	Correct	2371 ms	340 KB	Output is correct
18	Correct	2455 ms	320 KB	Output is correct
19	Correct	2292 ms	316 KB	Output is correct
20	Correct	2106 ms	316 KB	Output is correct

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	659 ms	340 KB	Output is correct
2	Correct	413 ms	316 KB	Output is correct
3	Correct	298 ms	320 KB	Output is correct
4	Correct	1770 ms	320 KB	Output is correct
5	Correct	1638 ms	316 KB	Output is correct
6	Correct	1499 ms	316 KB	Output is correct
7	Correct	213 ms	340 KB	Output is correct
8	Correct	227 ms	320 KB	Output is correct
9	Correct	2049 ms	340 KB	Output is correct
10	Correct	1550 ms	320 KB	Output is correct
11	Correct	1787 ms	316 KB	Output is correct
12	Correct	1819 ms	340 KB	Output is correct
13	Correct	1266 ms	316 KB	Output is correct
14	Correct	2021 ms	340 KB	Output is correct
15	Correct	2340 ms	320 KB	Output is correct
16	Correct	2415 ms	316 KB	Output is correct
17	Correct	2371 ms	340 KB	Output is correct
18	Correct	2455 ms	320 KB	Output is correct
19	Correct	2292 ms	316 KB	Output is correct
20	Correct	2106 ms	316 KB	Output is correct
21	Correct	2848 ms	320 KB	Output is correct
22	Incorrect	3127 ms	316 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #4

0 / 41.0

#	결과	실행 시간	메모리	Grader output
1	Correct	659 ms	340 KB	Output is correct
2	Correct	413 ms	316 KB	Output is correct
3	Correct	298 ms	320 KB	Output is correct
4	Correct	1770 ms	320 KB	Output is correct
5	Correct	1638 ms	316 KB	Output is correct
6	Correct	1499 ms	316 KB	Output is correct
7	Correct	213 ms	340 KB	Output is correct
8	Correct	227 ms	320 KB	Output is correct
9	Correct	2049 ms	340 KB	Output is correct
10	Correct	1550 ms	320 KB	Output is correct
11	Correct	1787 ms	316 KB	Output is correct
12	Correct	1819 ms	340 KB	Output is correct
13	Correct	1266 ms	316 KB	Output is correct
14	Correct	2021 ms	340 KB	Output is correct
15	Correct	2340 ms	320 KB	Output is correct
16	Correct	2415 ms	316 KB	Output is correct
17	Correct	2371 ms	340 KB	Output is correct
18	Correct	2455 ms	320 KB	Output is correct
19	Correct	2292 ms	316 KB	Output is correct
20	Correct	2106 ms	316 KB	Output is correct
21	Correct	2848 ms	320 KB	Output is correct
22	Incorrect	3127 ms	316 KB	Output isn't correct
23	Halted	0 ms	0 KB	-