Submission #671713

#	Time	Username	Problem	Language	Result	Execution time	Memory
671713		Nimbostratus	Drvca (COCI19_drvca)	C++17	0 / 110	123 ms	21192 KiB

drvca

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using lint = long long;
const int maxn = 2e5 + 5;
const int inf = 1e9 + 5;
const int mod = 1e9 + 7;

int n;
int a[maxn];
multiset<int> s1;
multiset<int> s2;
multiset<int> sd;

void init() {
	s1.clear();
	s2.clear();
	sd.clear();
	for(int i = 0; i < n; i++) {
		s2.insert(a[i]);
		if(i > 0)
			sd.insert(a[i] - a[i - 1]);
	}
}

void print() {
	cout << s1.size() << endl;
	while(!s1.empty()) {
		cout << *s1.begin() << " ";
		s1.erase(s1.begin());
	}
	cout << endl;
	cout << s2.size() << endl;
	while(!s2.empty()) {
		cout << *s2.begin() << " ";
		s2.erase(s2.begin());
	}
}

signed main() {
	#ifdef Local
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	sort(a, a + n);
	if(n == 2) {
		cout << 1 << endl << a[0] << endl;
		cout << 1 << endl << a[1] << endl;
		return 0;
	}
	if(n == 3) {
		cout << 1 << endl << a[0] << endl;
		cout << 2 << endl << a[1] << " " << a[2] << endl;
		return 0;
	}
	int d;
	int k;
	//case 01
	init();
	d = a[1] - a[0];
	k = 2;
	s1.insert(a[0]);
	s1.insert(a[1]);
	s2.erase(s2.find(a[0]));
	s2.erase(s2.find(a[1]));
	sd.erase(sd.find(d));
	sd.erase(sd.find(a[2] - a[1]));
	while(true) {
		if(*sd.begin() == *sd.rbegin()) {
			print();
			return 0;
		}
		k++;
		int curr = a[0] + (k - 1) * d;
		s1.insert(curr);
		auto it = s2.find(curr);
		if(it == s2.end())
			break;
		int prv = 0, nxt = 0;
		if(it != s2.begin()) {
			prv = *prev(it);
			sd.erase(curr - prv);
		}
		auto tmp = next(it);
		if(tmp != s2.end()) {
			nxt = *tmp;
			sd.erase(nxt - curr);
		}
		if(nxt && prv)
			sd.insert(nxt - prv);
	}
	//case 02
	init();
	d = a[2] - a[0];
	k = 2;
	s1.insert(a[0]);
	s1.insert(a[2]);
	s2.erase(s2.find(a[0]));
	s2.erase(s2.find(a[2]));
	sd.erase(sd.find(d));
	sd.erase(sd.find(a[3] - a[2]));
	sd.erase(sd.find(a[2] - a[1]));
	sd.erase(sd.find(a[1] - a[0]));
	sd.insert(a[3] - a[1]);
	while(true) {
		if(*sd.begin() == *sd.rbegin()) {
			print();
			return 0;
		}
		k++;
		int curr = a[0] + (k - 1) * d;
		s1.insert(curr);
		auto it = s2.find(curr);
		if(it == s2.end())
			break;
		int prv = 0, nxt = 0;
		if(it != s2.begin()) {
			prv = *prev(it);
			sd.erase(curr - prv);
		}
		auto tmp = next(it);
		if(tmp != s2.end()) {
			nxt = *tmp;
			sd.erase(nxt - curr);
		}
		if(nxt && prv)
			sd.insert(nxt - prv);
	}
	//case 12
	init();
	d = a[2] - a[1];
	k = 2;
	s1.insert(a[1]);
	s1.insert(a[2]);
	s2.erase(s2.find(a[1]));
	s2.erase(s2.find(a[2]));
	sd.erase(sd.find(d));
	sd.erase(sd.find(a[3] - a[2]));
	sd.erase(sd.find(a[1] - a[0]));
	sd.insert(a[3] - a[0]);
	while(true) {
		if(*sd.begin() == *sd.rbegin()) {
			print();
			return 0;
		}
		k++;
		int curr = a[1] + (k - 1) * d;
		s1.insert(curr);
		auto it = s2.find(curr);
		if(it == s2.end())
			break;
		int prv = 0, nxt = 0;
		if(it != s2.begin()) {
			prv = *prev(it);
			sd.erase(curr - prv);
		}
		auto tmp = next(it);
		if(tmp != s2.end()) {
			nxt = *tmp;
			sd.erase(nxt - curr);
		}
		if(nxt && prv)
			sd.insert(nxt - prv);
	}
	cout << -1 << endl;	
}

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