Submission #1160814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160814		guagua0407	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	100 / 100	3127 ms	70888 KiB

Main

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int inf=1e9;

int main() {_
    int n;
    cin>>n;
    vector<int> a(2*n);
    for(int i=0;i<2*n;i++){
        cin>>a[i];
    }
    vector<vector<int>> b(2,vector<int>(n));
    for(int i=0;i<2;i++){
        for(int j=0;j<n;j++){
            cin>>b[i][j];
        }
        sort(all(b[i]));
    }
    vector<int> A=a;
    A.insert(A.end(),all(a));
    A.insert(A.end(),all(a));
    struct node{
        int pos,val,dif;
    };
    vector<vector<node>> d(2*n);
    for(int i=2*n;i<3*n;i++){
        int pos=lower_bound(A.begin()+n,A.begin()+2*n,A[i],greater<int>())-A.begin();
        int l=i-n+1;
        if(l<pos){
            d[i%(2*n)].push_back({l,n-(pos-l),0});
        }
        d[i%(2*n)].push_back({max(pos,l),n-max(0,pos-l),-1});
        pos=upper_bound(A.begin()+3*n,A.begin()+4*n,A[i],greater<int>())-A.begin();
        if(pos<=i+n-1){
            d[i%(2*n)].push_back({pos-n+1,n-(pos-i)+1,0});
        }
        d[i%(2*n)].push_back({i+1,-1,-1});
    }
    for(int i=3*n;i<4*n;i++){
        int pos=upper_bound(A.begin()+2*n,A.begin()+3*n,A[i])-A.begin();
        int l=i-n+1;
        if(l<pos){
            d[i%(2*n)].push_back({l,(pos-l)+1,0});
        }
        d[i%(2*n)].push_back({max(pos,l),n-(i-max(pos,l)),1});
        pos=lower_bound(A.begin()+4*n,A.begin()+5*n,A[i])-A.begin();
        if(pos<=i+n-1){
            d[i%(2*n)].push_back({pos-n+1,(pos-i),0});
        }
        d[i%(2*n)].push_back({i+1,-1,-1});
    }
    for(int i=0;i<2*n;i++){
        //cout<<i<<'\n';
        for(auto v:d[i]){
            //cout<<v.pos%(2*n)<<' '<<v.val<<' '<<v.dif<<'\n';
        }
    }
    vector<vector<int>> cnt(2,vector<int>(2*n+1));
    auto check=[&](int mid){
        fill(all(cnt[0]),0);
        fill(all(cnt[1]),0);
        //cout<<"mid "<<mid<<'\n';
        auto add=[&](int t,int l,int r){
            if(r<l) return;
            //cout<<l<<' '<<r<<'\n';
            l%=(2*n);
            r%=(2*n);
            if(l<=r){
                cnt[t][l]++;
                cnt[t][r+1]--;
            }
            else{
                cnt[t][l]++;
                cnt[t][2*n]--;
                cnt[t][0]++;
                cnt[t][r+1]--;
            }
        };
        for(int t=0;t<2;t++){
            for(int i=0;i<2*n;i++){
                int L=lower_bound(all(b[t]),a[i]-mid)-b[t].begin()+1;
                int R=upper_bound(all(b[t]),a[i]+mid)-b[t].begin()-1+1;
                //cout<<i<<'\n';
                //cout<<"L R "<<L<<' '<<R<<'\n';
                if(R<L) continue;
                int sz=(int)d[i].size();
                for(int j=0;j<sz-1;j++){
                    if(d[i][j].dif==0){
                        if(L<=d[i][j].val and d[i][j].val<=R){
                            add(t,d[i][j].pos,d[i][j+1].pos-1);
                        }
                    }
                    else{
                        int dl=-1,dr=-1;
                        if(L<=d[i][j].val and d[i][j].val<=R){
                            dl=0;
                            dr=max((L-d[i][j].val)/d[i][j].dif,(R-d[i][j].val)/d[i][j].dif);
                        }
                        else{
                            dl=(L-d[i][j].val)/d[i][j].dif;
                            dr=(R-d[i][j].val)/d[i][j].dif;
                        }
                        if(dl>dr) swap(dl,dr);
                        dr=min(dr,d[i][j+1].pos-d[i][j].pos-1);
                        if(dl<0 or dr<0 or dr<dl or d[i][j].pos+dl>=d[i][j+1].pos) continue;
                        //cout<<d[i][j].pos+dl<<' '<<d[i][j].pos+dr<<'\n';
                        add(t,d[i][j].pos+dl,d[i][j].pos+dr);
                    }
                }
            }
        }
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=cnt[1][i];
        }
        //cout<<'\n';
        for(int i=0;i<2*n;i++){
            sum+=cnt[0][i];
            sum+=cnt[1][(i+n)%(2*n)];
            if((i+n)==2*n) sum+=cnt[1][2*n];
            if(sum==2*n){
                //cout<<"find "<<i<<'\n';
                return true;
            }
        }
        return false;
    };
    int l=0,r=max({*max_element(all(a)),*max_element(all(b[0])),*max_element(all(b[1]))});
    while(l<r){
        int mid=(l+r)/2;
        if(check(mid)){
            r=mid;
        }
        else{
            l=mid+1;
        }
    }
    cout<<l<<'\n';
    return 0;
}
//maybe its multiset not set
//yeeorz
//diaoborz

Compilation message (stderr)

Main.cpp: In function 'void setIO(std::string)':
Main.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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