제출 #1314680

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1314680		pvpro	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	30 / 100	5095 ms	35112 KiB

Main

#ifndef LOCAL
#pragma GCC Optimize("O3,Ofast,unroll-loops")
#pragma GCC Target("bmi,bmi2,avx,avx2")
#endif
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

#define int ll

#define f first 
#define s second 
#define mp make_pair 
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin() (x).rend()
#ifndef LOCAL
#define endl "\n"
#endif

mt19937 rnd(11);

vector<int> solve(vector<int> &a, vector<int> &b, int x) {
	int n = a.size() / 2;
	bool way;
	auto calc = [&](int i) {
		vector<int> now;
		for (int j = 0; j < n; ++j) {
			now.pb(a[i + j]);
		}
		sort(all(now));
		int ans = 0;
		for (int j = 0; j < n; ++j) {
			ans = max(ans, abs(now[j] - b[j]));
		}
		for (int j = 0; j < n; ++j) {
			if (abs(now[j] - b[j]) == ans) {
				if (now[j] > b[j]) {
					way = true;
				} else {
					way = false;
				}
			}
		}
		return ans;
	};
	int ind = 0;
	for (int i = 1; i < n; ++i) {
		if (a[i - 1] < a[n + i - 1] && a[i] >= a[n + i]) {
			ind = i;
		}
	}
	// for (int i = 0; i < n; ++i) {
	// 	cout << calc(i) << ' ';
	// }
	// cout << endl;
	// cout << ind << endl;
	vector<int> ans(n, 0);
	auto get = [&](int l, int r, bool run, auto &&calc) {
		if (r < l) {
			return;
		}
		int sl = l, sr = r;
		while (r - l > 2) {
			int m1 = (l * 2 + r) / 3;
			int m2 = (l + 2 * r) / 3;
			int cm1 = calc(m1);
			int cm2 = calc(m2);
			if (cm1 < cm2 || (cm1 == cm2 && (way != run))) {
				r = m2;
			} else {
				l = m1;
			}
		}
		int best = -1;
		if (calc(l) <= x) {
			best = l;
		} else if (calc((l + r) / 2) <= x) {
			best = (l + r) / 2;
		} else if (calc(r) <= x) {
			best = r;
		}
		if (best == -1) {
			return;
		}
		int l1 = sl - 1, r1 = best;
		while (r1 - l1 > 1) {
			int m = (l1 + r1) / 2;
			if (calc(m) <= x) {
				r1 = m;
			} else {
				l1 = m;
			}
		}
		for (int i = r1; i <= best; ++i) {
			ans[i] = 1;
		}
		l1 = best, r1 = sr + 1;
		while (r1 - l1 > 1) {
			int m = (l1 + r1) / 2;
			if (calc(m) <= x) {
				l1 = m;
			} else {
				r1 = m;
			}
		}
		for (int i = best; i <= l1; ++i) {
			ans[i] = 1;
		}
	};
	get(0, ind - 1, false, calc);
	get(ind, n - 1, true, calc);
	return ans;
}

void solve() {
    int n;
	cin >> n;
	vector<int> a(n * 2);
	for (auto &x : a) {
		cin >> x;
	}
	vector<int> b(n);
	for (auto &x : b) {
		cin >> x;
	}
	vector<int> c(n);
	for (auto &x : c) {
		cin >> x;
	}
	sort(all(b));
	sort(all(c));
	vector<int> a_(a.size());
	for (int i = 0; i < a.size(); ++i) {
		a_[i] = a[(i + n) % a.size()];
		a_[i] = ((int)1e9) - a_[i];
	}
	vector<int> b_ = b;
	vector<int> c_ = c;
	for (auto &x : b_) {
		x = ((int)1e9) - x;
	}
	for (auto &x : c_) {
		x = ((int)1e9) - x;
	}
	reverse(all(b_));
	reverse(all(c_));
	int l = -1, r = 1e9 + 1;
	while (r - l > 1) {
		int m = (l + r) / 2;
		// m = 3;
		vector<int> ansB = solve(a, b, m);
		vector<int> ansC = solve(a, c, m);
		vector<int> ansB_ = solve(a_, c_, m);
		vector<int> ansC_ = solve(a_, b_, m);
    // for (auto &x : ansB) {
    //     cout << x << ' ';
    // }
    // cout << endl;
    // for (auto &x : ansC) {
    //     cout << x << ' ';
    // }
    // cout << endl;
    // for (auto &x : ansB_) {
    //     cout << x << ' ';
    // }
    // cout << endl;
    // for (auto &x : ansC_) {
    //     cout << x << ' ';
    // }
    // cout << endl;
    
		bool ok = false;
		for (int i = 0; i < n; ++i) {
			if (ansB[i] && ansB_[i]) {
				ok = true;
				break;
			}
			if (ansC[i] && ansC_[i]) {
				ok = true;
				break;
			}
		}
		if (ok) {
			r = m;
		} else {
			l = m;
		}
		// break;
	}
	cout << r << endl;
}

signed main() {
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #else
        ios::sync_with_stdio(false);
        cin.tie(0);
    #endif
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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