# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1257606 | knhatdev | Drvca (COCI19_drvca) | C++20 | 181 ms | 12104 KiB |
#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define task "noel"
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, a[N];
void check1()
{
int d = a[2] - a[1];
vector<int> v;
multiset<int> val, dis;
v.push_back(a[1]);
v.push_back(a[2]);
int trc = -1;
for(int i = 1; i <= n; i++)
{
if(i == 1 || i == 2) continue;
val.insert(a[i]);
if(trc != -1) dis.insert(a[i] - trc);
trc = a[i];
}
if(val.size() == 1 || (*dis.begin() == *dis.rbegin()))
{
cout << v.size() << '\n';
for(int x : v) cout << x << ' ';
cout << '\n';
cout << val.size() << '\n';
for(int x : val) cout << x << ' ';
exit(0);
}
for(int i = 3; i <= n; i++)
{
int x = v.back() + d;
if(val.find(x) != val.end())
{
v.push_back(x);
val.erase(val.find(x));
auto tmp = val.lower_bound(x);
auto tmp2 = val.lower_bound(x);
if(tmp != val.end())
dis.erase(dis.find(*tmp - x));
if(tmp2 != val.begin())
{
--tmp2;
dis.erase(dis.find(x - *tmp2));
if(tmp != val.end())
dis.insert(*tmp - *tmp2);
}
}
else
{
return;
}
if(val.size() == 1 || (*dis.begin() == *dis.rbegin()))
{
cout << v.size() << '\n';
for(int x : v) cout << x << ' ';
cout << '\n';
cout << val.size() << '\n';
for(int x : val) cout << x << ' ';
exit(0);
}
}
}
void check2()
{
int d = a[3] - a[1];
vector<int> v;
multiset<int> val, dis;
v.push_back(a[1]);
v.push_back(a[3]);
int trc = -1;
for(int i = 1; i <= n; i++)
{
if(i == 1 || i == 3) continue;
val.insert(a[i]);
if(trc != -1) dis.insert(a[i] - trc);
trc = a[i];
}
if(val.size() == 1 || (*dis.begin() == *dis.rbegin()))
{
cout << v.size() << '\n';
for(int x : v) cout << x << ' ';
cout << '\n';
cout << val.size() << '\n';
for(int x : val) cout << x << ' ';
exit(0);
}
for(int i = 3; i <= n; i++)
{
int x = v.back() + d;
if(val.find(x) != val.end())
{
v.push_back(x);
val.erase(val.find(x));
auto tmp = val.lower_bound(x);
auto tmp2 = val.lower_bound(x);
if(tmp != val.end())
dis.erase(dis.find(*tmp - x));
if(tmp2 != val.begin())
{
--tmp2;
dis.erase(dis.find(x - *tmp2));
if(tmp != val.end())
dis.insert(*tmp - *tmp2);
}
}
else
{
return;
}
if(val.size() == 1 || (*dis.begin() == *dis.rbegin()))
{
cout << v.size() << '\n';
for(int x : v) cout << x << ' ';
cout << '\n';
cout << val.size() << '\n';
for(int x : val) cout << x << ' ';
exit(0);
}
}
}
void check3()
{
int d = a[3] - a[2];
vector<int> v;
multiset<int> val, dis;
v.push_back(a[2]);
v.push_back(a[3]);
int trc = -1;
for(int i = 1; i <= n; i++)
{
if(i == 2 || i == 3) continue;
val.insert(a[i]);
if(trc != -1) dis.insert(a[i] - trc);
trc = a[i];
}
for(int i = 3; i <= n; i++)
{
int x = v.back() + d;
if(val.find(x) != val.end())
{
v.push_back(x);
val.erase(val.find(x));
auto tmp = val.lower_bound(x);
auto tmp2 = val.lower_bound(x);
if(tmp != val.end())
dis.erase(dis.find(*tmp - x));
if(tmp2 != val.begin())
{
--tmp2;
dis.erase(dis.find(x - *tmp2));
if(tmp != val.end())
dis.insert(*tmp - *tmp2);
}
}
else
{
return;
}
if(val.size() == 1 || (*dis.begin() == *dis.rbegin()))
{
cout << v.size() << '\n';
for(int x : v) cout << x << ' ';
cout << '\n';
cout << val.size() << '\n';
for(int x : val) cout << x << ' ';
exit(0);
}
}
}
main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(task ".inp", "r")){
freopen(task ".inp", "r", stdin);
freopen(task ".out", "w", stdout);
}
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + 1 + n);
if(n == 2)
{
cout << 1 << '\n' << a[1] << '\n' << 1 << '\n' << a[2];
exit(0);
}
// if(n <= 4)
// {
// cout << 2 << '\n';
// for(int i = 1; i <= 2; i++)
// cout << a[i] << ' ';
// cout << '\n';
// cout << n - 2 << '\n';
// for(int i = 3; i <= n; i++)
// cout << a[i] << ' ';
// exit(0);
// }
check1();
check2();
check3();
cout << -1 << '\n';
}
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... |