Submission #198017

#	Time	Username	Problem	Language	Result	Execution time	Memory
198017		wleung_bvg	Drvca (COCI19_drvca)	C++14	110 / 110	193 ms	7504 KiB

drvca

#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int sz(const C&c){return int(c.size());}
using ll=long long;constexpr const char nl='\n',sp=' ';

const int MAXN = 1e5 + 5;

int N, H[MAXN];
map<int, int> vals, diffs;

void add(int v) {
    auto cur = vals.find(v);
    if (cur != vals.end()) {
        ++cur->second;
        ++diffs[0];
        return;
    }
    auto nxt = vals.upper_bound(v);
    if (nxt != vals.begin() && nxt != vals.end()) {
        auto it = diffs.find(nxt->first - prev(nxt)->first);
        if (--it->second == 0) diffs.erase(it);
    }
    cur = vals.emplace_hint(nxt, v, 1);
    if (nxt != vals.end()) ++diffs[nxt->first - v];
    if (cur != vals.begin()) ++diffs[v - prev(cur)->first];
}

void rem(int v) {
    auto cur = vals.find(v);
    if (cur->second >= 2) {
        --cur->second;
        auto it = diffs.find(0);
        if (--it->second == 0) diffs.erase(it);
        return;
    }
    auto nxt = next(cur);
    if (nxt != vals.end()) {
        auto it = diffs.find(nxt->first - v);
        if (--it->second == 0) diffs.erase(it);
    }
    if (cur != vals.begin()) {
        auto it = diffs.find(v - prev(cur)->first);
        if (--it->second == 0) diffs.erase(it);
    }
    vals.erase(cur);
    if (nxt != vals.begin()) if (nxt != vals.end()) ++diffs[nxt->first - prev(nxt)->first];
}

bool check(int A, int B) {
    int cur = A, diff = B - A;
    vector<int> reinsert;
    while (true) {
        auto it = vals.lower_bound(cur);
        if (it == vals.end() || it->first != cur) {
            break;
        }
        reinsert.push_back(it->first);
        rem(it->first);
        cur += diff;
        if (sz(diffs) <= 1) {
            vector<int> A, B;
            for (int v : reinsert) A.push_back(v);
            for (auto &&p : vals) for (int i = 0; i < p.second; i++) B.push_back(p.first);
            if (A.empty()) {
                A.push_back(B.back());
                B.pop_back();
            }
            if (B.empty()) {
                B.push_back(A.back());
                A.pop_back();
            }
            assert(sz(A) + sz(B) == N);
            cout << sz(A) << nl;
            for (int i = 0; i < sz(A); i++) cout << A[i] << " \n"[i == sz(A) - 1];
            cout << sz(B) << nl;
            for (int i = 0; i < sz(B); i++) cout << B[i] << " \n"[i == sz(B) - 1];
            return true;
        }
    }
    for (int v : reinsert) add(v);
    return false;
}

int main() {
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    // freopen("err.txt", "w", stderr);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) cin >> H[i];
    sort(H, H + N);
    for (int i = 0; i < N; i++) add(H[i]);
    if (check(H[0], H[1])) return 0;
    if (N >= 3 && check(H[0], H[2])) return 0;
    if (N >= 3 && check(H[1], H[2])) return 0;
    cout << -1 << nl;
    return 0;
}

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