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;
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
const int N = 1e5 + 5;
const ll inf = 1e9 * 600;
const ll mod = 1e9 + 7;
const int lg = 30;
vector<int> v1, v2;
bool ok[N], mark[N];
int a[N], n;
inline bool solve(int x, int y)
{
//cout << x << ' ' << y << endl;
for(int i = 0; i < n; i++)
mark[i] = false;
v1.clear();
v2.clear();
mark[x] = mark[y] = true;
int r = a[y] - a[x], last = a[y];
for(int i = y+1; i < n; i++)
{
if(a[i] - last == r)
{
mark[i] = true;
last = a[i];
}
}
//for(int i = 0; i < n; i++)
//cout << mark[i];
//cout << endl;
r = 0;
for(int i = 0; i < n; i++)
{
if(mark[i])
{
v1.pb(a[i]);
if(!ok[i+1])
continue;
int k = v2.size();
if(i == n-1)
{
for(int j = i+1; j < n; j++)
v2.pb(a[j]);
return true;
}
if(k == 0)
{
for(int j = i+1; j < n; j++)
v2.pb(a[j]);
return true;
}
if(k == 1 && i == n-2)
{
for(int j = i+1; j < n; j++)
v2.pb(a[j]);
return true;
}
if(k == 1 && a[n-1] - a[n-2] == a[i+1] - v2[k-1])
{
for(int j = i+1; j < n; j++)
v2.pb(a[j]);
return true;
}
if(i == n-2 && a[i+1] - v2[0] == r)
{
for(int j = i+1; j < n; j++)
v2.pb(a[j]);
return true;
}
if(r == a[n-1] - a[n-2] && r == a[i+1] - v2[k-1])
{
for(int j = i+1; j < n; j++)
v2.pb(a[j]);
return true;
}
}
else
{
v2.pb(a[i]);
int k = v2.size();
if(k == 2)
r = v2[1] - v1[0];
if(k >= 2 && v2[k-1] - v2[k-2] != r)
return false;
}
}
return false;
}
inline void print()
{
cout << v1.size() << endl;
for(auto it : v1)
cout << it << ' ';
cout << endl;
cout << v2.size() << endl;
for(auto it : v2)
cout << it << ' ';
cout << endl;
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
sort(a, a+n);
ok[n-1] = ok[n-2] = true;
for(int i = n-3; i >= 0; i--)
{
if(a[i+2] - a[i+1] == a[i+1] - a[i])
ok[i] = true;
else
break;
}
/*
for(int i = 0; i < n; i++)
cout << ok[i];
cout << endl;
//*/
if(solve(0, 1))
{
print();
}
else if(solve(0, 2))
{
print();
}
else if(solve(1, 2))
{
print();
}
else
{
cout << -1 << endl;
}
return 0;
}
# | 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... |