oj.uz

Submission #362335

# Submission time Handle Problem Language Result Execution time Memory
362335 2021-02-02T17:18:22 Z limabeans Drvca (COCI19_drvca) C++17
0 / 110
 31 ms 2412 KB 
#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();
		}
		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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2408 KB Output is correct
2 Correct 31 ms 2412 KB Output is correct
3 Correct 31 ms 2408 KB Output is correct
4 Correct 31 ms 2284 KB Output is correct
5 Correct 31 ms 2408 KB Output is correct
6 Correct 31 ms 2284 KB Output is correct
7 Correct 31 ms 2408 KB Output is correct
8 Correct 31 ms 2284 KB Output is correct
9 Incorrect 21 ms 1376 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Incorrect 1 ms 364 KB Output isn't correct
10 Halted 0 ms 0 KB -