Submission #802077

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802077	2023-08-02T09:33:24 Z	fatemetmhr	Giraffes (JOI22_giraffes)	C++17	32 / 100	5486 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;
	}
	ll tt = 100000000;
	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	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	3579 ms	312 KB	Output is correct
5	Correct	3913 ms	316 KB	Output is correct
6	Correct	3941 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	4383 ms	320 KB	Output is correct
10	Correct	4293 ms	312 KB	Output is correct

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	3579 ms	312 KB	Output is correct
5	Correct	3913 ms	316 KB	Output is correct
6	Correct	3941 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	4383 ms	320 KB	Output is correct
10	Correct	4293 ms	312 KB	Output is correct
11	Correct	4533 ms	316 KB	Output is correct
12	Correct	4589 ms	316 KB	Output is correct
13	Correct	4400 ms	316 KB	Output is correct
14	Correct	4886 ms	316 KB	Output is correct
15	Correct	4926 ms	316 KB	Output is correct
16	Correct	4830 ms	316 KB	Output is correct
17	Correct	4917 ms	320 KB	Output is correct
18	Correct	4888 ms	312 KB	Output is correct
19	Correct	5038 ms	312 KB	Output is correct
20	Correct	5057 ms	316 KB	Output is correct

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	3579 ms	312 KB	Output is correct
5	Correct	3913 ms	316 KB	Output is correct
6	Correct	3941 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	4383 ms	320 KB	Output is correct
10	Correct	4293 ms	312 KB	Output is correct
11	Correct	4533 ms	316 KB	Output is correct
12	Correct	4589 ms	316 KB	Output is correct
13	Correct	4400 ms	316 KB	Output is correct
14	Correct	4886 ms	316 KB	Output is correct
15	Correct	4926 ms	316 KB	Output is correct
16	Correct	4830 ms	316 KB	Output is correct
17	Correct	4917 ms	320 KB	Output is correct
18	Correct	4888 ms	312 KB	Output is correct
19	Correct	5038 ms	312 KB	Output is correct
20	Correct	5057 ms	316 KB	Output is correct
21	Correct	5486 ms	312 KB	Output is correct
22	Incorrect	5076 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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	3579 ms	312 KB	Output is correct
5	Correct	3913 ms	316 KB	Output is correct
6	Correct	3941 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	4383 ms	320 KB	Output is correct
10	Correct	4293 ms	312 KB	Output is correct
11	Correct	4533 ms	316 KB	Output is correct
12	Correct	4589 ms	316 KB	Output is correct
13	Correct	4400 ms	316 KB	Output is correct
14	Correct	4886 ms	316 KB	Output is correct
15	Correct	4926 ms	316 KB	Output is correct
16	Correct	4830 ms	316 KB	Output is correct
17	Correct	4917 ms	320 KB	Output is correct
18	Correct	4888 ms	312 KB	Output is correct
19	Correct	5038 ms	312 KB	Output is correct
20	Correct	5057 ms	316 KB	Output is correct
21	Correct	5486 ms	312 KB	Output is correct
22	Incorrect	5076 ms	320 KB	Output isn't correct
23	Halted	0 ms	0 KB	-