Submission #802075

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
802075	2023-08-02T09:32:48 Z	fatemetmhr	Giraffes (JOI22_giraffes)	C++17	32 / 100	527 ms	384 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	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	389 ms	320 KB	Output is correct
5	Correct	393 ms	332 KB	Output is correct
6	Correct	413 ms	320 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	216 KB	Output is correct
9	Correct	442 ms	336 KB	Output is correct
10	Correct	430 ms	316 KB	Output is correct

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	389 ms	320 KB	Output is correct
5	Correct	393 ms	332 KB	Output is correct
6	Correct	413 ms	320 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	216 KB	Output is correct
9	Correct	442 ms	336 KB	Output is correct
10	Correct	430 ms	316 KB	Output is correct
11	Correct	460 ms	384 KB	Output is correct
12	Correct	483 ms	328 KB	Output is correct
13	Correct	448 ms	316 KB	Output is correct
14	Correct	514 ms	340 KB	Output is correct
15	Correct	503 ms	212 KB	Output is correct
16	Correct	484 ms	212 KB	Output is correct
17	Correct	488 ms	316 KB	Output is correct
18	Correct	488 ms	320 KB	Output is correct
19	Correct	503 ms	340 KB	Output is correct
20	Correct	518 ms	320 KB	Output is correct

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	389 ms	320 KB	Output is correct
5	Correct	393 ms	332 KB	Output is correct
6	Correct	413 ms	320 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	216 KB	Output is correct
9	Correct	442 ms	336 KB	Output is correct
10	Correct	430 ms	316 KB	Output is correct
11	Correct	460 ms	384 KB	Output is correct
12	Correct	483 ms	328 KB	Output is correct
13	Correct	448 ms	316 KB	Output is correct
14	Correct	514 ms	340 KB	Output is correct
15	Correct	503 ms	212 KB	Output is correct
16	Correct	484 ms	212 KB	Output is correct
17	Correct	488 ms	316 KB	Output is correct
18	Correct	488 ms	320 KB	Output is correct
19	Correct	503 ms	340 KB	Output is correct
20	Correct	518 ms	320 KB	Output is correct
21	Correct	527 ms	320 KB	Output is correct
22	Incorrect	501 ms	340 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #4

0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	389 ms	320 KB	Output is correct
5	Correct	393 ms	332 KB	Output is correct
6	Correct	413 ms	320 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	216 KB	Output is correct
9	Correct	442 ms	336 KB	Output is correct
10	Correct	430 ms	316 KB	Output is correct
11	Correct	460 ms	384 KB	Output is correct
12	Correct	483 ms	328 KB	Output is correct
13	Correct	448 ms	316 KB	Output is correct
14	Correct	514 ms	340 KB	Output is correct
15	Correct	503 ms	212 KB	Output is correct
16	Correct	484 ms	212 KB	Output is correct
17	Correct	488 ms	316 KB	Output is correct
18	Correct	488 ms	320 KB	Output is correct
19	Correct	503 ms	340 KB	Output is correct
20	Correct	518 ms	320 KB	Output is correct
21	Correct	527 ms	320 KB	Output is correct
22	Incorrect	501 ms	340 KB	Output isn't correct
23	Halted	0 ms	0 KB	-