Submission #1122487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122487		Math4Life2020	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	0 / 100	5095 ms	36924 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> qry0(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++) {
		//cout << "i="<<i<<"\n";
		if (bmax[i]==(-INF)) {
			invarr.push_back({0,i});
			//cout << 0 <<","<<i<<"\n";
		} else {
			invarr.push_back({0LL,i-bmax[i]-1});
			//cout << 0 <<","<<i-bmax[i]-1<<"\n";
			invarr.push_back({max(0LL,i+1-bmin[i]),min(i,1+jmax[i])});
			//cout << max(0LL,i+1-bmin[i]) <<","<<min(i,1+jmax[i])<<"\n";
			if (((i-1-jmax[i])<bmin[i]) || ((i-1-jmax[i])>bmax[i])) {
				invarr.push_back({2+jmax[i],i});
				//cout << 2+jmax[i] <<","<<i<<"\n";
			}
		}
		//cout << "\n";
	}
	if (bmax[N]==(-INF)) {
		invarr.push_back({1,N});
	}
	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);
	}

	bool endt = 1;
	for (ll i=0;i<N;i++) {
		endt = endt && (abs(a[i+N]-b[N-1-i])<=ans);
	}
	vans.push_back(endt);
	return vans;
}

vector<bool> qry(ll ans) {
	vector<bool> q1 = qry0(ans);
	vector<ll> reva(2*N+1,0);
	reva[0]=-INF/2;
	for (ll i=0;i<(2*N);i++) {
		reva[i+1]=a[2*N-1-i];
	}
	vector<ll> acopy = a;
	a = reva;
	vector<bool> q2 = qry0(ans);
	// cout << "ans="<<ans<<"\n";
	// for (ll x: q2) {
	// 	cout << "q2: "<<x<<"\n";
	// }
	a = acopy;
	vector<bool> qf;
	qf.push_back(q1[0]);
	q1[N-1]=1;
	for (ll i=1;i<N;i++) {
		qf.push_back(q1[i] && q2[N+1-i]);
	}
	return qf;
}

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);
	// for (auto x: a) {
	// 	cout << x<<"\n";
	// }
	// vector<bool> b1 = qry(3); 
	// for (ll x: b1) {
	// 	cout << x << " in b1 \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: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 21
• Subtask 4: 0 / 37
• Subtask 5: 0 / 33