# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1258082 | _rain_ | Drvca (COCI19_drvca) | C++20 | 17 ms | 2372 KiB |
#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];
bool 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;
}
bool check(int id1 , int id2){
vector<int>v;
for(int i = 1; i <= n; ++i) mark[i] = false;
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(auto& id : v) mark[id] = true;
vector<int>nxt;
for(int i = 1; i <= n; ++i) if (!mark[i]) nxt.push_back(i);
bool ok = check_possible(nxt);
if (ok){
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 ok;
}
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;
cout << -1;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |