Submission #811271

#	Time	Username	Problem	Language	Result	Execution time	Memory
811271		Pring	Drvca (COCI19_drvca)	C++14	0 / 110	59 ms	13500 KiB

drvca

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

#define int long long
typedef pair<int, int> pii;

const int MXN = 100005;
int n, a[MXN];
multiset<int> MS;

inline void COUT(vector<int> &L, vector<int> &R) {
    cout << L.size() << endl;
    for (auto &i : L) cout << i << ' ';
    cout << endl << R.size() << endl;
    for (auto &i : R) cout << i << ' ';
    cout << endl;
}

bool check2(multiset<int> MS) {
    int pre = *MS.begin();
    MS.erase(MS.begin());
    int miku = -1;
    for (auto it = MS.begin(); it != MS.end(); it++) {
        if (miku == -1) miku = *it - pre;
        else if (miku != *it - pre) return false;
        pre = *it;
    }
    return true;
}

bool check(multiset<int> MS, int a0, int d) {
    vector<int> L, R;
    while (MS.find(a0) != MS.end()) {
        L.push_back(a0);
        MS.erase(MS.find(a0));
        a0 += d;
    }
    if (MS.empty()) {
        R.push_back(L.back());
        L.pop_back();
        COUT(L, R);
        return true;
    }
    if (check2(MS)) {
        for (auto it = MS.begin(); it != MS.end(); it++) R.push_back(*it);
        COUT(L, R);
        return true;
    }
    MS.insert(L.back());
    L.pop_back();
    if (check2(MS)) {
        for (auto it = MS.begin(); it != MS.end(); it++) R.push_back(*it);
        COUT(L, R);
        return true;
    }
    return false;
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    if (n == 2) {
        cout << 1 << endl << a[0] << endl << 1 << endl << a[1] << endl;
        return;
    }
    for (int i = 0; i < n; i++) MS.insert(a[i]);
    if (check(MS, a[0], a[1] - a[0])) return;
    if (check(MS, a[1], a[2] - a[1])) return;
    if (check(MS, a[0], a[2] - a[0])) return;
    cout << -1 << endl;
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    solve();
    return 0;
}

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