Submission #1122482

#TimeUsernameProblemLanguageResultExecution timeMemory
1122482Math4Life2020Growing Vegetables is Fun 5 (JOI24_vegetables5)C++17
0 / 100
5095 ms37040 KiB
#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]); 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"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...