Submission #202490

#	Time	Username	Problem	Language	Result	Execution time	Memory
202490		rdd6584	Drvca (COCI19_drvca)	C++14	110 / 110	184 ms	37472 KiB

drvca

#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
const ll MOD = (ll)1e9 + 7;
const long double PI = 3.141592653589793238462643383279502884197;

priority_queue<int, vector<int>, greater<int>> pq;

vector<int> v;
multiset<int> se, tmp;

int vec[100000];
int n;

void print() {
    printf("%d\n", sz(v));
    for (int i = 0; i < sz(v); i++)
        printf("%d ", v[i]);
    printf("\n%d\n", sz(tmp));
    for (int i : tmp)
        printf("%d ", i);
    exit(0);
}
void check() {
    if (sz(v) == n) {
        se.insert(v.back());
        v.pop_back();
    }

    vector<int> vtmp = v;
    multiset<int> stmp = se;
    tmp = se;
    if (sz(se) == 1) print();
    int kk = *(++se.begin());
    int d = kk - *se.begin();

    kk = *(--(--se.end()));
    d = min(d, *(--se.end()) - kk);
    int next = *(--se.end());

    while (!se.empty()) {
        auto t = se.find(next);
        if (t == se.end()) {
            if (sz(v) >= 2 && next == v.back()) {
                v.pop_back();
                se.insert(next);
                tmp.insert(next);
                continue;
            }
            else break;
        }
        se.erase(t);
        next -= d;
    }
    if (se.empty()) print();

    v = vtmp;
    se = stmp;
    tmp = se;

    kk = *(++se.begin());
    d = kk - *se.begin();
    kk = *(--(--se.end()));
    d = min(d, *(--se.end()) - kk);
    next = v.back();
    while (!se.empty()) {
        auto t = se.find(next);
        if (t == se.end()) {
            if (sz(v) >= 2 && next == v.back()) {
                v.pop_back();
                se.insert(next);
                tmp.insert(next);
                continue;
            }
            else break;
        }
        se.erase(t);
        next -= d;
    }
    if (se.empty()) print();
}

int main() {
    scanf("%d", &n);

    for (int i = 0; i < n; i++)
        scanf("%d", &vec[i]);
    sort(vec, vec + n);

    if (n == 2) { return !printf("1\n%d\n1\n%d", vec[0], vec[1]); }

    // 1~2 등차 해보고 안되면..
    int d = 0;
    v.push_back(vec[0]);
    v.push_back(vec[1]);
    d = vec[1] - vec[0];

    for (int i = 2; i < n; i++) se.insert(vec[i]);
    int next = vec[1] + d;

    while (!se.empty()) {
        auto t = se.find(next);
        if (t == se.end()) break;
        v.push_back(*t);
        se.erase(t);
        next += d;
    }
    check();


    v.push_back(vec[0]);
    v.push_back(vec[2]);
    d = vec[2] - vec[0];

    se.insert(vec[1]);
    for (int i = 3; i < n; i++) se.insert(vec[i]);
    next = vec[2] + d;

    while (!se.empty()) {
        auto t = se.find(next);
        if (t == se.end()) break;
        v.push_back(*t);
        se.erase(t);
        next += d;
    }
    check();


    v.push_back(vec[1]);
    v.push_back(vec[2]);
    d = vec[2] - vec[1];

    se.insert(vec[0]);
    for (int i = 3; i < n; i++) se.insert(vec[i]);
    next = vec[2] + d;

    while (!se.empty()) {
        auto t = se.find(next);
        if (t == se.end()) break;
        v.push_back(*t);
        se.erase(t);
        next += d;
    }
    check();

    printf("-1");
}

Compilation message (stderr)

drvca.cpp: In function 'int main()':
drvca.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
drvca.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &vec[i]);
         ~~~~~^~~~~~~~~~~~~~~

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