oj.uz

Submission #442271

# Submission time Handle Problem Language Result Execution time Memory
442271 2021-07-07T11:10:26 Z minoum Drvca (COCI19_drvca) C++17
0 / 110
 33 ms 3780 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

const int MAXN = 1e5+10;

int n, a[MAXN], dif[MAXN];
bool good[MAXN], done = false;

vector <int> x, y;
int pt, difx, dify;

inline void pre1(){
	x.clear(); y.clear();
	x.push_back(a[0]); x.push_back(a[1]);
	pt = 2; difx = a[1]-a[0]; dify = 0;
	return;
}

inline void pre2(){
	x.clear(); y.clear();
	x.push_back(a[0]); y.push_back(a[1]); x.push_back(a[2]);
	pt = 3; difx = a[2]-a[0]; dify = 0;
	return;
}

inline void pre3(){
	x.clear(); y.clear();
	y.push_back(a[0]); x.push_back(a[1]); x.push_back(a[2]);
	pt = 3; difx = a[2]-a[1]; dify = 0;
	return;
}

inline bool ok(){
	if(!good[pt]) return false;
	if(y.empty()) return true;
	if((int)y.size()>=2&&a[pt]-y.back()!=dify) return false;
	if(pt<n-1&&a[pt]-y.back()!=dif[pt]) return false;
	return true;
}

inline void ch(){
	if(pt>=n){
		done = true;
		return;
	}
	while(pt<n){
		if(ok()){
			done = true;
			for(int i = pt; i < n; i++) y.push_back(a[i]);
			return;
		}
		if(difx==a[pt]-x.back()){
			x.push_back(a[pt]); pt++;
			continue;
		}
		if((int)y.size()>=2&&dify!=a[pt]-y.back()) return;
		if(!y.empty()) dify = a[pt]-y.back();
		y.push_back(a[pt]); pt++;
	}
	return;
}



int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	sort(a, a+n);
	good[n-1] = good[n-2] = true;
	dif[n-2] = a[n-1]-a[n-2];
	for(int i = n-3; i>=0; i--){
		good[i] = good[i+1]&&(dif[i+1]==(a[i+1]-a[i]));
		dif[i] = (good[i]?dif[i+1]:-1);
	}
	if(good[0]){
		cout << n-1 << '\n';
		for(int i = 0; i < n-1; i++) cout << a[i] << " ";
		cout << '\n' << 1 << '\n' << a[n-1] << endl;
		return 0;
	}
	pre1(); ch();
	if(!done) pre2(), ch();
	if(!done) pre3(), ch();
	if(!done) cout << -1 << '\n';
	else{
		cout << (int)x.size() << '\n';
		for(int i: x) cout <<i << " ";
		cout << '\n' << (int)y.size() << '\n';
		for(int i: y) cout << i << " ";
		cout << '\n';
	}
	return 0; 
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3728 KB Output is correct
2 Correct 33 ms 3612 KB Output is correct
3 Correct 32 ms 3780 KB Output is correct
4 Correct 32 ms 3640 KB Output is correct
5 Incorrect 22 ms 2716 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -