제출 #671753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
671753		Nimbostratus	Drvca (COCI19_drvca)	C++17	110 / 110	236 ms	12188 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 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());
	}
}

bool trav(int i, int j) {
	s1.clear();
	s2.clear();
	sd.clear();
	for(int pos = 0; pos < n; pos++) {
		if(pos > 0 && pos != i && pos - 1 != i)
			sd.insert(a[pos] - a[pos - 1]);
		else if(pos > 1 && pos != i && pos - 1 == i)
			sd.insert(a[pos] - a[pos - 2]);
		if(pos == i)
			s1.insert(a[pos]);
		else
			s2.insert(a[pos]);
	}
	int d = a[j] - a[i];
	for(int k = 2, curr; k <= n; k++) {
		curr = a[i] + (k - 1) * d;
		auto it = s2.find(curr);
		if(it == s2.end())
			return false;
		int prv = 0, nxt = 0;
		if(it != s2.begin()) {
			prv = *prev(it);
			sd.erase(sd.find(curr - prv));
		}
		it++;
		if(it != s2.end()) {
			nxt = *it;
			sd.erase(sd.find(nxt - curr));
		}
		it--;
		if(prv && nxt)
			sd.insert(nxt - prv);
		s2.erase(it);
		s1.insert(curr);
		if(*sd.begin() == *sd.rbegin())
			return true;
	}
	return false;
}

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;
	}
	if(trav(0, 1)) {
		print();
		return 0;
	}
	if(trav(0, 2)) {
		print();
		return 0;
	}
	if(trav(1, 2)) {
		print();
		return 0;
	}
	cout << -1 << endl;
}

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