Submission #519428

#	Time	Username	Problem	Language	Result	Execution time	Memory
519428		KoD	Drvca (COCI19_drvca)	C++17	110 / 110	138 ms	12464 KiB

drvca

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

void show(const vector<int>& v) {
    const int n = v.size();
    std::cout << n << '\n';
    for (int i = 0; i < n; ++i) {
        std::cout << v[i] << " \n"[i + 1 == n];
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<int> A(N);
    for (auto& x : A) {
        std::cin >> x;
    }
    const auto try_seq = [&](const int first, const int dif) {
        std::multiset<int> set(A.begin(), A.end());
        std::multiset<int> dist;
        for (auto itr = set.begin(); std::next(itr) != set.end(); ++itr) {
            dist.insert(*std::next(itr) - *itr);
        }
        int element = first;
        vector<int> taken;
        while (true) {
            auto itr = set.find(element);
            if (itr == set.end()) {
                return;
            }
            if (itr != set.begin()) {
                dist.erase(dist.find(*itr - *std::prev(itr)));
            }
            if (std::next(itr) != set.end()) {
                dist.erase(dist.find(*std::next(itr) - *itr));
            }
            if (itr != set.begin() and std::next(itr) != set.end()) {
                dist.insert(*std::next(itr) - *std::prev(itr));
            }
            taken.push_back(element);
            set.erase(itr);
            if (dist.empty() or *dist.begin() == *dist.rbegin()) {
                show(taken);
                show(vector<int>(set.begin(), set.end()));
                std::exit(EXIT_SUCCESS);
            }
            element += dif;
        }
    };
    std::sort(A.begin(), A.end());
    try_seq(A[0], A[1] - A[0]);
    try_seq(A[0], A[2] - A[0]);
    try_seq(A[1], A[2] - A[1]);
    std::cout << -1 << '\n';
    return 0;
}

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