Submission #802065

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802065	2023-08-02T09:29:18 Z	fatemetmhr	Giraffes (JOI22_giraffes)	C++17	32 / 100	548 ms	340 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 chpt = 0;
int cur = 0;
int l = 0, r;
int ptl = 0, ptr;
int n;

struct tagh{
	bool ty1, ty2, rem1, rem2;
	int ll, rr, ptll, ptrr;
	tagh(bool a, bool b, bool c, bool d, int x, int y, int z, int w){
		ty1 = a;
		ty2 = b;
		rem1 = c;
		rem2 = d;
		ll = x;
		rr = y;
		ptll = z;
		ptrr = w;
	}

	void undo(){
		if(!rem1)
			cur--;
		if(!rem2)
			cur--;
		ptl = ptll;
		ptr = ptrr;
		l = ll;
		r = rr;
		if(ty1){
			rem[ind[ptl]] = rem1;
		}
		else{
			rem[ind[ptr]] = rem1;
		}
		if(ty2){
			rem[l] = rem2;
		}
		else{
			rem[r] = rem2;
		}
	}
};
vector <tagh> ch;

void random_er(){
	//cout << "change " << endl;
	if(ch.empty())
		return;
	int keep = rng() % int(ch.size());
	if(rng() % (7 * n) == 0)
		keep = 0;
	while(ch.size() > keep){
		ch.back().undo();
		ch.pop_back();
	}
}


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

	cin >> n;
	r = ptr = n - 1;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		a[i]--;
		ind[a[i]] = i;
	}
	int tt = 10000000;
	int ans = n;

	while(l <= r){
		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;
		}
		break;
	}
	if(l > r)
		return cout << 0 << endl, 0;
	while(tt--){
		while(l <= r){
			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;
			}
			break;
		}
		if(l > r){
			ans = min(ans, cur);
			random_er();
			continue;
		}
		if(tt < 1e6 && rng() % int(1e6 - tt) == 0){
			random_er();
			continue;
		}
		int ty1 = rng() % 2, ty2 = rng() % 2;
		//cout << "in " << tt << ' ' << ptl << ' ' << ptr << ' ' << l << ' ' << r << ' ' << ty1 << ' ' << ty2 << ' ' << cur << endl;
		ch.emplace_back(ty1, ty2, rem[ind[(ty1 ? ptl : ptr)]], rem[ty2 ? l : r], l, r, ptl, ptr);
		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--;
		}
	}
	cout << ans << endl;
}

Compilation message

giraffes.cpp: In function 'void random_er()':
giraffes.cpp:75:18: warning: comparison of integer expressions of different signedness: 'std::vector<tagh>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |  while(ch.size() > keep){
      |        ~~~~~~~~~~^~~~~~

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	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	368 ms	320 KB	Output is correct
5	Correct	392 ms	316 KB	Output is correct
6	Correct	413 ms	316 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	446 ms	316 KB	Output is correct
10	Correct	416 ms	312 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	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	368 ms	320 KB	Output is correct
5	Correct	392 ms	316 KB	Output is correct
6	Correct	413 ms	316 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	446 ms	316 KB	Output is correct
10	Correct	416 ms	312 KB	Output is correct
11	Correct	462 ms	320 KB	Output is correct
12	Correct	460 ms	320 KB	Output is correct
13	Correct	428 ms	212 KB	Output is correct
14	Correct	479 ms	316 KB	Output is correct
15	Correct	504 ms	312 KB	Output is correct
16	Correct	477 ms	320 KB	Output is correct
17	Correct	494 ms	316 KB	Output is correct
18	Correct	486 ms	312 KB	Output is correct
19	Correct	500 ms	316 KB	Output is correct
20	Correct	499 ms	316 KB	Output is correct

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	368 ms	320 KB	Output is correct
5	Correct	392 ms	316 KB	Output is correct
6	Correct	413 ms	316 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	446 ms	316 KB	Output is correct
10	Correct	416 ms	312 KB	Output is correct
11	Correct	462 ms	320 KB	Output is correct
12	Correct	460 ms	320 KB	Output is correct
13	Correct	428 ms	212 KB	Output is correct
14	Correct	479 ms	316 KB	Output is correct
15	Correct	504 ms	312 KB	Output is correct
16	Correct	477 ms	320 KB	Output is correct
17	Correct	494 ms	316 KB	Output is correct
18	Correct	486 ms	312 KB	Output is correct
19	Correct	500 ms	316 KB	Output is correct
20	Correct	499 ms	316 KB	Output is correct
21	Incorrect	548 ms	312 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #4

0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	368 ms	320 KB	Output is correct
5	Correct	392 ms	316 KB	Output is correct
6	Correct	413 ms	316 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	446 ms	316 KB	Output is correct
10	Correct	416 ms	312 KB	Output is correct
11	Correct	462 ms	320 KB	Output is correct
12	Correct	460 ms	320 KB	Output is correct
13	Correct	428 ms	212 KB	Output is correct
14	Correct	479 ms	316 KB	Output is correct
15	Correct	504 ms	312 KB	Output is correct
16	Correct	477 ms	320 KB	Output is correct
17	Correct	494 ms	316 KB	Output is correct
18	Correct	486 ms	312 KB	Output is correct
19	Correct	500 ms	316 KB	Output is correct
20	Correct	499 ms	316 KB	Output is correct
21	Incorrect	548 ms	312 KB	Output isn't correct
22	Halted	0 ms	0 KB	-