Submission #1085674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085674		serifefedartar	Drvca (COCI19_drvca)	C++17	0 / 110	40 ms	7616 KiB

drvca

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 100;

multiset<int> other_sequence;
map<int,int> diff;
vector<int> h, sequence;
int cnt = 0;

void omit(int k) {
    auto u = other_sequence.lower_bound(k);
    int C = 0;
    if (u != other_sequence.begin()) {
        C++;
        int dd = *u - *prev(u);
        diff[dd]--;
        if (diff[dd] == 0)
            cnt--;
    }
    if (prev(other_sequence.end()) != u) {
        C++;
        int x = *u;
        u++;
        int dd = *u - x;
        u--;
        diff[dd]--;;
        if (diff[dd] == 0)
            cnt--;
    }

    if (C == 2) {
        int L = *prev(u);
        u++;
        int R = *u;
        u--;
        diff[R - L]++;
        if (diff[R - L] == 1)
            cnt++;
    }
    other_sequence.erase(u);
}

int main() {
    fast;
    int N;
    cin >> N;

    h = vector<int>(N+1, 0);
    for (int i = 1; i <= N; i++)
        cin >> h[i];
    sort(h.begin(), h.end());

    if (N == 2) {
        cout << "1\n";
        cout << h[1] << "\n";
        cout << "1\n";
        cout << h[2] << "\n";
        exit(0);
    }

    for (int i = 1; i <= 2; i++) {
        for (int j = i+1; j <= 3; j++) {
            diff.clear();
            other_sequence.clear();
            sequence.clear();
            cnt = 0;
            for (int q = 1; q <= N; q++) {
                other_sequence.insert(h[q]);
                if (q != 1)
                    diff[h[q] - h[q-1]]++;
            }
    
            for (auto u : diff)
                cnt += (u.s == 1);

            omit(h[i]);
            omit(h[j]);
            sequence.push_back(h[i]);
            sequence.push_back(h[j]);

            if (cnt <= 1) {
                if (other_sequence.size() == 0) {
                    other_sequence.insert(sequence.back());
                    sequence.pop_back();
                }

                cout << sequence.size() << "\n";
                for (auto u : sequence)
                    cout << u << " ";
                cout << "\n";
                cout << other_sequence.size() << "\n";
                for (auto u : other_sequence)
                    cout << u << " ";
                cout << "\n";
                exit(0);
            }

            int seq_diff = sequence[1] - sequence[0];
            while (true) {
                int potential_new = sequence.back() + seq_diff;
                if (other_sequence.count(potential_new) == 0)
                    break;

                omit(potential_new);
                sequence.push_back(potential_new);

                if (cnt <= 1) {
                    if (other_sequence.size() == 0) {
                        other_sequence.insert(sequence.back());
                        sequence.pop_back();
                    }

                    cout << sequence.size() << "\n";
                    for (auto u : sequence)
                        cout << u << " ";
                    cout << "\n";
                    cout << other_sequence.size() << "\n";
                    for (auto u : other_sequence)
                        cout << u << " ";
                    cout << "\n";
                    exit(0);
                }
            }
        }
    }
    cout << "-1\n";
}

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