Submission #1306586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306586		kduckp	Drvca (COCI19_drvca)	C++20	0 / 110	1038 ms	7484 KiB

drvca

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define vi vector<int>
#define all(x) x.begin(), x.end()

// Hàm kiểm tra một vector có phải là cấp số cộng không
bool isArithmetic(const vi& v) {
    if (v.empty()) return true; // Tùy đề bài, thường dãy trống vẫn coi là CSC
    if (v.size() == 1) return true;
    int d = v[1] - v[0];
    for (int i = 2; i < v.size(); i++) {
        if (v[i] - v[i - 1] != d) return false;
    }
    return true;
}

void printResult(const vi& A, const vi& B) {
    cout << A.size() << endl;
    for (int x : A) cout << x << " ";
    cout << endl;
    cout << B.size() << endl;
    for (int x : B) cout << x << " ";
    cout << endl;
    exit(0);
}

// Hàm thử dựng dãy A bắt đầu từ start_val, công sai d, và lấy tối đa max_len phần tử
void solve_with_d(int start_idx, int d, int n, const vi& a) {
    vi A_full;
    vector<bool> used(n + 1, false);
    
    int last = a[start_idx];
    A_full.push_back(a[start_idx]);
    used[start_idx] = true;

    // Bước 1: Tìm tất cả các ứng viên cho dãy A với công sai d
    for (int i = start_idx + 1; i <= n; i++) {
        if (a[i] == last + d) {
            A_full.push_back(a[i]);
            used[i] = true;
            last = a[i];
        }
    }

    // Bước 2: Thử mọi độ dài của dãy A từ dài nhất về ngắn nhất (1 phần tử)
    // Việc thử mọi độ dài giúp tránh lỗi "tham lam" nhặt mất số của dãy B
    while (!A_full.empty()) {
        vi B;
        // Đánh dấu lại các phần tử thuộc A hiện tại
        vector<bool> current_in_A(n + 1, false);
        int count = 0;
        int target_idx = 0;
        
        // Vì mảng a đã sort, ta nhặt các phần tử của A_full từ mảng a
        for(int i = 1; i <= n; i++) {
            if (target_idx < A_full.size() && a[i] == A_full[target_idx]) {
                current_in_A[i] = true;
                target_idx++;
            } else {
                B.push_back(a[i]);
            }
        }

        if (isArithmetic(B)) {
            vi A_final;
            for(int i=1; i<=n; i++) if(current_in_A[i]) A_final.push_back(a[i]);
            if (A_final.empty() && B.empty()) { /* do nothing */ }
            else printResult(A_final, B);
        }
        
        // Giảm độ dài dãy A xuống để thử trường hợp khác
        A_full.pop_back(); 
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vi a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a.begin() + 1, a.end());

    if (n == 1) {
        cout << "1\n" << a[1] << "\n0\n\n";
        return 0;
    }

    // Theo hướng dẫn: Thử 3 trường hợp của 3 số nhỏ nhất
    // TH1: a[1] và a[2] cùng dãy A
    for (int i = 2; i <= n; i++) {
        solve_with_d(1, a[i] - a[1], n, a);
    }
    
    // TH2: a[1] thuộc dãy B, a[2] và a[3] thuộc dãy A (Nếu n >= 3)
    if (n >= 3) {
        solve_with_d(2, a[3] - a[2], n, a);
    }

    // TH3: a[1] và a[2] thuộc dãy B, dãy A bắt đầu từ đâu đó (Thực chất TH1 & TH2 đã bao phủ)

    cout << -1;
    return 0;
}

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