| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 765690 | 1075508020060209tc | Drvca (COCI19_drvca) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;
int ar[200005];
int tar[200005];
int sfok[200005];
int chk(vector<int>A){
for(int i=1;i<A.size();i++){
if(A[i]-A[i-1]!=A[1]-A[0]){
return 0;
}
}
return 1;
}
void ot(vector<int>pl){
vector<int>A;
vector<int>B;
for(int i=1;i<=n;i++){
tar[i]=0;
}
for(int i=0;i<pl.size();i++){
tar[pl[i]]=1;
}
for(int i=1;i<=n;i++){
if(tar[pl[i]]==1){
A.push_back(ar[i]);
}else{
B.push_back(ar[i]);
}
}
if(chk(A)&&chk(B)){
if(B.size()==0){
B.push_back(ar[n]);
A.pop_back();
}
}
cout<<A.size()<<endl;
for(int i=0;i<A.size();i++){
cout<<A[i]<<" ";
}cout<<endl;
cout<<B.size()<<endl;
for(int i=0;i<B.size();i++){
cout<<B[i]<<" ";
}cout<<endl;
exit(0);
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>ar[i];
}
if(n==2){
cout<<"1\n";
cout<<ar[1]<<endl;
cout<<"1\n";
cout<<ar[2]<<endl;return 0;
}
sort(ar+1,ar+n+1);
sfok[n]=1;
for(int i=n-1;i>=1;i--){
if(ar[i]-ar[i+1]!=ar[n-1]-ar[n]){
break;
}
sfok[i]=1;
}
vector<int>A;
vector<int>B;
A.clear();B.clear();
A.push_back(1);
A.push_back(2);
ot(A);
for(int i=3;i<=n;i++){
if(ar[i]-ar[A.back()]==ar[2]-ar[1]){
A.push_back(i);
ot(i);
}
}
A.clear();
A.push_back(1);
A.push_back(3);
ot(A);
for(int i=4;i<=n;i++){
if(ar[i]-ar[A.back()]==ar[3]-ar[1]){
A.push_back(i);
ot(i);
}
}
A.clear();
A.push_back(2);
A.push_back(3);
ot(A);
for(int i=4;i<=n;i++){
if(ar[i]-ar[A.back()]==ar[3]-ar[2]){
A.push_back(i);
ot(i);
}
}
cout<<-1<<endl;
}