Submission #1122439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122439		Math4Life2020	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	9 / 100	5093 ms	66596 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]);
			}
		}
		// if (bmin[i]==INF) {
		// 	cout << "f1\n";
		// 	cout << "i="<<i<<", a[i]="<<a[i]<<"\n";
		// 	cout << "b: \n";
		// 	for (ll i=0;i<N;i++) {
		// 		cout << b[i] <<" ";
		// 	}
		// 	cout << "\n";
		// 	//return vans;
		// }
	}

	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});
			}
		}
	}
	// for (ll i=0;i<N;i++) {
	// 	invarr.push_back({0,i-bmax[i]-1});
	// 	invarr.push_back({i+1-bmin[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});
			}
		}
	}

	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) {
		// 	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());
	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