oj.uz

Submission #439621

# Submission time Handle Problem Language Result Execution time Memory
439621 2021-06-30T11:29:48 Z negar_a Drvca (COCI19_drvca) C++14
0 / 110
 42 ms 3140 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;
	}
	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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 1 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 1 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2064 KB Output is correct
2 Correct 31 ms 2084 KB Output is correct
3 Correct 32 ms 2124 KB Output is correct
4 Correct 36 ms 2168 KB Output is correct
5 Correct 34 ms 2112 KB Output is correct
6 Correct 33 ms 3140 KB Output is correct
7 Correct 33 ms 3112 KB Output is correct
8 Correct 42 ms 3116 KB Output is correct
9 Correct 29 ms 2536 KB Output is correct
10 Incorrect 23 ms 2088 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 1 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -