Submission #439627

#	Time	Username	Problem	Language	Result	Execution time	Memory
439627		negar_a	Drvca (COCI19_drvca)	C++14	110 / 110	45 ms	3160 KiB

drvca

//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 1e5 + 5;
int n, a[maxn], d[maxn];
bool mark[maxn];

void output(int c){
	cout << c << endl;
	for(int i = 0; i < n; i ++){
		if(mark[i]){
			cout << a[i] << " ";
		}
	}
	cout << endl << n - c << endl;
	for(int i = 0; i < n; i ++){
		if(!mark[i]){
			cout << a[i] << " ";
		}
	}
	return;
}

bool solve(int x, int tar){
	int t = -2, t2 = -2, last = -1;
	int c = 2;
	for(int i = 0; i < n; i ++){
//		cout << x << " " << tar << " " << t << " " << t2 << " " << last << " " << c << endl;
		if(mark[i]){
			continue;
		}
		if(a[i] == t2){
			t2 += t;
			if(d[i] == t || d[i] == -2){
				output(c);
				return true;
			}
		}
		else if(a[i] == tar){
			tar += x;
			mark[i] = true;
			c ++;
		}
		else{
			if(t == -2){
				t ++;
				last = a[i];
			}
			else if(t == -1){
				t = a[i] - last;
				t2 = a[i] + t;
				if(d[i] == t || d[i] == -2){
					output(c);
					return true;
				}
			}
			else if(a[i] != t2){
//				cout << "why? " << i << endl;
				return false;
			}
			else{
				t2 += t;
				if(d[i] == t || d[i] == -2){
					output(c);
					return true;
				}
			}
		}
	}
	if(c == n){
		cout << n - 1 << endl;
		for(int i = 0; i < n - 1; i ++){
			cout << a[i] << " ";
		}
		cout << endl << 1 << endl;
		cout << a[n - 1];
		return true;
	}
	output(c);
	return true;
}

int main(){
	fast_io;
	cin >> n;
	for(int i = 0; i < n; i ++){
		cin >> a[i];
	}
	sort(a, a + n);
	d[n - 2] = a[n - 1] - a[n - 2];
	for(int i = n - 3; i >= 0; i --){
		if(a[i] == a[i + 1] - d[i + 1]){
			d[i] = d[i + 1];
		}else{
			d[i] = -1;
		}
	}
	d[n - 1] = -2;
//	cout << "d : ";
//	for(int i = 0; i < n; i ++){
//		cout << a[i] << " ";
//	}
//	cout << endl;
	memset(mark, false, sizeof mark);
	mark[0] = mark[1] = true;
	if(solve(a[1] - a[0], a[1] + (a[1] - a[0]))){
		return 0;	
	}
	memset(mark, false, sizeof mark);
	mark[0] = mark[2] = true;
	if(solve(a[2] - a[0], a[2] + (a[2] - a[0]))){
		return 0;	
	}
	memset(mark, false, sizeof mark);
	mark[1] = mark[2] = true;
	if(solve(a[2] - a[1], a[2] + (a[2] - a[1]))){
		return 0;	
	}
	cout << -1;
	
	return 0;
}

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