#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++) {
if (bmax[i]==(-INF)) {
invarr.push_back({0,i});
} else {
invarr.push_back({0LL,i-bmax[i]-1});
invarr.push_back({max(0LL,i+1-bmin[i]),min(i,1+jmax[i])});
if (((i-1-jmax[i])<bmin[i]) || ((i-1-jmax[i])>bmax[i])) {
invarr.push_back({2+jmax[i],i});
}
}
}
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);
//a = acopy;
vector<bool> qf;
for (ll i=0;i<N;i++) {
//qf.push_back(q1[i]&&q2[N-i]);
qf.push_back(q1[i]);
}
return qf;
}*/
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]);
}
}
}
for (ll i=0;i<N;i++) {
if (bmax[i]==(-INF)) {
invarr.push_back({0,i});
} else {
invarr.push_back({0LL,i-bmax[i]-1});
invarr.push_back({max(0LL,i+1-bmin[i]),min(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 (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 || (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);
}
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());
// swap(a,fa);
// swap(b,nc);
// vector<bool> b1 = qry(8);
// for (auto x: b1) {
// cout << x<<"\n";
// }
// exit(0);
ans = min(ans,process());
//cout << "ans0="<<ans<<"\n";
swap(b,c);
swap(nb,nc);
ans = min(ans,process());
cout << ans <<"\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |