Submission #496032

#	Time	Username	Problem	Language	Result	Execution time	Memory
496032		AlperenT	Drvca (COCI19_drvca)	C++17	110 / 110	46 ms	4092 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(arr[v[i]] - arr[v[i - 1]] != arr[v[1]] - arr[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(1); a.push_back(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(nxt);
            cur = nxt;
        }

        cur = -1;

        for(int i = 1; i <= n; i++){
            if(!vis[i]){
                if(b.size() < 2){
                    b.push_back(i);
                    cur = i;
                }
            }
        }

        if(b.size() == 2){
            dif = arr[b[1]] - arr[b[0]];

            while(true){
                nxt = lower_bound(arr + 1, arr + n + 1, arr[cur] + dif) - arr;

                if(nxt > n || arr[nxt] != arr[cur] + dif) break;
                else if(vis[nxt]){
                    if(nxt + 1 <= n && arr[nxt + 1] == arr[nxt]) nxt++;
                    else{
                        while(a.back() >= nxt){
                            vis[a.back()] = false;
                            a.pop_back();
                        }
                    }
                }

                vis[nxt] = true;
                b.push_back(nxt);
                cur = nxt;
            }
        }

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

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

        if(check(a) && check(b) && a.size() + b.size() == n) ansa = a, ansb = b;
    }

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

        a.push_back(1); a.push_back(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(nxt);
            cur = nxt;
        }

        cur = -1;

        for(int i = 1; i <= n; i++){
            if(!vis[i]){
                if(b.size() < 2){
                    b.push_back(i);
                    cur = i;
                }
            }
        }

        if(b.size() == 2){
            dif = arr[b[1]] - arr[b[0]];

            while(true){
                nxt = lower_bound(arr + 1, arr + n + 1, arr[cur] + dif) - arr;

                if(nxt > n || arr[nxt] != arr[cur] + dif) break;
                else if(vis[nxt]){
                    if(nxt + 1 <= n && arr[nxt + 1] == arr[nxt]) nxt++;
                    else{
                        while(a.back() >= nxt){
                            vis[a.back()] = false;
                            a.pop_back();
                        }
                    }
                }
                vis[nxt] = true;
                b.push_back(nxt);
                cur = nxt;
            }
        }

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

        a.push_back(2); a.push_back(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(nxt);
            cur = nxt;
        }

        cur = -1;

        for(int i = 1; i <= n; i++){
            if(!vis[i]){
                if(b.size() < 2){
                    b.push_back(i);
                    cur = i;
                }
            }
        }

        if(b.size() == 2){
            dif = arr[b[1]] - arr[b[0]];

            while(true){
                nxt = lower_bound(arr + 1, arr + n + 1, arr[cur] + dif) - arr;

                if(nxt > n || arr[nxt] != arr[cur] + dif) break;
                else if(vis[nxt]){
                    if(nxt + 1 <= n && arr[nxt + 1] == arr[nxt]) nxt++;
                    else{
                        while(a.back() >= nxt){
                            vis[a.back()] = false;
                            a.pop_back();
                        }
                    }
                }
                vis[nxt] = true;
                b.push_back(nxt);
                cur = nxt;
            }
        }

        if(check(a) && check(b) && a.size() + b.size() == n) 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(i);
            else b.push_back(i);
        }

        if(check(a) && check(b) && a.size() + b.size() == n) 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 << arr[i] << " ";
        cout << "\n";

        cout << ansb.size() << "\n";
        for(auto i : ansb) cout << arr[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(arr[v[i]] - arr[v[i - 1]] != arr[v[1]] - arr[v[0]]) return false;
      |                    ~~^~~~~~~~~~
drvca.cpp: In function 'int main()':
drvca.cpp:79:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   79 |         if(check(a) && check(b) && a.size() + b.size() == n) ansa = a, ansb = b;
      |                                    ~~~~~~~~~~~~~~~~~~~~^~~~
drvca.cpp:89:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         if(check(a) && check(b) && a.size() + b.size() == n) ansa = a, ansb = b;
      |                                    ~~~~~~~~~~~~~~~~~~~~^~~~
drvca.cpp:143:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  143 |         if(check(a) && check(b) && a.size() + b.size() == n) ansa = a, ansb = b;
      |                                    ~~~~~~~~~~~~~~~~~~~~^~~~
drvca.cpp:197:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  197 |         if(check(a) && check(b) && a.size() + b.size() == n) ansa = a, ansb = b;
      |                                    ~~~~~~~~~~~~~~~~~~~~^~~~
drvca.cpp:207:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  207 |         if(check(a) && check(b) && a.size() + b.size() == n) ansa = a, ansb = b;
      |                                    ~~~~~~~~~~~~~~~~~~~~^~~~

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