Submission #802077

#	Time	Username	Problem	Language	Result	Execution time	Memory
802077		fatemetmhr	Giraffes (JOI22_giraffes)	C++17	32 / 100	5486 ms	340 KiB

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 (stderr)

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 / 10
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 41