Submission #1193041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193041		nguyenkhangninh99	Drvca (COCI19_drvca)	C++20	110 / 110	132 ms	11972 KiB

drvca

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn = 1e5 + 5;
int n, p[maxn];

void check(int a, int b){
    multiset<int> s, diff;
    for(int i = 0; i < n; i++) s.insert(p[i]);
    s.erase(s.find(a));
    s.erase(s.find(b));
 
    vector<int> ans;
    ans.push_back(a);
    ans.push_back(b);

    int last = -1;
    for(auto x: s){
        if(last != -1) diff.insert(x - last);
        last = x;
    }

    int k = b - a;
    int tmp = b + k;
    
    do{
        if(*diff.begin() == *diff.rbegin()){
            cout << ans.size() << "\n";
            for(int x: ans) cout << x << " ";
            cout << "\n" << s.size() << "\n";
            for(int x: s) cout << x << " ";
            exit(0);  
        }

        auto it = s.find(tmp);
        if (it == s.end()) break;
        auto l = it, r = it;
        if(it != s.begin()) {
            l--;
            diff.erase(diff.find(*it - *l));
        }
        r++;
        if(r != s.end()){
            diff.erase(diff.find(*r - *it));
            if (it != s.begin()) diff.insert(*r - *l);
        }
        s.erase(it);
        ans.push_back(tmp);
        tmp += k;
    } while((int)ans.size() < n);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;

    for(int i = 0; i < n; i++) cin >> p[i];
    
    sort(p, p + n);

    if(n <= 4){
        cout << n / 2 << "\n";
        for(int i = 0; i < n / 2; i++) cout << p[i] << " ";
        cout << "\n" << n - n / 2 << "\n";
        for(int i = n / 2; i < n; i++) cout << p[i] << " ";
    }else{
        check(p[0], p[1]);
        check(p[0], p[2]);
        check(p[1], p[2]);
        cout << -1;
    }
}

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