Submission #442659

#	Time	Username	Problem	Language	Result	Execution time	Memory
442659		Saynaa	Drvca (COCI19_drvca)	C++14	110 / 110	147 ms	7372 KiB

drvca

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
int n, a[MAXN];
multiset< int > all, m1, m2;

bool solve(int d, int mn){
	m1.clear(), m2.clear(), all.clear();
	for(int i = 0; i < n; i ++)
		all.insert(a[i]);
	while( 1 ){
		if( all.empty() || *all.lower_bound(mn) != mn)
			break;
		m1.insert(mn), all.erase(all.lower_bound(mn));
		mn += d;
	}
	if( all.empty()){
		cout << m1.size() - 1 << endl;
		int i = 0;
		for(multiset< int > :: iterator it = m1.begin(); i < m1.size() - 1; it ++, i ++)
			cout << *it << " ";
		cout << endl << 1 << endl;
		cout << *(--m1.end()) << endl;
		return true;
	}
	if( all.size() <= 2){
		cout << m1.size() << endl;
		for(multiset< int > :: iterator it = m1.begin(); it != m1.end(); it ++)
			cout << *it << " ";
		cout << endl << m2.size() << endl;
		for(multiset< int > :: iterator it = m2.begin();it != m2.end(); it ++)
			cout << *it << " ";
		cout << endl;
		return true;
	}
	multiset< int > :: iterator ls = all.end();
	ls --;
	bool ok = false;
	mn = *all.begin();
	d = min(*(++all.begin()) - mn, *(all.rbegin()) - *(--ls));
	while( all.size() ){
		if( *all.lower_bound(mn) != mn){
			if( m1.count(mn)){
				m1.erase(m1.lower_bound(mn));
				m2.insert(mn);
				mn += d;
				ok = true;
				continue;
			}	
			else return false;
		}
		m2.insert(mn);
		all.erase(all.lower_bound(mn));
		mn += d;
	}
	while( ok && *m1.lower_bound(mn) == mn){
		m1.erase(m1.lower_bound(mn));
		m2.insert(mn);
		mn += d;
	}
	if( ok && *m1.lower_bound(mn) == mn) return false;
	if( m1.empty()) return false;
	cout << m1.size() << endl;
	for(multiset< int > :: iterator it = m1.begin(); it != m1.end(); it ++)
		cout << *it << " ";
	cout << endl << m2.size() << endl;
	for(multiset< int > :: iterator it = m2.begin();it != m2.end(); it ++)
		cout << *it << " ";
	cout << endl;
	return true;	
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 0; i < n; i ++)
		cin >> a[i];
	if( n == 2){
		cout << 1 << endl << a[0] << endl;
		cout << 1 << endl << a[1] << endl;
		return 0;
	}
	sort(a, a + n);
	if( solve(a[1] - a[0], a[0]))
		return 0;
	if( solve(a[2] - a[0], a[0]))
		return 0;
	if( solve(a[2] - a[1], a[1]))
		return 0;
	cout << -1 << endl;
	
	return 0;
}

Compilation message (stderr)

drvca.cpp: In function 'bool solve(int, int)':
drvca.cpp:21:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(multiset< int > :: iterator it = m1.begin(); i < m1.size() - 1; it ++, i ++)
      |                                                    ~~^~~~~~~~~~~~~~~

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