Submission #439969

#	Time	Username	Problem	Language	Result	Execution time	Memory
439969		hivakarami	Drvca (COCI19_drvca)	C++14	0 / 110	26 ms	708 KiB

drvca

#include<bits/stdc++.h>

 
using namespace std;
 
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>

 
const int N = 1e5 + 5;
const ll inf = 1e9 * 600;
const ll mod = 1e9 + 7;
const int lg = 30;


vector<int> v1, v2;
bool ok[N], mark[N];
int a[N], n;



inline bool solve(int x, int y)
{

	//cout << x << ' ' << y << endl;


	for(int i = 0; i < n; i++)
		mark[i] = false;
	v1.clear();
	v2.clear();		
	
	mark[x] = mark[y] = true;
	int r = a[y] - a[x], last = a[y];
	for(int i = y+1; i < n; i++)
	{
		if(a[i] - last == r)
		{
			mark[i] = true;
			last = a[i];
		}
	}
	
	
	
	//for(int i = 0; i < n; i++)
		//cout << mark[i];
	//cout << endl;
	
	
	r = 0;
	for(int i = 0; i < n; i++)
	{
		if(mark[i])
		{
			v1.pb(a[i]);
			
			if(!ok[i+1])
				continue;
				
			int k = v2.size();	
				
			if(i == n-1)
			{
				for(int j = i+1; j < n; j++)
					v2.pb(a[j]);
				return true;	
			}
			
			if(k == 0)
			{
				for(int j = i+1; j < n; j++)
					v2.pb(a[j]);
				return true;
			}
			
			if(k == 1 && i == n-2)
			{
				for(int j = i+1; j < n; j++)
					v2.pb(a[j]);

				return true;
			}
			
			if(k == 1 && a[n-1] - a[n-2] == a[i+1] - v2[k-1])
			{
				for(int j = i+1; j < n; j++)
					v2.pb(a[j]);
				return true;
			}
			
			if(i == n-2 && a[i+1] - v2[0] == r)
			{
				for(int j = i+1; j < n; j++)
					v2.pb(a[j]);
				return true;
			}
			
			
			if(r == a[n-1] - a[n-2] && r == a[i+1] - v2[k-1])
			{
				for(int j = i+1; j < n; j++)
					v2.pb(a[j]);
				return true;
			}
			
		}
		else
		{
			v2.pb(a[i]);
			int k = v2.size();
			if(k == 2)
				r = v2[1] - v1[0];
			if(k >= 2 && v2[k-1] - v2[k-2] != r)
				return false;
		}
	}	
	

	return false;

}



inline void print()
{
	
	cout << v1.size() << endl;
	for(auto it : v1)
		cout << it << ' ';
	cout << endl;
	
	
	cout << v2.size() << endl;
	for(auto it : v2)
		cout << it << ' ';
	cout << endl;
}




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);
	
	ok[n] = ok[n-1] = ok[n-2] = true;
	for(int i = n-3; i >= 0; i--)
	{
		if(a[i+2] - a[i+1] == a[i+1] - a[i])
			ok[i] = true;
		else
			break;
	}
	
	/*
	for(int i = 0; i < n; i++)
		cout << ok[i];
	cout << endl;
	//*/
	
			
	if(solve(0, 1))
	{
		print();
		
	}
	else if(solve(0, 2))
	{
		print();
	}
	else if(solve(1, 2))	
	{
		print();
		
	}
	else
	{
		cout << -1 << endl;
	}




	return 0;
}

 

 

 
 

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