Submission #801949

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
801949	2023-08-02T08:39:17 Z	Sohsoh84	Giraffes (JOI22_giraffes)	C++17	10 / 100	379 ms	348 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];

inline void rand_perm() {
	int l = 1, r = n;
	int fl = 1, fr = n;
	for (int i = 1; i <= n; i++) {
		int x = (rng() % 2 ? fr-- : fl++);
		int y = (rng() % 2 ? r-- : l++);
		T[y] = x;
	}
}

inline int distance() {
	for (int i = 1; i <= n; i++)
		ind[P[i]] = i;

	for (int i = 1; i <= n; i++)
		F[ind[T[i]]] = i;

	int ans = 0;
	for (int i = 1; i <= n; i++)
		if (F[i] != i)
			ans++;
	
	return ans;
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int fuck = 1000000;
	
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> P[i];

	int ans = n;
	while (fuck--) {
		rand_perm();
		ans = min(ans, distance());
	}

	cout << ans << endl;
	return 0;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	340 KB	Output is correct
2	Correct	59 ms	340 KB	Output is correct
3	Correct	96 ms	348 KB	Output is correct
4	Correct	129 ms	340 KB	Output is correct
5	Correct	153 ms	340 KB	Output is correct
6	Correct	198 ms	340 KB	Output is correct
7	Correct	188 ms	340 KB	Output is correct
8	Correct	209 ms	340 KB	Output is correct
9	Correct	214 ms	340 KB	Output is correct
10	Correct	211 ms	340 KB	Output is correct

Subtask #2

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	340 KB	Output is correct
2	Correct	59 ms	340 KB	Output is correct
3	Correct	96 ms	348 KB	Output is correct
4	Correct	129 ms	340 KB	Output is correct
5	Correct	153 ms	340 KB	Output is correct
6	Correct	198 ms	340 KB	Output is correct
7	Correct	188 ms	340 KB	Output is correct
8	Correct	209 ms	340 KB	Output is correct
9	Correct	214 ms	340 KB	Output is correct
10	Correct	211 ms	340 KB	Output is correct
11	Correct	235 ms	340 KB	Output is correct
12	Correct	285 ms	340 KB	Output is correct
13	Correct	292 ms	340 KB	Output is correct
14	Correct	320 ms	340 KB	Output is correct
15	Correct	347 ms	340 KB	Output is correct
16	Correct	344 ms	344 KB	Output is correct
17	Correct	373 ms	336 KB	Output is correct
18	Correct	371 ms	340 KB	Output is correct
19	Incorrect	379 ms	344 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	340 KB	Output is correct
2	Correct	59 ms	340 KB	Output is correct
3	Correct	96 ms	348 KB	Output is correct
4	Correct	129 ms	340 KB	Output is correct
5	Correct	153 ms	340 KB	Output is correct
6	Correct	198 ms	340 KB	Output is correct
7	Correct	188 ms	340 KB	Output is correct
8	Correct	209 ms	340 KB	Output is correct
9	Correct	214 ms	340 KB	Output is correct
10	Correct	211 ms	340 KB	Output is correct
11	Correct	235 ms	340 KB	Output is correct
12	Correct	285 ms	340 KB	Output is correct
13	Correct	292 ms	340 KB	Output is correct
14	Correct	320 ms	340 KB	Output is correct
15	Correct	347 ms	340 KB	Output is correct
16	Correct	344 ms	344 KB	Output is correct
17	Correct	373 ms	336 KB	Output is correct
18	Correct	371 ms	340 KB	Output is correct
19	Incorrect	379 ms	344 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

Subtask #4

0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	340 KB	Output is correct
2	Correct	59 ms	340 KB	Output is correct
3	Correct	96 ms	348 KB	Output is correct
4	Correct	129 ms	340 KB	Output is correct
5	Correct	153 ms	340 KB	Output is correct
6	Correct	198 ms	340 KB	Output is correct
7	Correct	188 ms	340 KB	Output is correct
8	Correct	209 ms	340 KB	Output is correct
9	Correct	214 ms	340 KB	Output is correct
10	Correct	211 ms	340 KB	Output is correct
11	Correct	235 ms	340 KB	Output is correct
12	Correct	285 ms	340 KB	Output is correct
13	Correct	292 ms	340 KB	Output is correct
14	Correct	320 ms	340 KB	Output is correct
15	Correct	347 ms	340 KB	Output is correct
16	Correct	344 ms	344 KB	Output is correct
17	Correct	373 ms	336 KB	Output is correct
18	Correct	371 ms	340 KB	Output is correct
19	Incorrect	379 ms	344 KB	Output isn't correct
20	Halted	0 ms	0 KB	-