Submission #442283

#	Time	Username	Problem	Language	Result	Execution time	Memory
442283		minoum	Drvca (COCI19_drvca)	C++17	0 / 110	33 ms	2752 KiB

drvca

#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 = abs(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 = abs(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 = abs(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&&abs(a[pt]-y.back())!=dify) return false;
	if(dif[pt]!=-1&&abs(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==abs(a[pt]-x.back())){
			x.push_back(a[pt]); pt++;
			continue;
		}
		if((int)y.size()>=2&&dify!=abs(a[pt]-y.back())) return;
		if(!y.empty()) dify = abs(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-1] = -1;
	dif[n-2] = abs(a[n-1]-a[n-2]);
	for(int i = n-3; i>=0; i--){
		good[i] = (good[i+1]&&(dif[i+1]==abs(a[i+1]-a[i])));
		dif[i] = dif[i+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] << '\n';
		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
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30