Submission #211749

#	Time	Username	Problem	Language	Result	Execution time	Memory
211749		VEGAnn	Drvca (COCI19_drvca)	C++14	110 / 110	76 ms	4396 KiB

drvca

#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
const int N = 100100;
vector<int> vc, vec;
map<int, int> mp;
int n, a[N], pre[N], net[N], dif, lst;
bool mrk[N];

void check(){
    if (sz(mp) < 2){
        vc.clear();
        vec.clear();
        
        for (int i = 0; i < n; i++)
            if (mrk[i])
                vc.PB(a[i]);
            else vec.PB(a[i]);
            
        cout << sz(vc) << '\n';
        for (int cr : vc)
            cout << cr << " "; cout << '\n';
            
        cout << sz(vec) << '\n';
        for (int cr : vec)
            cout << cr << " "; cout << '\n';
            
        exit(0);
    }
}

void calc(){
    
    int pr = -1;
    mp.clear();
    
    for (int i = 0; i < n; i++){
        if (mrk[i]) continue;
        pre[i] = pr;
        if (pr >= 0)
            mp[a[i] - a[pr]]++;
        pr = i;
    }
    
    pr = n;
    for (int i = n - 1; i >= 0; i--){
        if (mrk[i]) continue;
        net[i] = pr;
        pr = i;
    }
    
    check();
    
    for (int pt = 0; pt < n; ){
        if (mrk[pt]) {
            pt++;
            continue;
        }
            
        int cp = pt;
        
        while (cp < n && dif + lst != a[cp])
            cp++;
        
        if (cp == n) break;
        
        int pr = pre[cp];
        int nt = net[cp];
        
        if (pr >= 0){
            int def = a[cp] - a[pr];
            mp[def]--;
            if (mp[def] == 0)
                mp.erase(mp.find(def));
            net[pr] = nt;
        }
        
        if (nt < n){
            int def = a[nt] - a[cp];
            mp[def]--;
            if (mp[def] == 0)
                mp.erase(mp.find(def));
                
            if (pr >= 0) 
                mp[a[nt] - a[pr]]++;
            pre[nt] = pr;
        }
        
        mrk[cp] = 1;
        lst += dif;
        
        check();
        
        pt = cp + 1;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
        
    sort(a, a + n);
    
    if (n == 2){
        cout << "1\n" << a[0];
        cout << "\n1\n" << a[1];
        return 0;
    }
    
    fill(mrk, mrk + n, 0);
    mrk[0] = mrk[1] = 1;
    dif = a[1] - a[0];
    lst = a[1];
    calc();
    
    fill(mrk, mrk + n, 0);
    mrk[0] = mrk[2] = 1;
    dif = a[2] - a[0];
    lst = a[2];
    calc();
    
    fill(mrk, mrk + n, 0);
    mrk[1] = mrk[2] = 1;
    dif = a[2] - a[1];
    lst = a[2];
    calc();
    
    cout << -1;
    
    return 0;
}

Compilation message (stderr)

drvca.cpp: In function 'void check()':
drvca.cpp:22:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for (int cr : vc)
         ^~~
drvca.cpp:23:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
             cout << cr << " "; cout << '\n';
                                ^~~~
drvca.cpp:26:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
         for (int cr : vec)
         ^~~
drvca.cpp:27:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
             cout << cr << " "; cout << '\n';
                                ^~~~

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