Submission #202649

#	Time	Username	Problem	Language	Result	Execution time	Memory
202649		SorahISA	Drvca (COCI19_drvca)	C++17	80 / 110	42 ms	4084 KiB

drvca

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

#define int long long
#define double long double

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

int32_t main() {
    fastIO();
    
    int n, diffA, diffB, fl, as, bs;
    cin >> n;
    
    vector<int> v(n), A, B;
    for (auto &x : v) cin >> x;
    sort(v.begin(), v.end());
    
    if (n == 2) {
        cout << 1 << "\n";
        cout << v[0] << "\n";
        cout << 1 << "\n";
        cout << v[1] << "\n";
        return 0;
    }
    
    /// for subtask 3 : ans.len == N/2 ///
    
    if (n > 300) {
        /// A, A, ... ///
        A.clear(), B.clear();
        diffA = v[1] - v[0];
        A.push_back(v[0]);
        A.push_back(v[1]);
        for (int i = 2; i < n; ++i) {
            if (v[i] - *prev(A.end()) == diffA and A.size() < n/2) {
                A.push_back(v[i]);
            }
            else {
                B.push_back(v[i]);
            }
        }
        
        fl = 1;
        as = A.size(), bs = B.size();
        if (bs >= 2) diffB = B[1] - B[0];
        for (int i = 2; i < bs; ++i) {
            if (B[i] - B[i - 1] != diffB) {fl = 0; break;}
        }
        
        if (fl) {
            if (bs == 0) {
                cout << as - 1 << "\n";
                for (int i = 1; i < as; ++i) cout << A[i] << " \n"[i == as-1];
                cout << 1 << "\n";
                cout << A[0] << "\n";
            }
            else {
                cout << as << "\n";
                for (int i = 0; i < as; ++i) cout << A[i] << " \n"[i == as-1];
                cout << bs << "\n";
                for (int i = 0; i < bs; ++i) cout << B[i] << " \n"[i == bs-1];
            }
            return 0;
        }
        
        /// A, B, A, ... ///
        swap(v[1], v[2]);
        
        A.clear(), B.clear();
        diffA = v[1] - v[0];
        A.push_back(v[0]);
        A.push_back(v[1]);
        B.push_back(v[2]);
        for (int i = 3; i < n; ++i) {
            if (v[i] - *prev(A.end()) == diffA and A.size() < n/2) {
                A.push_back(v[i]);
            }
            else {
                B.push_back(v[i]);
            }
        }
        
        fl = 1;
        as = A.size(), bs = B.size();
        if (bs >= 2) diffB = B[1] - B[0];
        for (int i = 2; i < bs; ++i) {
            if (B[i] - B[i - 1] != diffB) {fl = 0; break;}
        }
        
        if (fl) {
            if (bs == 0) {
                cout << as - 1 << "\n";
                for (int i = 1; i < as; ++i) cout << A[i] << " \n"[i == as-1];
                cout << 1 << "\n";
                cout << A[0] << "\n";
            }
            else {
                cout << as << "\n";
                for (int i = 0; i < as; ++i) cout << A[i] << " \n"[i == as-1];
                cout << bs << "\n";
                for (int i = 0; i < bs; ++i) cout << B[i] << " \n"[i == bs-1];
            }
            return 0;
        }
        
        swap(v[1], v[2]);
        
        /// A, B, B, ... ///
        swap(v[0], v[1]); swap(v[1], v[2]);
        
        A.clear(), B.clear();
        diffA = v[1] - v[0];
        A.push_back(v[0]);
        A.push_back(v[1]);
        B.push_back(v[2]);
        for (int i = 3; i < n; ++i) {
            if (v[i] - *prev(A.end()) == diffA and A.size() < n/2) {
                A.push_back(v[i]);
            }
            else {
                B.push_back(v[i]);
            }
        }
        
        fl = 1;
        as = A.size(), bs = B.size();
        if (bs >= 2) diffB = B[1] - B[0];
        for (int i = 2; i < bs; ++i) {
            if (B[i] - B[i - 1] != diffB) {fl = 0; break;}
        }
        
        if (fl) {
            if (bs == 0) {
                cout << as - 1 << "\n";
                for (int i = 1; i < as; ++i) cout << A[i] << " \n"[i == as-1];
                cout << 1 << "\n";
                cout << A[0] << "\n";
            }
            else {
                cout << as << "\n";
                for (int i = 0; i < as; ++i) cout << A[i] << " \n"[i == as-1];
                cout << bs << "\n";
                for (int i = 0; i < bs; ++i) cout << B[i] << " \n"[i == bs-1];
            }
            return 0;
        }
        
        swap(v[1], v[2]); swap(v[0], v[1]);
        
        /// No answer found ///
        cout << -1 << "\n";
        
        return 0;
    }
    
    /// for subtask 1,2 : N <= 300 ///
    
    for (int mi = n; mi >= 1; --mi) {
    
        /// A, A, ... ///
        A.clear(), B.clear();
        diffA = v[1] - v[0];
        A.push_back(v[0]);
        A.push_back(v[1]);
        for (int i = 2; i < n; ++i) {
            if (v[i] - *prev(A.end()) == diffA and A.size() < mi) {
                A.push_back(v[i]);
            }
            else {
                B.push_back(v[i]);
            }
        }
        
        fl = 1;
        as = A.size(), bs = B.size();
        if (bs >= 2) diffB = B[1] - B[0];
        for (int i = 2; i < bs; ++i) {
            if (B[i] - B[i - 1] != diffB) {fl = 0; break;}
        }
        
        if (fl) {
            if (bs == 0) {
                cout << as - 1 << "\n";
                for (int i = 1; i < as; ++i) cout << A[i] << " \n"[i == as-1];
                cout << 1 << "\n";
                cout << A[0] << "\n";
            }
            else {
                cout << as << "\n";
                for (int i = 0; i < as; ++i) cout << A[i] << " \n"[i == as-1];
                cout << bs << "\n";
                for (int i = 0; i < bs; ++i) cout << B[i] << " \n"[i == bs-1];
            }
            return 0;
        }
        
        /// A, B, A, ... ///
        swap(v[1], v[2]);
        
        A.clear(), B.clear();
        diffA = v[1] - v[0];
        A.push_back(v[0]);
        A.push_back(v[1]);
        B.push_back(v[2]);
        for (int i = 3; i < n; ++i) {
            if (v[i] - *prev(A.end()) == diffA and A.size() < mi) {
                A.push_back(v[i]);
            }
            else {
                B.push_back(v[i]);
            }
        }
        
        fl = 1;
        as = A.size(), bs = B.size();
        if (bs >= 2) diffB = B[1] - B[0];
        for (int i = 2; i < bs; ++i) {
            if (B[i] - B[i - 1] != diffB) {fl = 0; break;}
        }
        
        if (fl) {
            if (bs == 0) {
                cout << as - 1 << "\n";
                for (int i = 1; i < as; ++i) cout << A[i] << " \n"[i == as-1];
                cout << 1 << "\n";
                cout << A[0] << "\n";
            }
            else {
                cout << as << "\n";
                for (int i = 0; i < as; ++i) cout << A[i] << " \n"[i == as-1];
                cout << bs << "\n";
                for (int i = 0; i < bs; ++i) cout << B[i] << " \n"[i == bs-1];
            }
            return 0;
        }
        
        swap(v[1], v[2]);
        
        /// A, B, B, ... ///
        swap(v[0], v[1]); swap(v[1], v[2]);
        
        A.clear(), B.clear();
        diffA = v[1] - v[0];
        A.push_back(v[0]);
        A.push_back(v[1]);
        B.push_back(v[2]);
        for (int i = 3; i < n; ++i) {
            if (v[i] - *prev(A.end()) == diffA and A.size() < mi) {
                A.push_back(v[i]);
            }
            else {
                B.push_back(v[i]);
            }
        }
        
        fl = 1;
        as = A.size(), bs = B.size();
        if (bs >= 2) diffB = B[1] - B[0];
        for (int i = 2; i < bs; ++i) {
            if (B[i] - B[i - 1] != diffB) {fl = 0; break;}
        }
        
        if (fl) {
            if (bs == 0) {
                cout << as - 1 << "\n";
                for (int i = 1; i < as; ++i) cout << A[i] << " \n"[i == as-1];
                cout << 1 << "\n";
                cout << A[0] << "\n";
            }
            else {
                cout << as << "\n";
                for (int i = 0; i < as; ++i) cout << A[i] << " \n"[i == as-1];
                cout << bs << "\n";
                for (int i = 0; i < bs; ++i) cout << B[i] << " \n"[i == bs-1];
            }
            return 0;
        }
        
        swap(v[1], v[2]); swap(v[0], v[1]);
    }
    
    /// No answer found ///
    cout << -1 << "\n";
    
    return 0;
}

Compilation message (stderr)

drvca.cpp: In function 'int32_t main()':
drvca.cpp:36:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (v[i] - *prev(A.end()) == diffA and A.size() < n/2) {
                                                    ~~~~~~~~~^~~~~
drvca.cpp:76:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (v[i] - *prev(A.end()) == diffA and A.size() < n/2) {
                                                    ~~~~~~~~~^~~~~
drvca.cpp:118:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (v[i] - *prev(A.end()) == diffA and A.size() < n/2) {
                                                    ~~~~~~~~~^~~~~
drvca.cpp:167:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (v[i] - *prev(A.end()) == diffA and A.size() < mi) {
                                                    ~~~~~~~~~^~~~
drvca.cpp:207:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (v[i] - *prev(A.end()) == diffA and A.size() < mi) {
                                                    ~~~~~~~~~^~~~
drvca.cpp:249:61: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (v[i] - *prev(A.end()) == diffA and A.size() < mi) {
                                                    ~~~~~~~~~^~~~

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