oj.uz

Submission #439612

# Submission time Handle Problem Language Result Execution time Memory
439612 2021-06-30T10:54:08 Z negar_a Drvca (COCI19_drvca) C++14
0 / 110
 43 ms 3156 KB 
//!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] == 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;
	}
	return false;
}

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 << d[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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 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 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3156 KB Output is correct
2 Correct 38 ms 3060 KB Output is correct
3 Correct 33 ms 3116 KB Output is correct
4 Correct 43 ms 3108 KB Output is correct
5 Incorrect 22 ms 2120 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 332 KB Output isn't correct
2 Halted 0 ms 0 KB -