Submission #496025

#	Time	Username	Problem	Language	Result	Execution time	Memory
496025		AlperenT	Drvca (COCI19_drvca)	C++17	0 / 110	37 ms	2908 KiB

drvca

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, arr[N], dif, cur, nxt;

bool vis[N];

vector<int> a, b, ansa, ansb;

bool check(vector<int> v){
    for(int i = 2; i < v.size(); i++) if(v[i] - v[i - 1] != v[1] - v[0]) return false;
    return true;
}

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

    cin >> n;

    for(int i = 1; i <= n; i++) cin >> arr[i];

    sort(arr + 1, arr + n + 1);

    if(arr[1] != arr[2]){
        a.clear(), b.clear(); memset(vis, 0, sizeof(vis));

        a.push_back(arr[1]); a.push_back(arr[2]);
        vis[1] = vis[2] = true;

        dif = arr[2] - arr[1];

        cur = 2;

        while(true){
            nxt = lower_bound(arr + 1, arr + n + 1, arr[cur] + dif) - arr;
            if(nxt > n || arr[nxt] != arr[cur] + dif) break;
            vis[nxt] = true;
            a.push_back(arr[nxt]);
            cur = nxt;
        }

        for(int i = 1; i <= n; i++) if(!vis[i]) b.push_back(arr[i]);

        if(check(b)) ansa = a, ansb = b;
    }
    else{
        a.clear(), b.clear();

        for(int i = 1; i <= n; i++){
            if(arr[i] == arr[1]) a.push_back(arr[i]);
            else b.push_back(arr[i]);
        }

        if(check(b)) ansa = a, ansb = b;
    }

    if(n >= 3 && arr[1] != arr[3]){
        a.clear(), b.clear(); memset(vis, 0, sizeof(vis));

        a.push_back(arr[1]); a.push_back(arr[3]);
        vis[1] = vis[3] = true;

        dif = arr[3] - arr[1];

        cur = 3;

        while(true){
            nxt = lower_bound(arr + 1, arr + n + 1, arr[cur] + dif) - arr;
            if(nxt > n || arr[nxt] != arr[cur] + dif) break;
            vis[nxt] = true;
            a.push_back(arr[nxt]);
            cur = nxt;
        }

        for(int i = 1; i <= n; i++) if(!vis[i]) b.push_back(arr[i]);

        if(check(b)) ansa = a, ansb = b;
    }
    
    if(n >= 3 && arr[2] != arr[3]){
        a.clear(), b.clear(); memset(vis, 0, sizeof(vis));

        a.push_back(arr[2]); a.push_back(arr[3]);
        vis[2] = vis[3] = true;

        dif = arr[3] - arr[2];

        cur = 3;

        while(true){
            nxt = lower_bound(arr + 1, arr + n + 1, arr[cur] + dif) - arr;
            if(nxt > n || arr[nxt] != arr[cur] + dif) break;
            vis[nxt] = true;
            a.push_back(arr[nxt]);
            cur = nxt;
        }

        for(int i = 1; i <= n; i++) if(!vis[i]) b.push_back(arr[i]);

        if(check(b)) ansa = a, ansb = b;
    }
    else if(n >= 3){
        a.clear(), b.clear();

        for(int i = 1; i <= n; i++){
            if(arr[i] == arr[2]) a.push_back(arr[i]);
            else b.push_back(arr[i]);
        }

        if(check(b)) ansa = a, ansb = b;
    }

    if(ansb.size() > ansa.size()) swap(ansb, ansa);

    if(ansa.size() == 0) cout << -1;
    else{
        if(ansb.size() == 0) ansb.push_back(ansa.back()), ansa.pop_back();

        cout << ansa.size() << "\n";
        for(auto i : ansa) cout << i << " ";
        cout << "\n";

        cout << ansb.size() << "\n";
        for(auto i : ansb) cout << i << " ";
        cout << "\n";
    }
}

Compilation message (stderr)

drvca.cpp: In function 'bool check(std::vector<int>)':
drvca.cpp:14:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i = 2; i < v.size(); i++) if(v[i] - v[i - 1] != v[1] - v[0]) return false;
      |                    ~~^~~~~~~~~~

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