제출 #1085671

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1085671		serifefedartar	Drvca (COCI19_drvca)	C++17	50 / 110	1036 ms	11204 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, 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.erase(diff.find(dd));
        if (diff.count(dd) == 0)
            cnt--;
    }
    if (prev(other_sequence.end()) != u) {
        C++;
        int x = *u;
        u++;
        int dd = *u - x;
        u--;
        diff.erase(diff.find(dd));
        if (diff.count(dd) == 0)
            cnt--;
    }

    if (C == 2) {
        int L = *prev(u);
        u++;
        int R = *u;
        u--;
        diff.insert(R - L);
        if (diff.count(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.insert(h[q] - h[q-1]);
            }
    
            int last = -1;
            for (auto u : diff) {
                cnt += (last != u);
                last = u;
            }

            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: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30