제출 #1306587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306587		kduckp	Drvca (COCI19_drvca)	C++20	50 / 110	1094 ms	5372 KiB

drvca

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

#define int long long
#define vi vector<int>

bool isArithmetic(const vi& v) {
    if (v.empty()) return true; 
    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 check(vi A, vi B) {
    if ((A.empty() && B.empty())) return;
    // Tùy đề bài có cho phép 1 dãy rỗng hay không, 
    // nếu không cho phép rỗng thì thêm: if (A.empty() || B.empty()) return;
    if (isArithmetic(A) && isArithmetic(B)) {
        cout << A.size() << "\n";
        for (int x : A) cout << x << " "; cout << "\n";
        cout << B.size() << "\n";
        for (int x : B) cout << x << " "; cout << "\n";
        exit(0);
    }
}

// Hàm này nhặt dãy A theo cách: Thử mọi số lượng phần tử có thể có của dãy A
void solve(int n, const vi& a, int first_idx, int second_idx) {
    int d = a[second_idx] - a[first_idx];
    vi candidates;
    vector<bool> is_candidate(n + 1, false);
    
    // Nhặt tất cả các vị trí có thể thuộc dãy A bắt đầu từ first_idx với công sai d
    int last = a[first_idx];
    candidates.push_back(first_idx);
    for (int i = first_idx + 1; i <= n; i++) {
        if (a[i] == last + d) {
            candidates.push_back(i);
            last = a[i];
        }
    }

    // Thử mọi "độ dài" của dãy A (nhặt từ trái qua phải)
    for (int len = 1; len <= candidates.size(); len++) {
        vi A, B;
        vector<bool> inA(n + 1, false);
        for (int i = 0; i < len; i++) inA[candidates[i]] = true;
        
        for (int i = 1; i <= n; i++) {
            if (inA[i]) A.push_back(a[i]);
            else B.push_back(a[i]);
        }
        check(A, B);
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; if (!(cin >> n)) return 0;
    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;
    }

    // Trường hợp đặc biệt: Dãy A chỉ có đúng 1 phần tử là a[1]
    vi A_single = {a[1]}, B_rest;
    for(int i=2; i<=n; i++) B_rest.push_back(a[i]);
    check(A_single, B_rest);

    // TH1: a[1] và a[2] thuộc cùng 1 dãy
    solve(n, a, 1, 2);
    // TH2: a[1] và a[3] thuộc cùng 1 dãy (a[2] phải thuộc dãy kia)
    if (n >= 3) solve(n, a, 1, 3);
    // TH3: a[2] và a[3] thuộc cùng 1 dãy (a[1] phải thuộc dãy kia)
    if (n >= 3) solve(n, a, 2, 3);

    cout << -1;
    return 0;
}

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