Submission #222729

#	Time	Username	Problem	Language	Result	Execution time	Memory
222729		kingfran1907	Drvca (COCI19_drvca)	C++14	110 / 110	109 ms	6900 KiB

drvca

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5+10;

int n;
int niz[maxn];
vector<int> a;
multiset<int> b;
map<int, int> m;

void print() {
    printf("%d\n", a.size());
    for (int i = 0; i < a.size(); i++)
        printf("%d ", a[i]);

    printf("\n%d\n", b.size());
    for (auto iter = b.begin(); iter != b.end(); iter++)
        printf("%d ", *iter);
    printf("\n");
}

void print_deb() {
    printf("a: ");
    for (int i = 0; i < a.size(); i++)
        printf("%d ", a[i]);
    printf("\nb: ");
    for (auto iter = b.begin(); iter != b.end(); iter++)
        printf("%d ", *iter);

    printf("\nm: ");
    for (auto iter = m.begin(); iter != m.end(); iter++)
        printf("(%d, %d) ", iter->first, iter->second);
    printf("\n\n");
}

void check(int x, int y) {
    a.clear();
    b.clear();
    m.clear();

    int dif = niz[y] - niz[x];
    a.push_back(niz[x]);
    a.push_back(niz[y]);

    int last = -1;
    for (int i = 0; i < n; i++) {
        if (i == x || i == y) continue;
        if (niz[i] == a.back() + dif) a.push_back(niz[i]);
        else {
            b.insert(niz[i]);
            if (last != -1) m[niz[i] - last]++;
            last = niz[i];
        }
    }

    if (m.size() == 1) {
        print();
        exit(0);
    }
    //print_deb();

    while (!a.empty()) {
        int tren = a.back();
        int pref, nex;
        auto iter = b.lower_bound(tren);
        if (iter == b.begin()) pref = -1;
        else pref = *(--iter), iter++;

        if (iter == b.end()) nex = -1;
        else nex = *iter;

        if (pref != -1) m[tren - pref]++;
        if (nex != -1) m[nex - tren]++;

        if (pref != -1 && nex != -1) {
            //printf("retard: %d %d -> %d\n", nex, pref, nex - pref);
            m[nex - pref]--;
            if (m[nex - pref] == 0) m.erase(nex - pref);
        }
        a.pop_back();
        b.insert(tren);

        //printf("prev, nex: %d, %d\n", pref, nex);
        //print_deb();

        if (m.size() == 1) {
            print();
            exit(0);
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", niz+i);
    sort(niz, niz+n);

    if (n < 5) {
        printf("%d\n", n / 2);
        for (int i = 0; i < n / 2; i++)
            printf("%d ", niz[i]);

        printf("\n%d\n", n - n / 2);
        for (int i = 0; i < n - n / 2; i++)
            printf("%d ", niz[n / 2 + i]);
        printf("\n");
        return 0;
    }
    check(0, 1);
    check(0, 2);
    check(1, 2);
    printf("-1\n");
    return 0;
}

Compilation message (stderr)

drvca.cpp: In function 'void print()':
drvca.cpp:13:28: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", a.size());
                    ~~~~~~~~^
drvca.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); i++)
                     ~~^~~~~~~~~~
drvca.cpp:17:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::multiset<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("\n%d\n", b.size());
                      ~~~~~~~~^
drvca.cpp: In function 'void print_deb()':
drvca.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a.size(); i++)
                     ~~^~~~~~~~~~
drvca.cpp: In function 'int main()':
drvca.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
drvca.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", niz+i);
         ~~~~~^~~~~~~~~~~~~

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