Submission #1258113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258113		_rain_	Drvca (COCI19_drvca)	C++20	110 / 110	20 ms	3140 KiB

drvca

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

#define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define BIT(maks , x) (((mask) >> (x)) & (1))
#define MASK(x) ((LL)(1)<<(x))

template<class X,class Y>
	bool maximize(X &x , Y y){
		if (x < y) return x = y , true; else return false;
	}
template<class X,class Y>
	bool minimize(X &x,Y y){
		if (x > y) return x = y , true; else return false;
	}

const int N = (int) 1e5;
	int h[N + 2];
	int mark[N + 2] = {};
	int n;
	
	bool check_possible(vector<int>&data){
		if (data.size() < 3) return true;
		for(int i = 2; i < data.size(); ++i) if (h[data[i]] - h[data[i - 1]] != h[data[i - 1]] - h[data[i - 2]]) return false;
		return true;
	}
	
	void print(vector<int>v , vector<int>nxt){
		if (nxt.size() == 0) nxt.push_back(v.back()) , v.pop_back();
		cout << nxt.size() << '\n';
		for(auto& x : nxt) cout << h[x] << ' '; cout << '\n';
		cout << v.size() << '\n';
		for(auto& x : v) cout << h[x] << ' '; cout << '\n';
		return;
	}
	
	bool check(int id1 , int id2){
		vector<int>v , nxt;
			for(int i = 1; i <= n; ++i) mark[i] = -1;
			v.push_back(id1) , v.push_back(id2);
			int cur_sz = 1;
			for(int i = id2 + 1; i <= n; ++i) {
				if (h[i] - h[v[cur_sz]] == h[v[cur_sz]] - h[v[cur_sz - 1]]) {
					v.push_back(i);
					++cur_sz;
				}
			}
			for(int i = 0; i < v.size(); ++i) mark[v[i]] = i + 1;
			for(int i = 1; i <= n; ++i){
				if (mark[i]!=-1) continue;
				if (nxt.size() < 2) nxt.push_back(i) , mark[i] = 0;
				else{
					if (h[i] - h[nxt.back()] == h[nxt.back()] - h[nxt[nxt.size() - 2]]){
						nxt.push_back(i); 
						mark[i] = 0;
					}
				}
			}
			
			bool ok = true;
			for(int i = 1; i <= n; ++i) if (mark[i]==-1) ok = false;
			if (ok){
				print(v,nxt);
				return true;
			}
	
			while (v.size() && nxt.size() && v.back() > nxt.back()) {
				mark[v.back()] = -1;
				v.pop_back();
			}
			
			int t;
			
			t = (nxt.size() ? nxt.back() : 0);
			
			for(int i = t + 1; i <= n; ++i){
				if (mark[i]!=-1) continue;
				if (nxt.size() < 2) nxt.push_back(i) , mark[i] = 0;
				else{
					if (h[i] - h[nxt.back()] == h[nxt.back()] - h[nxt[nxt.size() - 2]]){
						nxt.push_back(i); 
						mark[i] = 0;
					}
				}
			}
			
			t = (v.size() ? v.back() : 0);
//			
			for(int i = t + 1; i <= n; ++i){
				if (mark[i]!=-1) continue;
				if (v.size() < 2) nxt.push_back(i) , mark[i] = 0;
				else{
					if (h[i] - h[v.back()] == h[v.back()] - h[v[v.size() - 2]]){
						v.push_back(i); 
						mark[i] = 0;
					}
				}
			}
		for(int i = 1; i <= n; ++i) if (mark[i]==-1) return false;
		print(v,nxt);
		return true;
	}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n;
		for(int i = 1; i <= n; ++i) cin >> h[i];
		sort(h+1,h+n+1);
//		for(int i = 1; i <= n; ++i) cout << h[i] << ' '; cout << '\n';
		if (check(1,2)) return 0;
		if (check(1,3)) return 0;
		if (check(2,3)) return 0;
//		if (n > 3 && check(2,4)) return 0;
		cout << -1;
	return 0;
}

Compilation message (stderr)

drvca.cpp: In function 'int main()':
drvca.cpp:110:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
drvca.cpp:111:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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