Submission #496010

#	Time	Username	Problem	Language	Result	Execution time	Memory
496010		AlperenT	Drvca (COCI19_drvca)	C++17	0 / 110	1096 ms	5516 KiB

drvca

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, arr[N], difa, difb, x, y, cur, nxt;

bool vis[N];

vector<int> ansa, ansb, fix;

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);

    for(int i = 2; i <= n; i++){
        difa = arr[i] - arr[1];

        if(i == 2) x = -1, y = -1;
        else if(i == 3) x = 2, y = -1;
        else if(i >= 4) x = 2, y = 3;

        cur = i;

        vis[1] = vis[i] = true;

        fix.push_back(1), fix.push_back(i);
        ansa.push_back(1), ansa.push_back(i);

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

            while(nxt <= n && vis[nxt]) nxt++;

            if(nxt <= n && arr[nxt] != arr[cur] + difa) nxt = n + 2;

            if(x == -1 && nxt > cur + 1 && cur + 1 <= n) x = cur + 1;
            else if(y == -1 && nxt > cur + 1 && cur + 1 <= n) y = cur + 1;

            if(y == -1 && nxt > cur + 2 && cur + 2 <= n) y = cur + 2;

            if(nxt > n || arr[nxt] != arr[cur] + difa) break;
            else{
                vis[nxt] = true;
                fix.push_back(nxt);
                ansa.push_back(nxt);

                cur = nxt;
            }
        }

        if(x == -1){
            cout << 1 << "\n" << arr[1] << "\n";
            cout << n - 1 << "\n";
            for(int i = 2; i <= n; i++) cout << arr[i] << " ";
            cout << "\n";
            return 0;
        }
        else if(y == -1){
            cout << n - 1 << "\n";
            for(int i = 1; i <= n; i++) if(i != x) cout << arr[i] << " ";
            cout << "\n";
            cout << 1 << "\n" << arr[x] << "\n";;
            return 0;
        }
        else{
            vis[x] = vis[y] = true;

            fix.push_back(x), fix.push_back(y);
            ansb.push_back(x), ansb.push_back(y);

            difb = arr[y] - arr[x];

            cur = y;

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

                while(nxt <= n && arr[nxt] == arr[cur] + difb && vis[nxt]) nxt++;

                if(nxt > n || arr[nxt] != arr[cur] + difb) break;
                else{
                    vis[nxt] = true;
                    fix.push_back(nxt);
                    ansb.push_back(nxt);

                    cur = nxt;
                }
            }

            if(ansa.size() + ansb.size() == n){
                cout << ansa.size() << "\n";
                for(auto j : ansa) cout << arr[j] << " ";
                cout << "\n";
                cout << ansb.size() << "\n";
                for(auto j : ansb) cout << arr[j] << " ";
                cout << "\n";
                return 0;
            }
        }

        // cout << i << ": ";
        // for(auto j : ansa) cout << j << " ";
        // cout << "\n";
        // cout << x << " " << y << "\n";

        for(auto j : fix) vis[j] = false;
        ansa.clear(); ansb.clear();
    }

    cur = 1;

    for(int i = 2; i <= n; i++) if(arr[i] == arr[1]) cur = i;

    if(cur >= n - 1){
        cout << cur - 1 << "\n";
        for(int i = 1; i <= cur - 1; i++) cout << arr[i] << " ";
        cout << "\n";
        cout << 1 << "\n";
        cout << arr[n] << "\n";
    }
    else{
        bool flag = true;
        for(int i = cur + 2; i + 1 <= n; i++){
            if(arr[i + 1] - arr[i] != arr[cur + 2] - arr[cur + 1]) flag = false;
        }

        if(flag){
            cout << cur << "\n";
            for(int i = 1; i <= cur; i++) cout << arr[i];
            cout << "\n";
            cout << n - cur << "\n";
            for(int i = cur + 1; i <= n; i++) cout << arr[i];
            cout << "\n";
        }
    }

    cout << -1;
}

Compilation message (stderr)

drvca.cpp: In function 'int main()':
drvca.cpp:97:42: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |             if(ansa.size() + ansb.size() == n){
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~

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