Submission #1122436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122436		Math4Life2020	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	9 / 100	5093 ms	66388 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?
	vector<bool> vans(N,false); //return this if none work
	//checking "a" against "b"
	vector<pii> invarr;
	for (ll i=0;i<N;i++) {
		//cout << "process i="<<i<<"\n";
		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 << "t="<<t<<" invalid \n";
			}
		}
	}
	for (ll i=0;i<N;i++) {
		//cout << "process i+N="<<(i+N)<<"\n";
		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});
				//cout << "t="<<t<<" invalid \n";
			}
		}
	}
	vector<ll> pfsv(N+5,0);
	for (pii p0: invarr) {
		ll x = p0.first; ll y = p0.second;
		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);
		//nb.push_back(-x);
	}
	for (ll i=0;i<N;i++) {
		ll x; cin >> x;
		c.push_back(x);
		//nc.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(4);
	// for (ll x: b1) {
	// 	cout << x<<" ";
	// }
	// exit(0);

	ans = min(ans,process());
	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