Submission #802095

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802095	2023-08-02T09:50:45 Z	Sohsoh84	Giraffes (JOI22_giraffes)	C++17	59 / 100	3559 ms	91532 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 = 500 + 10;
const ll TMAX = 1e6 + 10;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int dp[MAXN][MAXN][MAXN], n, P[TMAX];

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];

	if (n < MAXN) {
		for (int len = 1; len <= n; len++) {
			for (int l = 1; l <= n - len + 1; l++) {
				for (int tl = 1; tl <= n - len + 1; tl++) {
					int r = l + len - 1;
					int tr = tl + len - 1;

					if (P[l] == tl) dp[len][l][tl] = dp[len - 1][l + 1][tl + 1] + 1;
					else if (P[r] == tl) dp[len][l][tl] = dp[len - 1][l][tl + 1] + 1;
					else if (P[l] == tr) dp[len][l][tl] = dp[len - 1][l + 1][tl] + 1;
					else if (P[r] == tr) dp[len][l][tl] = dp[len - 1][l][tl] + 1;
					else dp[len][l][tl] = max({
							dp[len - 1][l][tl], 
							dp[len - 1][l + 1][tl], 
							dp[len - 1][l][tl + 1], 
							dp[len - 1][l + 1][tl + 1]
							});
				}
			}
		}

		cout << n - dp[n][1][1] << endl;
	} else {
		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	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	468 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	1 ms	468 KB	Output is correct
17	Correct	0 ms	468 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	0 ms	468 KB	Output is correct
20	Correct	1 ms	468 KB	Output is correct

Subtask #3
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	468 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	1 ms	468 KB	Output is correct
17	Correct	0 ms	468 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	0 ms	468 KB	Output is correct
20	Correct	1 ms	468 KB	Output is correct
21	Correct	1 ms	1236 KB	Output is correct
22	Correct	5 ms	9940 KB	Output is correct
23	Correct	23 ms	35436 KB	Output is correct
24	Correct	38 ms	59932 KB	Output is correct
25	Correct	55 ms	85064 KB	Output is correct
26	Correct	68 ms	89164 KB	Output is correct
27	Correct	71 ms	89728 KB	Output is correct
28	Correct	69 ms	90336 KB	Output is correct
29	Correct	53 ms	90988 KB	Output is correct
30	Correct	56 ms	91532 KB	Output is correct

Subtask #4
0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	0 ms	468 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	1 ms	468 KB	Output is correct
16	Correct	1 ms	468 KB	Output is correct
17	Correct	0 ms	468 KB	Output is correct
18	Correct	1 ms	468 KB	Output is correct
19	Correct	0 ms	468 KB	Output is correct
20	Correct	1 ms	468 KB	Output is correct
21	Correct	1 ms	1236 KB	Output is correct
22	Correct	5 ms	9940 KB	Output is correct
23	Correct	23 ms	35436 KB	Output is correct
24	Correct	38 ms	59932 KB	Output is correct
25	Correct	55 ms	85064 KB	Output is correct
26	Correct	68 ms	89164 KB	Output is correct
27	Correct	71 ms	89728 KB	Output is correct
28	Correct	69 ms	90336 KB	Output is correct
29	Correct	53 ms	90988 KB	Output is correct
30	Correct	56 ms	91532 KB	Output is correct
31	Incorrect	3559 ms	340 KB	Output isn't correct
32	Halted	0 ms	0 KB	-

Submission #802095

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 22.0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 0 / 41.0

Subtask #1
10.0 / 10.0

Subtask #2
22.0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
0 / 41.0