oj.uz

Submission #802031

# Submission time Handle Problem Language Result Execution time Memory
802031 2023-08-02T09:11:46 Z Sohsoh84 Giraffes (JOI22_giraffes) C++17
10 / 100
 1881 ms 340 KB 
// 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];

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--;
			else 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];
		ind[P[i]] = 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 217 ms 320 KB Output is correct
2 Correct 178 ms 316 KB Output is correct
3 Correct 136 ms 320 KB Output is correct
4 Correct 1227 ms 320 KB Output is correct
5 Correct 1041 ms 316 KB Output is correct
6 Correct 1006 ms 320 KB Output is correct
7 Correct 157 ms 320 KB Output is correct
8 Correct 177 ms 340 KB Output is correct
9 Correct 1564 ms 332 KB Output is correct
10 Correct 1162 ms 340 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 320 KB Output is correct
2 Correct 178 ms 316 KB Output is correct
3 Correct 136 ms 320 KB Output is correct
4 Correct 1227 ms 320 KB Output is correct
5 Correct 1041 ms 316 KB Output is correct
6 Correct 1006 ms 320 KB Output is correct
7 Correct 157 ms 320 KB Output is correct
8 Correct 177 ms 340 KB Output is correct
9 Correct 1564 ms 332 KB Output is correct
10 Correct 1162 ms 340 KB Output is correct
11 Correct 1479 ms 320 KB Output is correct
12 Correct 1282 ms 340 KB Output is correct
13 Correct 986 ms 340 KB Output is correct
14 Correct 1529 ms 320 KB Output is correct
15 Correct 1647 ms 316 KB Output is correct
16 Correct 1705 ms 316 KB Output is correct
17 Correct 1881 ms 340 KB Output is correct
18 Correct 1734 ms 340 KB Output is correct
19 Incorrect 1863 ms 332 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 320 KB Output is correct
2 Correct 178 ms 316 KB Output is correct
3 Correct 136 ms 320 KB Output is correct
4 Correct 1227 ms 320 KB Output is correct
5 Correct 1041 ms 316 KB Output is correct
6 Correct 1006 ms 320 KB Output is correct
7 Correct 157 ms 320 KB Output is correct
8 Correct 177 ms 340 KB Output is correct
9 Correct 1564 ms 332 KB Output is correct
10 Correct 1162 ms 340 KB Output is correct
11 Correct 1479 ms 320 KB Output is correct
12 Correct 1282 ms 340 KB Output is correct
13 Correct 986 ms 340 KB Output is correct
14 Correct 1529 ms 320 KB Output is correct
15 Correct 1647 ms 316 KB Output is correct
16 Correct 1705 ms 316 KB Output is correct
17 Correct 1881 ms 340 KB Output is correct
18 Correct 1734 ms 340 KB Output is correct
19 Incorrect 1863 ms 332 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 320 KB Output is correct
2 Correct 178 ms 316 KB Output is correct
3 Correct 136 ms 320 KB Output is correct
4 Correct 1227 ms 320 KB Output is correct
5 Correct 1041 ms 316 KB Output is correct
6 Correct 1006 ms 320 KB Output is correct
7 Correct 157 ms 320 KB Output is correct
8 Correct 177 ms 340 KB Output is correct
9 Correct 1564 ms 332 KB Output is correct
10 Correct 1162 ms 340 KB Output is correct
11 Correct 1479 ms 320 KB Output is correct
12 Correct 1282 ms 340 KB Output is correct
13 Correct 986 ms 340 KB Output is correct
14 Correct 1529 ms 320 KB Output is correct
15 Correct 1647 ms 316 KB Output is correct
16 Correct 1705 ms 316 KB Output is correct
17 Correct 1881 ms 340 KB Output is correct
18 Correct 1734 ms 340 KB Output is correct
19 Incorrect 1863 ms 332 KB Output isn't correct
20 Halted 0 ms 0 KB -