Submission #442279

#	Time	Username	Problem	Language	Result	Execution time	Memory
442279		minoum	Drvca (COCI19_drvca)	C++17	0 / 110	33 ms	2756 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 = 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;
}

void tim(){
	ll s = 0;
	for(ll i = 0; i < LLONG_MAX; i++)
		for(ll j = 0; j < LLONG_MAX; j++){
			s += i; s%=(1000000007);
			for(int h = 0; h < 1000; h++) tim();
		}
}


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]:0);
	}
	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();
		//cout << "2222" << endl;
	} 
	if(!done){
		pre3(), ch();
		//cout << "333" << endl;
	} 
	if(!done) cout << -1 << '\n';
	else{
		if((int)x.size()+(int)y.size()!=n) tim();
		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