Submission #1264863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264863		goulthen	Drvca (COCI19_drvca)	C++20	110 / 110	122 ms	11972 KiB

drvca

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define fi first
#define se second

const int MAXN = 1e5 + 10;
const int INF = 1e18+10;
int a[MAXN], dif[MAXN], n;

void check(int x, int y) {
	multiset<int> s, dif;
	int k = y-x;
	rep(i,1,n) s.insert(a[i]);
	s.erase(s.find(x));
	s.erase(s.find(y));

	vector<int> ans;
	ans.pb(x); ans.pb(y);

	int last = -1;
	for (auto &v : s) {
		if (last != -1) dif.insert(v-last);
		last = v;
	}

	int tmp = y + k;
	do {
		if (*dif.begin() == *dif.rbegin()) {
			cout << ans.size() << '\n';
			for (int &v : ans) cout << v << " ";
			cout << '\n' << s.size() << '\n';
			for (auto &v : s) cout << v << " ";
			cout << '\n';	
	      exit(0);  
	    }

	    auto it = s.find(tmp);
	    if (it == s.end()) break;
	    auto l = it, r = it;

	    if (it != s.begin()) {
	    	l--;
	    	dif.erase(dif.find(*it-*l));
	    }
	    if (++r != s.end()) {
	    	dif.erase(dif.find(*r-*it));
	    	if (it != s.begin()) dif.insert(*r-*l); 
	    }

	    s.erase(it);
	    ans.pb(tmp);
	    tmp += k;
	} while ((int)ans.size() < n);
}

int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	rep(i,1,n) cin >> a[i];
	sort(a+1, a+n+1);
	
	if (n==2) {
		cout << "1\n" << a[1] << '\n' << "1\n" << a[2] << '\n';
		return 0;
	}
	if (n <= 4) {
		cout << "2\n";
		rep(i,1,2) cout << a[i] << " \n"[i==2];
		cout << n-2 << '\n';
		rep(i,3,n) cout << a[i] << " \n"[i==n];
		return 0;
	}

	check(a[1], a[2]);
	check(a[1], a[3]);
	check(a[2], a[3]);

	cout << "-1\n";
	return 0;
}

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