# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
235621 | 2020-05-28T21:01:49 Z | doowey | Drvca (COCI19_drvca) | C++14 | 676 ms | 3804 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int N = (int)1e5 + 10; vector<int> H; vector<bool>use; int main(){ fastIO; int n; cin >> n; H.resize(n); use.resize(n); for(int i = 0 ; i < n ; i ++ ) cin >> H[i]; sort(H.begin(),H.end()); if(n <= 4){ cout << 2 << "\n" << H[0] << " " << H[1] << "\n" << 2 << "\n" << H[2] << " " << H[3] << "\n"; return 0; } int c[3]; int cur; int g; for(int it = 0; it < 500 ; it ++ ){ for(int q = 0; q < 3; q ++ ) c[q] = (((int)rng() % n) + n) % n; sort(c, c + 3); if(c[0] == c[1] || c[1] == c[2]) continue; for(int i = 0 ; i < n ; i ++ ) use[i] = false; g=__gcd(H[c[1]]-H[c[0]],H[c[2]]-H[c[1]]); if(H[c[1]] == H[c[0]] || H[c[2]] == H[c[1]]) g=0; cur=H[0]; vector<int> rem; for(int i = 0 ; i < n; i ++ ){ if(cur == H[i]){ use[i]=true; cur += g; } else{ rem.push_back(H[i]); } } bool good = true; for(int i = 2; i < rem.size(); i ++ ){ if(rem[i - 1] - rem[i - 2] != rem[i] - rem[i - 1]){ good = false; } } if(good){ vector<int> A, B; for(int i = 0 ; i < n; i ++ ){ if(use[i]) A.push_back(H[i]); else B.push_back(H[i]); } if(B.empty()){ B.push_back(A[A.size() - 2]); B.push_back(A[A.size() - 1]); A.pop_back(); A.pop_back(); } cout << A.size() << "\n"; for(auto x : A) cout << x << " "; cout << "\n"; cout << B.size() << "\n"; for(auto x : B) cout << x << " "; cout << "\n"; return 0; } int low = -1; for(int i = 0 ; i < n; i ++ ){ if(!use[i]){ low = i; break; } } for(int i = 0 ; i < n ; i ++ ){ use[i]=false; } cur = H[low]; rem.clear(); for(int i = low ; i < n ; i ++ ){ if(cur == H[i]){ use[i]=true; cur += g; } } for(int i = 0 ; i < n; i ++ ){ if(!use[i]) rem.push_back(H[i]); } good=true; for(int i = 2; i < rem.size(); i ++ ){ if(rem[i - 1] - rem[i - 2] != rem[i] - rem[i - 1]){ good = false; } } if(good){ vector<int> A, B; for(int i = 0 ; i < n; i ++ ){ if(use[i]) A.push_back(H[i]); else B.push_back(H[i]); } if(B.empty()){ B.push_back(A[A.size() - 2]); B.push_back(A[A.size() - 1]); A.pop_back(); A.pop_back(); } cout << A.size() << "\n"; for(auto x : A) cout << x << " "; cout << "\n"; cout << B.size() << "\n"; for(auto x : B) cout << x << " "; cout << "\n"; return 0; } } cout << -1 << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 256 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 5 ms | 384 KB | Output is correct |
7 | Correct | 4 ms | 384 KB | Output is correct |
8 | Correct | 5 ms | 384 KB | Output is correct |
9 | Incorrect | 5 ms | 384 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 256 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 5 ms | 384 KB | Output is correct |
7 | Correct | 4 ms | 384 KB | Output is correct |
8 | Correct | 5 ms | 384 KB | Output is correct |
9 | Incorrect | 5 ms | 384 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 76 ms | 3788 KB | Output is correct |
2 | Correct | 88 ms | 3548 KB | Output is correct |
3 | Correct | 71 ms | 3804 KB | Output is correct |
4 | Correct | 50 ms | 3596 KB | Output is correct |
5 | Correct | 39 ms | 3400 KB | Output is correct |
6 | Correct | 69 ms | 3700 KB | Output is correct |
7 | Correct | 40 ms | 3732 KB | Output is correct |
8 | Correct | 37 ms | 3444 KB | Output is correct |
9 | Incorrect | 676 ms | 2636 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 256 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 5 ms | 384 KB | Output is correct |
7 | Correct | 4 ms | 384 KB | Output is correct |
8 | Correct | 5 ms | 384 KB | Output is correct |
9 | Incorrect | 5 ms | 384 KB | Output isn't correct |
10 | Halted | 0 ms | 0 KB | - |