Submission #1093006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093006		0pt1mus23	Drvca (COCI19_drvca)	C++14	0 / 110	217 ms	42892 KiB

drvca

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define ins insert
#define endl '\n'
#define putr(x) cout<<x<<endl;return;
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7,sze = 1e5 +23,inf = INT_MAX, L = 30; 

pair<int,int> dp[L][sze];
int lg[sze];

pair<int,int> qry(int l,int r){
    pair<int,int> res;
    int i = lg[r-l+1];
    res.first = min(dp[i][l].first,dp[i][r - (1<<i) +1].first);
    res.second = max(dp[i][l].second,dp[i][r - (1<<i) +1].second);
    return res;
}
int check(int l,int r,int cc){
    pair<int,int> res=qry(l,r);
    return ( res.first==res.second && res.first==cc) ;
}
void opt1z(){
    int n;
    cin>>n;
    for(int i=2;i<=n;i++){
        lg[i]=lg[i/2] +1;
    }
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    sort(all(arr));
    

    vector<int> lst;
    for(int i=0;i+1<n;i++){
        lst.pb(arr[i+1]-arr[i]);
        dp[0][i].first=lst[i];
        dp[0][i].second=lst[i];
    }
    int m = lst.size();

    for(int i =1;i<L;i++){
        for(int j=0;j + (1<<i)<=m;j++){
            dp[i][j].first = min(dp[i-1][j].first, dp[i-1][j + (1<<(i-1))].first); 
            dp[i][j].second = max(dp[i-1][j].second, dp[i-1][j + (1<<(i-1))].second); 
        }
    }
    // for(auto v:arr) cout<<v<<" ";cout<<endl;
    map<int,int> idx;
    vector<int> ranges;
    for(int i=0;i<n;i++){
        idx[arr[i]]=i;
    }
    for(int i=0;i+1<n;i++){
        int ferq = arr.back() - arr[i];
        if(ferq==0){
            break;
        }
        // cout<<ferq<<endl;
        int curr = arr[i];
        bool flag=true;

        ranges.clear(); // optimize later maybe
        ranges.pb(n-1);
        ranges.pb(i);
        while(true){

            int nx = curr - ferq;
            // cout<<ferq<<" ==== "<<nx<<endl;
            if(idx.find(nx)!=idx.end()){
                // cout<<nx<<endl;
                ranges.pb(idx[nx]);
                curr=nx;
            }
            else{
                break;
            }
        }
        // cout<<ferq<<" => \n";
        // for(auto v:ranges) cout<<v<<" ";cout<<"\n";
        int len = ranges.size();
        // vector<int> ferqs;
        int last=-1;
        int ortalar = -1;
        for(int j=1;j<len;j++){
            int r = ranges[j-1]-1;
            int l = ranges[j]+1;
            if(l<=r){
                // cout<<l<<";"<<r<<" "<<ranges[j-1]<<","<<ranges[j]<<endl;
                if(l<r){
                    int lx=l;
                    int rx = r-1;
                    pair<int,int> res = qry(lx,rx);
                    if(res.first!=res.second){
                        // cout<<ferq<<" error"<<endl;
                        flag=false;
                        break;
                    }
                    if(last==-1){
                        ortalar=res.first;
                    }
                    else{
                        if(ortalar==-1){
                            ortalar = last -arr[r];
                            if(ortalar!=res.first){
                                // cout<<ferq<<" error:"<< ortalar<<" "<<last<<" "<<arr[r]<<" "<<res.first<<endl;
                                flag=false;
                                break;
                            }
                        }
                        else{
                            if(( res.first!=ortalar || ( last-arr[r])!=res.first  )){
                                // cout<<ferq<<" error:"<< ortalar<<" "<<last<<" "<<arr[r]<<" "<<res.first<<endl;
                                flag=false;
                                break;
                            }
                        }
                    }
                }
                last=arr[l];
            }
        }

        if(ranges.back()!=0 && flag){
            int l = 0;
            int r = ranges.back()-2;
            if(r<l){
                if(last!=-1){
                    if(ortalar!=-1){
                        if((last-arr[0]) != ortalar ){
                            // cout<<ferq<<" error"<<endl;
                            flag=false;
                        }
                    }
                }
            }
            else{
                pair<int,int> res = qry(l,r);
                if(last!=-1){
                    if(ortalar==-1){
                        if( ( res.first!=res.second || (last - arr[r+1])!=res.first )){
                            // cout<<ferq<<" error"<<endl;
                            // cout<<res.first<<" "<<res.second<<" "<<l<<","<<r<<" "<<last<<" "<<arr[r+1]<<" "<<(res.first!=res.second)<<endl;
                            flag=false;
                        }
                    }
                    else{
                        if(( res.first!=res.second || res.first!=ortalar || (last - arr[r+1])!=ortalar)){
                            flag=false;
                        }
                    }
                }
                else{
                    if(res.first!=res.second){
                        flag=false;
                    }
                }
            }
        }

        
        if(flag){
            // cout<<ferq<<" => \n";
            // for(auto v:ranges) cout<<v<<" ";cout<<"\n";
            vector<int> a,b;
            map<int,int> used;
            reverse(all(ranges));
            for(auto v:ranges){
                used[v]=1;
                a.pb(arr[v]);
            }
            for(int j=0;j<n;j++){
                if(!used[j]){
                    b.pb(arr[j]);
                }
            }
            if(b.empty()){
                b.pb(a.back());
                a.pop_back();
            }
            cout<<a.size()<<"\n";
            for(auto v:a)cout<<v<<" ";cout<<endl;
            cout<<b.size()<<"\n";
            for(auto v:b)cout<<v<<" ";cout<<endl;

            return;
        }
    }


    putr(-1);

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int tt = 1;
    // cin>>tt;
    while(tt--){
        opt1z();
    }

    return 0;
}

Compilation message (stderr)

drvca.cpp: In function 'void opt1z()':
drvca.cpp:186:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  186 |             for(auto v:a)cout<<v<<" ";cout<<endl;
      |             ^~~
drvca.cpp:186:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  186 |             for(auto v:a)cout<<v<<" ";cout<<endl;
      |                                       ^~~~
drvca.cpp:188:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  188 |             for(auto v:b)cout<<v<<" ";cout<<endl;
      |             ^~~
drvca.cpp:188:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  188 |             for(auto v:b)cout<<v<<" ";cout<<endl;
      |                                       ^~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30