Submission #291927

#	Time	Username	Problem	Language	Result	Execution time	Memory
291927		penguinhacker	Drvca (COCI19_drvca)	C++17	0 / 110	1067 ms	3144 KiB

drvca

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

#define ll long long
#define ar array

const int mxN=1e5;
int n, h[mxN];
vector<int> ans[2];

bool chk(vector<int>& v) {
	if (v.size()<3) return 1;
	return v[1]-v[0]==v.back()-v[v.size()-2];
}

void solve(int x) {
	ans[1].clear();
	ans[0]={h[0], h[x]};
	for (int i=1; i<x; ++i) {
		ans[1].push_back(h[i]);
		if (!chk(ans[1])) {
			cout << "-1\n";
			exit(0);
		}
	}
	int d=h[x]-h[0];
	for (int i=x+1; i<n; ++i) {
		if (h[i]-ans[0].back()==d) {
			ans[0].push_back(h[i]);
		}
		else {
			ans[1].push_back(h[i]);
			if (!chk(ans[1])) return;
		}
	}
	if (ans[0].size()==n) {
		ans[0].pop_back();
		ans[1]={h[n-1]};
	}
	cout << ans[0].size() << "\n";
	for (int i : ans[0]) cout << i << " ";
	cout << "\n";
	cout << ans[1].size() << "\n";
	for (int i : ans[1]) cout << i << " ";
	exit(0);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ans[0].reserve(mxN);
	ans[1].reserve(mxN);
	cin >> n;
	for (int i=0; i<n; ++i) cin >> h[i];
	sort(h, h+n);
	for (int i=1; i<n; ++i) solve(i);
	cout << -1 << "\n";
	return 0;
}

Compilation message (stderr)

drvca.cpp: In function 'void solve(int)':
drvca.cpp:36:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |  if (ans[0].size()==n) {
      |      ~~~~~~~~~~~~~^~~

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