Submission #443645

#	Time	Username	Problem	Language	Result	Execution time	Memory
443645		Karliver	Drvca (COCI19_drvca)	C++14	110 / 110	105 ms	8260 KiB

drvca

    
#include <bits/stdc++.h>

#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
#define rforn(i, n) for(int i = (n) - 1;i >= 0;--i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;

const int INF = 1e9 + 1;
const int N = 2e5 + 100;
const double eps = 1e-7;

template <class T> using V = vector<T>;  
template <class T> using VV = V<V<T>>;  

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}

void write(V<int> a, V<int> b) {
    if(b.empty()) {
        b.push_back(a.back());
        a.pop_back();
    }

    cout << a.size() << '\n';

    for(auto c : a) cout << c << ' ';

    cout << '\n';
    

    cout << b.size() << '\n';

    for(auto c : b) cout << c << ' ';

    exit(0);
}


multiset<int> ps;
int bad = 0;
bool issok(multiset<int>::iterator it) {
    auto nxt = it;

    ++nxt;
    if(nxt == ps.end() || it == ps.begin())return true;

    auto pr = it;
    --pr;

    return ((*it - *pr) == (*nxt - *it));
}

void add(int x) {
    if(ps.size() < 2) {
        ps.insert(x);
        return;
    }

    auto it = ps.insert(x);

    --it;
    bad += !issok(it);
}



void del(int x) {
    auto it =  ps.lower_bound(x);

    bad -= !issok(it);

    auto pr = it;
    
    if(pr != ps.begin()) {
        pr--;
        bad -= !issok(pr);
    }


    auto nxt = it;
    if(nxt != ps.end()) {
        nxt++;
        if(nxt != ps.end()) {
            bad -= !issok(nxt);
        }
    }

    it = ps.erase(it);

    if(it != ps.end()) {
        bad += !issok(it);
    }
    if(it != ps.begin()) {
        --it;
        bad += !issok(it);
    }
}



void solve() {


    int n;
    cin >> n;


    V<int> a(n);

    forn(i, n) cin >> a[i];

    sort(all(a));


    if(n == 2) {
        cout << 1 << '\n' << a[0] << '\n' << 1 << '\n' << a[1] << '\n';
        return;
    }

    if(n == 3) {
        cout << 2 << '\n' << a[0] << ' ' << a[1] << '\n' << 1 << '\n' << a[2] << '\n';
        return;
    }

    if(n == 4) {

        cout << 2 << '\n' << a[0] << ' ' << a[1] << '\n' << 2 << '\n' << a[2] << ' ' << a[3] << '\n';
        return;
    }



    for(int p = 0;p < 3;++p) {
        for(int q = p + 1;q < 3;++q) {

            int dif = a[q] - a[p];

            int nt = a[q] + dif;

            ps.clear();
            bad = 0;

            for(int x = 0;x < n;++x) {
                if(x == p || x == q)continue;

                add(a[x]);
            }

            V<int> one{a[p], a[q]}, two;

            if(bad == 0) {
                for(auto c : ps)two.push_back(c);

                write(one, two);
            }

            for(int x = q + 1;x < n;++x) {
                if(a[x] == nt) {
                    one.push_back(nt);
                    del(nt);

                    if(bad == 0) {
                        for(auto t : ps)
                            two.push_back(t);

                        write(one, two);
                    }
                    nt += dif;
                }
            }
        }
    }
    cout << -1 << '\n';








}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {

        //cout << "Case #" << p + 1 << ": ";
        solve();
    }
}
int main() {

    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();

}

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