Submission #801995

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
801995	2023-08-02T08:58:10 Z	fatemetmhr	Giraffes (JOI22_giraffes)	C++17	32 / 100	210 ms	344 KB

giraffes

// Be name khode //


#include <bits/stdc++.h>

using namespace std;

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

typedef long long ll;
typedef long double ld;

#define all(x) x.begin(), x.end()
#define mp     make_pair
#define pb     push_back
#define fi     first
#define se     second

const int maxn5 = 8e3 + 5;

int a[maxn5], ind[maxn5];
bool rem[maxn5];


int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	int n; cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		a[i]--;
		ind[a[i]] = i;
	}
	int tt = 80000;
	int ans = n;
	while(tt--){
		int l = 0, r = n - 1;
		int ptl = 0, ptr = n - 1;
		int cur = 0;
		memset(rem, false, sizeof rem);
		for(int x = 0; x < n; x++){
			if(ind[ptl] == l && !rem[l]){
				ptl++;
				l++;
				continue;
			}
			if(ind[ptl] == r && !rem[r]){
				ptl++;
				r--;
				continue;
			}
			if(ind[ptr] == l && !rem[l]){
				ptr--;
				l++;
				continue;
			}
			if(ind[ptr] == r && !rem[r]){
				ptr--;
				r--;
				continue;
			}
			int ty1 = rng() % 2, ty2 = rng() % 2;
			//cout << "in " << tt << ' ' << ptl << ' ' << ptr << ' ' << l << ' ' << r << ' ' << ty1 << ' ' << ty2 << endl;
			if(ty1){
				if(!rem[ind[ptl]])
					cur++;
				rem[ind[ptl]] = true;
				ptl++;
			}
			else{
				if(!rem[ind[ptr]])
					cur++;
				rem[ind[ptr]] = true;
				ptr--;
			}
			if(ty2){
				if(!rem[l])
					cur++;
				rem[l] = true;
				l++;
			}
			else{
				if(!rem[r])
					cur++;
				rem[r] = true;
				r--;
			}
		}
		ans = min(ans, cur);
	}
	cout << ans << endl;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	340 KB	Output is correct
2	Correct	8 ms	212 KB	Output is correct
3	Correct	10 ms	340 KB	Output is correct
4	Correct	13 ms	340 KB	Output is correct
5	Correct	15 ms	336 KB	Output is correct
6	Correct	18 ms	344 KB	Output is correct
7	Correct	8 ms	340 KB	Output is correct
8	Correct	9 ms	340 KB	Output is correct
9	Correct	19 ms	212 KB	Output is correct
10	Correct	18 ms	340 KB	Output is correct

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	340 KB	Output is correct
2	Correct	8 ms	212 KB	Output is correct
3	Correct	10 ms	340 KB	Output is correct
4	Correct	13 ms	340 KB	Output is correct
5	Correct	15 ms	336 KB	Output is correct
6	Correct	18 ms	344 KB	Output is correct
7	Correct	8 ms	340 KB	Output is correct
8	Correct	9 ms	340 KB	Output is correct
9	Correct	19 ms	212 KB	Output is correct
10	Correct	18 ms	340 KB	Output is correct
11	Correct	23 ms	340 KB	Output is correct
12	Correct	23 ms	212 KB	Output is correct
13	Correct	19 ms	344 KB	Output is correct
14	Correct	28 ms	340 KB	Output is correct
15	Correct	30 ms	212 KB	Output is correct
16	Correct	30 ms	212 KB	Output is correct
17	Correct	33 ms	316 KB	Output is correct
18	Correct	32 ms	212 KB	Output is correct
19	Correct	32 ms	336 KB	Output is correct
20	Correct	31 ms	340 KB	Output is correct

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	340 KB	Output is correct
2	Correct	8 ms	212 KB	Output is correct
3	Correct	10 ms	340 KB	Output is correct
4	Correct	13 ms	340 KB	Output is correct
5	Correct	15 ms	336 KB	Output is correct
6	Correct	18 ms	344 KB	Output is correct
7	Correct	8 ms	340 KB	Output is correct
8	Correct	9 ms	340 KB	Output is correct
9	Correct	19 ms	212 KB	Output is correct
10	Correct	18 ms	340 KB	Output is correct
11	Correct	23 ms	340 KB	Output is correct
12	Correct	23 ms	212 KB	Output is correct
13	Correct	19 ms	344 KB	Output is correct
14	Correct	28 ms	340 KB	Output is correct
15	Correct	30 ms	212 KB	Output is correct
16	Correct	30 ms	212 KB	Output is correct
17	Correct	33 ms	316 KB	Output is correct
18	Correct	32 ms	212 KB	Output is correct
19	Correct	32 ms	336 KB	Output is correct
20	Correct	31 ms	340 KB	Output is correct
21	Correct	65 ms	320 KB	Output is correct
22	Incorrect	210 ms	320 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #4

0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	340 KB	Output is correct
2	Correct	8 ms	212 KB	Output is correct
3	Correct	10 ms	340 KB	Output is correct
4	Correct	13 ms	340 KB	Output is correct
5	Correct	15 ms	336 KB	Output is correct
6	Correct	18 ms	344 KB	Output is correct
7	Correct	8 ms	340 KB	Output is correct
8	Correct	9 ms	340 KB	Output is correct
9	Correct	19 ms	212 KB	Output is correct
10	Correct	18 ms	340 KB	Output is correct
11	Correct	23 ms	340 KB	Output is correct
12	Correct	23 ms	212 KB	Output is correct
13	Correct	19 ms	344 KB	Output is correct
14	Correct	28 ms	340 KB	Output is correct
15	Correct	30 ms	212 KB	Output is correct
16	Correct	30 ms	212 KB	Output is correct
17	Correct	33 ms	316 KB	Output is correct
18	Correct	32 ms	212 KB	Output is correct
19	Correct	32 ms	336 KB	Output is correct
20	Correct	31 ms	340 KB	Output is correct
21	Correct	65 ms	320 KB	Output is correct
22	Incorrect	210 ms	320 KB	Output isn't correct
23	Halted	0 ms	0 KB	-