Submission #1093852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093852		0pt1mus23	Drvca (COCI19_drvca)	C++14	110 / 110	425 ms	58200 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 = 18; 

int check(vector<int> arr){
    if(arr.empty()) return 0;
    int n = arr.size();
    for(int i=1;i+1<n;i++){
        if((arr[i+1]-arr[i]) != arr[i]-arr[i-1]){
            return 0;
        }
    }
    return 1;
}
void print(vector<int> arr,vector<int> brr){
    if(brr.empty()){
        brr.pb(arr.back());arr.pop_back();
    }
    cout<<arr.size()<<"\n";
    for(auto v:arr) cout<<v<<" "; cout<<endl;
    cout<<brr.size()<<"\n";
    for(auto v:brr) cout<<v<<" "; cout<<endl;
}
int equalz(vector<int> arr,int n,int eq){
    vector<int> a,b;
    for(auto v:arr){
        if(v==eq){
            a.pb(v);
        }
        else{
            b.pb(v);
        }
    }
    if(b.empty()){
        b.pb(a.back());
        a.pop_back();
    }
    // for(auto v:a) cout<<v<<" ";cout<<endl;
    if(check(b)){
        print(a,b);
        return 1;
    }
    if(a.size()>1){
        b.pb(a.back());
        a.pop_back();
        sort(all(b));
    }

    if(check(b)){
        print(a,b);
        return 1;
    }
    return 0;
}

int lg[sze];
pair<int,int> dp[L][sze];
pair<int,int> qry(int l,int r){
    if(r<l){
        return {-1,-1};
    }
    int i = lg[r-l+1];
    pair<int,int> res;
    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);
    map<int,int> count;
    int eq=-1;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        count[arr[i]]++;
        if(eq==-1 && count[arr[i]]>1){
            eq=arr[i];
        }
    }
    /*
    eq:
        x,x,x,x
        a,a+k, x? , a+3k...

        x,x,x
        a,b,c,d
    idx:
        n-1,i,...j
            f[i] : i sonuncu olsa, evvelki diff, => & 0 -> i-1 diff
    */
    sort(all(arr));
    if(eq!=-1){
        // cout<<eq<<endl;
        if(equalz(arr,n,eq)){
            return;
        }
    }

    // for(auto v:arr) cout<<v<<" ";cout<<endl;

    for(int i=0;i+1<n;i++){
        dp[0][i].first=(arr[i+1]-arr[i]);
        dp[0][i].second=(arr[i+1]-arr[i]);
        // cout<<i<<" "<<arr[i+1]-arr[i]<<endl;
    }
    int m2=n-1;
    for(int i =1;i<L;i++){
        for(int j=0;j+ (1<<i)<=m2;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> last;
    for(int i=0;i<n;i++){
        last[arr[i]]=i;
    }

    map<int,int> mem;
    mem[0]=1;
    set<int> ff;
    for(int im=0;im+1<n;im++){
        int ferq = arr.back()-arr[im]; 
        if(mem[ferq]){
            continue;
        }
        mem[ferq]=1;
        vector<int> lst;
        lst.pb(n-1);
        lst.pb(im);
        int curr = arr[im];
        while(true){
            curr = curr-ferq;
            if(!last.count(curr)){
                break;
            }
            lst.pb(last[curr]);
        }
        // cout<<ferq<<": ";
        // for(auto v:lst) cout<<v<<" ";cout<<endl;
        int m = lst.size();
        vector<pair<int,int>> f(m,{0,-1});
        vector<int> f3(m,-1);
        f[0].first=1;
        f[0].second=-1;

        int arxaferq = -1;
        for(int i=1;i<m;i++){
            if(!f[i-1].first){
                break;
            }
            int rx = lst[i-1]-1;
            int lx = lst[i]+1;
            if(lx>rx){
                f[i].first = 1;
                f3[i]=f3[i-1];
                f[i].second = f[i-1].second;
                continue;
            }

            int lan2 = arr[lx];

            pair<int,int> orta = qry(lx,rx-1);
            if(orta.first!=orta.second){
                break;
            }
            int connection=-1;
            if(f[i-1].second != -1){
                connection = f[i-1].second - arr[rx];
                // cout<<connection<<endl;
            }
            ff.clear();
            if(connection!=-1){
                ff.ins(connection);
            }

            if(orta.first!=-1){
                ff.ins(orta.first);
            }
            if(arxaferq!=-1){
                ff.ins(arxaferq);
            }
            // cout<<i<<" => ";
            // cout<<orta.first<<" "<<arxaferq<<" "<<connection<<" "<<endl;
            // cout<<endl;
            
            if(ff.size()>1){
                break;
            }
            if(!ff.empty()){
                // cout<<i<<" "<<"Sa"<<endl;
                arxaferq = (*ff.begin());
            }
            f3[i]=arxaferq;
            f[i].second  =  lan2;
            f[i].first  =  1;
        }
        // cout<<ferq<<" =: ";
        // for(auto v:lst) cout<<arr[v]<<" ";cout<<endl;
        // for(int i=0;i<m;i++){
        //     cout<<f[i].first<<" "<<f[i].second<<"\n";
        // }
        // cout<<endl;
        for(int i =0;i<m;i++){
            if(!f[i].first){
                break;
            }
            int f2 = f3[i];
            pair<int,int> zero = qry(0,lst[i]-2);
            if(zero.first!=zero.second){
                continue;
            }
            ff.clear();
            int connection =-1;
            if(lst[i]>0 && f[i].second!=-1 ){
                connection = f[i].second - arr[lst[i]-1];
                // cout<<ferq<<" "<<i<<" "<<f2<<" "<<connection<<" "<<f[i].second<<endl;
            }
            if(zero.first!=-1){
                ff.ins(zero.first);
            }
            if(f2!=-1){
                ff.ins(f2);
            }
            if(connection!=-1){
                ff.ins(connection);
            }
            if(ff.size()<2){
                map<int,int> used;
                vector<int> a,b;
                for(int j=0;j<=i;j++){
                    used[lst[j]]=1;
                    a.pb(arr[lst[j]]);
                }
                reverse(all(a));
                for(int j=0;j<n;j++){
                    if(!used[j]){
                        b.pb(arr[j]);
                    }
                }
                if(!check(a) || !check(b)){
                    putr("lan");
                    while(true){

                    }
                }
                print(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 print(std::vector<long long int>, std::vector<long long int>)':
drvca.cpp:26:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   26 |     for(auto v:arr) cout<<v<<" "; cout<<endl;
      |     ^~~
drvca.cpp:26:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   26 |     for(auto v:arr) cout<<v<<" "; cout<<endl;
      |                                   ^~~~
drvca.cpp:28:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   28 |     for(auto v:brr) cout<<v<<" "; cout<<endl;
      |     ^~~
drvca.cpp:28:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   28 |     for(auto v:brr) cout<<v<<" "; cout<<endl;
      |                                   ^~~~

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