제출 #1122456

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122456		Math4Life2020	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	9 / 100	5094 ms	49900 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>; 
const ll INF = 2e18;

vector<ll> a,fa,b,nb,c,nc;
ll N; 

vector<bool> qry(ll ans) { //for which of the N shifts is it valid?
	//cout << "querying ans = "<<ans<<"\n";
	vector<bool> vans(N,false); //return this if none work
	//checking "a" against "b"
	vector<pii> invarr;
	ll jmax[N];
	ll bmin[2*N];
	ll bmax[2*N];
	for (ll i=0;i<N;i++) {
		jmax[i]=-INF;
		for (ll j=0;j<N;j++) {
			if (a[j+N]>=a[i]) { //j=0 always works -> defined.
				jmax[i]=max(jmax[i],j);
			}
		}
	}
	for (ll i=0;i<(2*N);i++) {
		bmin[i]=INF;
		bmax[i]=-INF;
		for (ll j=0;j<N;j++) {
			if (abs(a[i]-b[j])<=ans) {
				bmin[i]=min(j,bmin[i]);
				bmax[i]=max(j,bmax[i]);
			}
		}
	}

	for (ll i=0;i<N;i++) {
		if (bmax[i]==(-INF)) {
			invarr.push_back({0,i});
		} else {
			invarr.push_back({0LL,i-bmax[i]-1});
			invarr.push_back({max(0LL,i+1-bmin[i]),min(i,1+jmax[i])});
			if (((i-1-jmax[i])<bmin[i]) || ((i-1-jmax[i])>bmax[i])) {
				invarr.push_back({2+jmax[i],i});
			}
		}
	}
	for (pii p0: invarr) {
		//cout << "invarr: "<<p0.first<<","<<p0.second<<"\n";
	}

	// for (ll i=0;i<N;i++) {
	// 	ll bind = i;
	// 	for (ll t=0;t<=i;t++) {
	// 		if (t>0) {
	// 			ll j=t-1;
	// 			if (a[j+N]>=a[i]) {
	// 				bind--;
	// 			}
	// 		}
	// 		if (abs(a[i]-b[bind])>ans) {
	// 			invarr.push_back({t,t});
	// 			cout << "true pbk: t="<<t<<"\n";
	// 		}
	// 	}
	// }

	for (ll i=0;i<N;i++) {
		ll bind = 0;
		for (ll j=(i+1);j<N;j++) {
			if (a[j]<=a[i+N]) {
				bind++;
			}
		}
		for (ll t=(i+1);t<N;t++) {
			if (t>(i+1)) {
				ll j=t-1;
				if (a[j]>a[i+N]) {
					bind++;
				}
			}
			if (abs(a[i+N]-b[bind])>ans) {
				invarr.push_back({t,t});
			}
		}
	}
	vector<ll> pfsv(N+5,0);
	for (pii p0: invarr) {
		ll x = p0.first; ll y = p0.second;
		if (x>y || (x>=(N+5))) {
			continue;
		}
		pfsv[x]++;
		if (y<=(N+1)) {
			pfsv[y+1]--;
		}
	}
	ll cv = 0;
	for (ll i=0;i<N;i++) {
		cv += pfsv[i];
		vans[i]=(cv==0);
	}
	return vans;
}

ll process() {
	ll ansmin = 0;
	ll ansmax = 2e9;
	while (ansmin!=ansmax) {
		ll anst = (ansmin+ansmax)/2;
		vector<bool> p1 = qry(anst);
		swap(a,fa);
		swap(b,nc);
		vector<bool> p2 = qry(anst);
		swap(a,fa);
		swap(b,nc);
		bool ansv = 0;
		for (ll i=0;i<N;i++) {
			if (p1[i] && p2[i]) {
				ansv = 1;
			}
		}
		if (ansv) { //aka you can do it
			ansmax = anst;
		} else {
			ansmin = anst+1;
		}
	}
	assert(ansmin <= ansmax);
	return ansmin;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> N;
	ll ans = INF;
	for (ll i=0;i<(2*N);i++) {
		ll x; cin >> x;
		a.push_back(x);
		fa.push_back(-1);
	}
	for (ll i=0;i<(2*N);i++) {
		fa[i]=-a[(i+N)%(2*N)];
	}
	for (ll i=0;i<N;i++) {
		ll x; cin >> x;
		b.push_back(x);
	}
	for (ll i=0;i<N;i++) {
		ll x; cin >> x;
		c.push_back(x);
	}
	sort(b.begin(),b.end());
	sort(c.begin(),c.end());
	for (ll i=0;i<N;i++) {
		nb.push_back(-b[i]);
		nc.push_back(-c[i]);
	}
	sort(nb.begin(),nb.end());
	sort(nc.begin(),nc.end());


	// swap(a,fa);
	// swap(b,nc);
	// vector<bool> b1 = qry(8); 
	// for (auto x: b1) {
	// 	cout << x<<"\n";
	// }
	// exit(0);

	ans = min(ans,process());
	//cout << "ans0="<<ans<<"\n";
	swap(b,c);
	swap(nb,nc);
	ans = min(ans,process());
	cout << ans <<"\n";
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 37
• Subtask 5: 0 / 33