Submission #1093010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093010		0pt1mus23	Drvca (COCI19_drvca)	C++14	0 / 110	225 ms	44256 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;
}
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(); 
        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;
            }
        }
        ranges.pb(-1);
        int len = ranges.size();
        vector<pair<int, pair<int,int>>> ferqs;
        int orta = -1;
        for(int j=1;j<len;j++){
            int r = ranges[j-1]-1;
            int l = ranges[j]+1;
            if(l<=r){
                if(l==r){
                    ferqs.pb({-1, {arr[l],arr[l]} });
                }
                else{
                    int lx = l;
                    int rx = r-1;
                    pair<int,int> res =  qry(lx,rx);
                    if(res.first!=res.second){
                        flag=false;
                        break;
                    }
                    orta = res.first;
                    ferqs.pb({res.first,{arr[l],arr[r]}});
                }
            }
        }
        if(flag){
            ranges.pop_back();
            reverse(all(ferqs));
            int ll = ferqs.size();
            // cout<<ferq<<" => "<<" "<<orta<<endl;
            if(ferqs.size() > 1){
                orta = ferqs[1].second.first - ferqs[0].second.second;
                // cout<<orta<<endl;

                for(int i =0;i<ll;i++){
                    if(ferqs[i].first!=-1 && ferqs[i].first!=orta){
                        flag=false;
                        break;
                    }
                    if(i){
                        if( (ferqs[i].second.first - ferqs[i-1].second.second ) != orta){
                            flag=false;
                            break;
                        }
                    }
                }
            }
        }

        
        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:148:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  148 |             for(auto v:a)cout<<v<<" ";cout<<endl;
      |             ^~~
drvca.cpp:148:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  148 |             for(auto v:a)cout<<v<<" ";cout<<endl;
      |                                       ^~~~
drvca.cpp:150:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  150 |             for(auto v:b)cout<<v<<" ";cout<<endl;
      |             ^~~
drvca.cpp:150:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  150 |             for(auto v:b)cout<<v<<" ";cout<<endl;
      |                                       ^~~~

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