#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using lint = long long;
const int maxn = 2e5 + 5;
const int inf = 1e9 + 5;
const int mod = 1e9 + 7;
int n;
int a[maxn];
multiset<int> s1;
multiset<int> s2;
multiset<int> sd;
void init() {
s1.clear();
s2.clear();
sd.clear();
for(int i = 0; i < n; i++) {
s2.insert(a[i]);
if(i > 0)
sd.insert(a[i] - a[i - 1]);
}
}
void print() {
cout << s1.size() << endl;
while(!s1.empty()) {
cout << *s1.begin() << " ";
s1.erase(s1.begin());
}
cout << endl;
cout << s2.size() << endl;
while(!s2.empty()) {
cout << *s2.begin() << " ";
s2.erase(s2.begin());
}
}
signed main() {
#ifdef Local
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
if(n == 2) {
cout << 1 << endl << a[0] << endl;
cout << 1 << endl << a[1] << endl;
return 0;
}
if(n == 3) {
cout << 1 << endl << a[0] << endl;
cout << 2 << endl << a[1] << " " << a[2] << endl;
return 0;
}
int d;
int k;
//case 01
init();
d = a[1] - a[0];
k = 2;
s1.insert(a[0]);
s1.insert(a[1]);
s2.erase(s2.find(a[0]));
s2.erase(s2.find(a[1]));
sd.erase(sd.find(d));
sd.erase(sd.find(a[2] - a[1]));
while(true) {
if(*sd.begin() == *sd.rbegin()) {
print();
return 0;
}
k++;
int curr = a[0] + (k - 1) * d;
s1.insert(curr);
auto it = s2.find(curr);
if(it == s2.end())
break;
int prv = 0, nxt = 0;
if(it != s2.begin()) {
prv = *prev(it);
sd.erase(curr - prv);
}
auto tmp = next(it);
if(tmp != s2.end()) {
nxt = *tmp;
sd.erase(nxt - curr);
}
if(nxt && prv)
sd.insert(nxt - prv);
}
//case 02
init();
d = a[2] - a[0];
k = 2;
s1.insert(a[0]);
s1.insert(a[2]);
s2.erase(s2.find(a[0]));
s2.erase(s2.find(a[2]));
sd.erase(sd.find(d));
sd.erase(sd.find(a[3] - a[2]));
sd.erase(sd.find(a[2] - a[1]));
sd.erase(sd.find(a[1] - a[0]));
sd.insert(a[3] - a[1]);
while(true) {
if(*sd.begin() == *sd.rbegin()) {
print();
return 0;
}
k++;
int curr = a[0] + (k - 1) * d;
s1.insert(curr);
auto it = s2.find(curr);
if(it == s2.end())
break;
int prv = 0, nxt = 0;
if(it != s2.begin()) {
prv = *prev(it);
sd.erase(curr - prv);
}
auto tmp = next(it);
if(tmp != s2.end()) {
nxt = *tmp;
sd.erase(nxt - curr);
}
if(nxt && prv)
sd.insert(nxt - prv);
}
//case 12
init();
d = a[2] - a[1];
k = 2;
s1.insert(a[1]);
s1.insert(a[2]);
s2.erase(s2.find(a[1]));
s2.erase(s2.find(a[2]));
sd.erase(sd.find(d));
sd.erase(sd.find(a[3] - a[2]));
sd.erase(sd.find(a[1] - a[0]));
sd.insert(a[3] - a[0]);
while(true) {
if(*sd.begin() == *sd.rbegin()) {
print();
return 0;
}
k++;
int curr = a[1] + (k - 1) * d;
s1.insert(curr);
auto it = s2.find(curr);
if(it == s2.end())
break;
int prv = 0, nxt = 0;
if(it != s2.begin()) {
prv = *prev(it);
sd.erase(curr - prv);
}
auto tmp = next(it);
if(tmp != s2.end()) {
nxt = *tmp;
sd.erase(nxt - curr);
}
if(nxt && prv)
sd.insert(nxt - prv);
}
cout << -1 << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
123 ms |
21192 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
