| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 765690 | 1075508020060209tc | Drvca (COCI19_drvca) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}