Submission #1173323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173323		Troll321	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	0 / 100	3769 ms	14524 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 6e5 + 5; 
const ll MAX = 1e18;
const ll MAXBINSER = 1e9;

ll n, ntot, ans = MAX, val[MAXN], red[MAXN], blue[MAXN];

ll diff[MAXN];
bool solve(ll x, ll arra[], ll arrb[]) {
	memset(diff, 0, sizeof(diff));

	// l <= N
	for (ll i = 1; i <= ntot; ++i) {
		// Search Range For val[i]
		ll idl = lower_bound(arra+1, arra+1+n, val[i]-x) - arra;
		ll idr = upper_bound(arra+1, arra+1+n, val[i]+x) - arra;
		if(idl > n || idr == 1 || idl > idr) {
			idl = -1;
			idr = -1;
		}
		idr--;

		ll idl2 = lower_bound(arrb+1, arrb+1+n, val[i]-x) - arrb;
		ll idr2 = upper_bound(arrb+1, arrb+1+n, val[i]+x) - arrb;
		if(idl2 > n || idr2 == 1 || idl2 > idr2) {
			idl2 = -1;
			idr2 = -1;
		}
		idr2--;

		// cout << i << " " << x << "| [" << idl << "," << idr << "] [" << idl2 << "," << idr2 << "]\n";

		ll l, r;
		if (i <= n) {
			// In
			if(idl != -1) {
				l = max((ll)1, i+1-idr);
				r = min(i, i+1-idl)+1;
				diff[l]++;
				diff[r]--;
				// cout << l << " " << r << " <> ";
			}


			// Out
			if(idl2 != -1) {
				if(abs(val[i]-arrb[i]) <= x) {
					l = i+1;
					r = n+1;
					diff[l]++;
					diff[r]--;
					// cout << l << " " << r << "|\n";
				}
			}
		} else {
			// In
			if(idl != -1) {
				if(abs(val[i]-arra[ntot-i+1]) <= x) {
					l = i-n+1;
					r = n+1;
					diff[l]++;
					diff[r]--;
					// cout << l << " " << r << " <> ";
				}
			}

			// Out
			if(idl2 != -1) {
				l = max((ll)1, idl2+i-ntot);
				r = min(i-n, idr2+i-ntot)+1;
				diff[l]++;
				diff[r]--;
				// cout << l << " " << r << "|\n";
			}
		}
	}

	// ------
	ll cur = 0;
	for (int i = 1; i <= ntot; ++i) {
		cur += diff[i];
		if(cur > ntot) {cout << 1/0;}
		if(cur == ntot) {return true;}
	}
	return false;
}

int main() {
	cin >> n;
	ntot = 2*n;

	ll tmpmax = 0;
	for (int i = 1; i <= ntot; ++i) {
		cin >> val[i];
		tmpmax = max(tmpmax, val[i]);
	}

	for (int i = 1; i <= n; ++i) {
		cin >> red[i];
	}

	for (int i = 1; i <= n; ++i) {
		cin >> blue[i];
	}

	sort(red+1, red+1+n);
	sort(blue+1, blue+1+n);

	// for (int i = 1; i <= n; ++i) {
	// 	cout << red[i] << " ";
	// } cout << "|\n";
	// for (int i = 1; i <= n; ++i) {
	// 	cout << blue[i] << " ";
	// } cout << "|\n";

	ll l = 0, r = tmpmax+1;
	while(l <= r) {
		ll mid = (l+r) >> 1;
		// cout << "---------" << mid << "--------\n";
		if(solve(mid, red, blue) || solve(mid, blue, red)) {
			ans = mid;
			r = mid-1;
		} else {
			l = mid+1;
		}
	}
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'bool solve(ll, ll*, ll*)':
Main.cpp:84:42: warning: division by zero [-Wdiv-by-zero]
   84 |                 if(cur > ntot) {cout << 1/0;}
      |                                         ~^~

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