Submission #362336

#	Time	Username	Problem	Language	Result	Execution time	Memory
362336		limabeans	Drvca (COCI19_drvca)	C++17	0 / 110	35 ms	2408 KiB

drvca

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;




bool valid(vector<int> a) {
    //if (a.empty()) return false;
    if ((int)a.size()<=2) return true;
    int gap = a[1]-a[0];
    for (int i=1; i<(int)a.size(); i++) {
	if (gap!=a[i]-a[i-1]) return false;
    }
    return true;
}

int n;
vector<int> a;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    a.resize(n);
    for (int i=0; i<n; i++) {
	cin>>a[i];
    }

    sort(a.begin(), a.end());

    if (n<=4) {
	for (int mask=0; mask<1<<n; mask++) {
	    vector<int> v, w;
	    for (int i=0; i<n; i++) {
		if (mask>>i&1) {
		    v.push_back(a[i]);
		} else {
		    w.push_back(a[i]);
		}
	    }
	    if (v.empty()) continue;
	    if (w.empty()) continue;
	    
	    if (valid(v) && valid(w)) {
		cout<<v.size()<<endl;
		for (int x: v) cout<<x<<" ";
		cout<<endl;
		cout<<w.size()<<endl;
		for (int x: w) cout<<x<<" ";
		cout<<endl;
		return 0;
	    }
	}

	out(-1);
    }


    for (int mask=0; mask<16; mask++) {
	vector<int> v, w;
	for (int i=0; i<4; i++) {
	    if (mask>>i&1) {
		v.push_back(a[i]);
	    } else {
		w.push_back(a[i]);
	    }
	}
	if (valid(v) && valid(w)) {

	    /*cout<<"TEST"<<endl;
	    cout<<v.size()<<endl;
	    for (int x: v) cout<<x<<" ";
	    cout<<endl;
	    cout<<w.size()<<endl;
	    for (int x: w) cout<<x<<" ";
	    cout<<endl;
	    cout<<"..."<<endl;*/
	    
	    bool ok = true;
	    for (int i=4; i<n && ok; i++) {
		if (v.size()<w.size()) {
		    swap(v,w);
		}
		assert((int)v.size()>=2);
		if (a[i]-v.back()==v[1]-v[0]) {
		    v.push_back(a[i]);
		} else {
		    if ((int)w.size()<=1) {
			w.push_back(a[i]);
		    } else if (a[i]-w.back()==w[1]-w[0]) {
			w.push_back(a[i]);
		    } else {
			ok = false;
		    }
		}
	    }

	    if (ok) {
		if (v.size()<w.size()) {
		    swap(v,w);
		}
		if (w.empty()) {
		    w.push_back(v.back());
		    v.pop_back();
		}

		assert(int(v.size()+w.size())==n);
		cout<<v.size()<<endl;
		for (int x: v) cout<<x<<" ";
		cout<<endl;
		cout<<w.size()<<endl;
		for (int x: w) cout<<x<<" ";
		cout<<endl;
		return 0;
	    }
	}
    }

    out(-1);
    
    
    return 0;
}

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