| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 580579 |
2022-06-21T13:06:34 Z |
AGE |
Drvca (COCI19_drvca) |
C++14 |
|
198 ms |
19620 KB |
#include<bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pb push_back
using namespace std;
const int N=1e6,M=2e3,mod=1e9+7;
multiset<int>st,stt;
pair<int,int>ans;
vector<int>v,v2;
map<int,int>mp;
int a[N];
main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
if(n==2){
cout<<1<<endl;
cout<<a[0]<<endl;
cout<<1<<endl;
cout<<a[1]<<endl;
return 0;
}
if(n==3){
cout<<2<<endl;
cout<<a[0]<<" "<<a[1]<<endl;
cout<<1<<endl;
cout<<a[2]<<endl;
return 0;
}
int Final_ans=0;
for(int ii=0;ii<=2;ii++){
if(Final_ans!=0)
break;
for(int jj=ii+1;jj<=2;jj++){
if(Final_ans!=0)
break;
st.clear(),stt.clear();
int x=a[ii];
int y=a[jj];
int diff=y-x;
int lst=y;
for(int i=n-1;i>=0;i--)
if(i!=ii&&i!=jj)
lst=i;
for(int i=0;i<n;i++){
if(i==ii||i==jj)
continue;
st.insert(a[i]);
if(i==lst)
continue;
stt.insert(a[i]-a[lst]);
lst=i;
}
/*for(auto x:st)
cout<<x<<" ";
cout<<endl;
for(auto x:stt)
cout<<x<<" ";
cout<<endl;
cout<<endl;*/
int lst2=y,num=2;
if(*stt.begin()==*st.rbegin())
Final_ans=num,ans.F=ii,ans.S=jj;
for(int i=lst2+diff;i>=1;i+=diff){
//cout<<i<<"!"<<endl;
if(Final_ans)
break;
num++;
if(st.size()==1)
break;
if(st.find(i)==st.end())
break;
int x=i;
auto itt=--st.end();
auto itt2=st.find(i);
if(itt2==itt){
//cout<<"@#"<<endl;
auto it=--st.find(i);
int diff2=(abs(*it-x));
st.erase(st.find(i));
stt.erase(stt.find(diff2));
}
else if(st.find(i)==st.begin()){
auto ittt=++st.find(i);
int diff2=abs((*ittt)-x);
st.erase(st.find(i));
stt.erase(stt.find(diff2));
// cout<<diff2<<endl;
//cout<<"!@!"<<endl;
}
else{
//cout<<"FI"<<endl;
auto it=++st.find(i);
auto it2=--st.find(i);
int diff1=abs(*it-x);
int diff2=abs(*it2-x);
st.erase(st.find(i));
if(stt.size())
stt.erase(stt.find(diff1));
if(stt.size())
stt.erase(stt.find(diff2));
stt.insert(abs(*it-*it2));
}
if(*stt.begin()==*stt.rbegin())
Final_ans=num,ans.F=ii,ans.S=jj;
}
}
}
//cout<<Final_ans<<" "<<ans.F<<" "<<ans.S<<endl;
if(Final_ans==0){
cout<<"-1"<<endl;
return 0;
}
v.pb(a[ans.F]);
v.pb(a[ans.S]);
for(int i=0;i<n;i++)
mp[a[i]]++;
int diff=a[ans.S]-a[ans.F];
for(int i=0;i<Final_ans-2;i++)
v.pb(v[v.size()-1]+diff),mp[v[v.size()-1]]--;
for(int i=0;i<n;i++){
if(i==ans.F||i==ans.S)
continue;
if(mp[a[i]]==0)
continue;
v2.pb(a[i]);
mp[a[i]]--;
}
cout<<v.size()<<endl;
for(int i=0;i<v.size();i++)
cout<<v[i]<<" ";
cout<<endl;
cout<<v2.size()<<endl;
for(int i=0;i<v2.size();i++)
cout<<v2[i]<<" ";
cout<<endl;
return 0;
}
Compilation message
drvca.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
16 | main()
| ^~~~
drvca.cpp: In function 'int main()':
drvca.cpp:206:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
206 | for(int i=0;i<v.size();i++)
| ~^~~~~~~~~
drvca.cpp:211:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
211 | for(int i=0;i<v2.size();i++)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
312 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
308 KB |
Output is correct |
| 9 |
Correct |
1 ms |
308 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
312 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
308 KB |
Output is correct |
| 9 |
Correct |
1 ms |
308 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
18524 KB |
Output is correct |
| 2 |
Correct |
154 ms |
14896 KB |
Output is correct |
| 3 |
Correct |
198 ms |
19600 KB |
Output is correct |
| 4 |
Correct |
157 ms |
14916 KB |
Output is correct |
| 5 |
Correct |
175 ms |
19620 KB |
Output is correct |
| 6 |
Correct |
152 ms |
14920 KB |
Output is correct |
| 7 |
Correct |
187 ms |
19548 KB |
Output is correct |
| 8 |
Correct |
144 ms |
14848 KB |
Output is correct |
| 9 |
Correct |
141 ms |
14580 KB |
Output is correct |
| 10 |
Correct |
162 ms |
15984 KB |
Output is correct |
| 11 |
Incorrect |
90 ms |
13280 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
312 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
308 KB |
Output is correct |
| 9 |
Correct |
1 ms |
308 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
