Submission #1093065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093065		0pt1mus23	Drvca (COCI19_drvca)	C++14	0 / 110	1057 ms	26872 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 pr(vector<int>& a,vector<int>& b){
    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;
}
int equalz(int n,vector<int> arr,int eq){
    // cout<<eq<<endl;
    int ferq = arr.back()-eq;
    map<int,int> last;
    vector<int> div;
    for(int i=0;i<n;i++){
        last[arr[i]]=i;
    }
    for(int i=1;i*i<=ferq;i++){
        if(ferq%i==0){
            div.pb(i);
            if(i*i !=ferq){
                div.pb(ferq/i);
            }
        }
    }
    map<int,int> var;
    for(auto d:div){
        // cout<<d<<" div=>? "<<endl;
        bool flag=true;
        vector<int> lst,alst,blst;
        lst.pb(n-1);
        int curr=arr.back();
        while(true){
            int nx = curr - d;
            if(last.find(nx)==last.end()){
                flag=false;
                break;
            }
            lst.pb(last[nx]);
            curr=nx;
        }
        // for(auto v:lst)cout<<arr[v]<<" ";cout<<endl;
        var.clear();
        for(auto v:lst){
            var[v]=1;
        }    
        int LAST=-1;
        multiset<int> st;
        multiset<int> vet;
        for(int i=0;i<n;i++){
            if(!var[i]){
                vet.ins(arr[i]);
                if(LAST!=-1){
                    st.ins((arr[i] - LAST));
                }
                LAST=arr[i];
            }
        }
        while(!lst.empty()){    
            if(st.empty() || *st.begin() == *st.rbegin()){
                break;
            }
            int x = lst.back();
            int y=  arr[x];
            lst.pop_back();
            if(!vet.empty()){
                auto it = vet.lower_bound(y);
                if(it==vet.end()){
                    auto it2 = prev(it);
                    st.ins(abs(y -  ( *it2 ) ));
                }
                else{
                    st.ins(abs((y - (*it) )));
                    if(it!=vet.begin()){
                        auto it2 = prev(it);
                        st.ins(abs((y - (*it2) )));
                        st.erase(st.find( (*it) - (*it2) ));
                    }
                }
            }
            vet.ins(y);

            // for(auto v:lst) cout<<arr[v]<<" ";cout<<endl;
            // // cout<<"st size:  "<<st.size()<<endl;
            //     for(auto v:vet) cout<<v<<" ";cout<<endl;
            //         for(auto v:st) cout<<v<<" ";cout<<endl;
            //             cout<<"--------------\n";
        }


        if(st.empty() || *st.begin() == *st.rbegin()){
            vector<int> a,b;
            var.clear();
            for(auto v:lst){
                a.pb(arr[v]);
                var[v]=1;
            }
            for(int i=0;i<n;i++){
                if(!var[i]){
                    b.pb(arr[i]);
                }
            }
            pr(a,b);
            return 1;
        }

    }   
    return 0;
}

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));
    int eq=-1;
    for(int i=1;i<n;i++){
        if(arr[i]==arr[i-1]){
            eq=arr[i];
            break;
        }
    }
    for(auto v:arr) cout<<v<<" ";cout<<endl;
    if(eq!=-1){
        if(equalz(n,arr,eq)){
            return;
        }
    }
    
 
    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); 
        }
    }
    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){
            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]);
                }
            }
            pr(a,b);
 
            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 pr(std::vector<long long int>&, std::vector<long long int>&)':
drvca.cpp:28:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   28 |     for(auto v:a)cout<<v<<" ";cout<<endl;
      |     ^~~
drvca.cpp:28:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   28 |     for(auto v:a)cout<<v<<" ";cout<<endl;
      |                               ^~~~
drvca.cpp:30:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   30 |     for(auto v:b)cout<<v<<" ";cout<<endl;
      |     ^~~
drvca.cpp:30:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   30 |     for(auto v:b)cout<<v<<" ";cout<<endl;
      |                               ^~~~
drvca.cpp: In function 'long long int equalz(long long int, std::vector<long long int>, long long int)':
drvca.cpp:51:14: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
   51 |         bool flag=true;
      |              ^~~~
drvca.cpp: In function 'void opt1z()':
drvca.cpp:151:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  151 |     for(auto v:arr) cout<<v<<" ";cout<<endl;
      |     ^~~
drvca.cpp:151:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  151 |     for(auto v:arr) cout<<v<<" ";cout<<endl;
      |                                  ^~~~

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