Submission #445579

#TimeUsernameProblemLanguageResultExecution timeMemory
445579hgmhcDrvca (COCI19_drvca)C++17
0 / 110
36 ms3364 KiB
#include <bits/stdc++.h> #define REP(i,a,b) for (auto i = (a); i <= (b); ++i) #define PER(i,a,b) for (auto i = (b); i >= (a); --i) #define log2(x) (31-__builtin_clz(x)) #define ALL(x) (x).begin(), (x).end() #define RALL(x) (x).rbegin(), (x).rend() #define SZ(x) (int)(x).size() #define PB push_back #define FI first #define SE second #define mup(x,y) x = min(x,y) #define Mup(x,y) x = max(x,y) #define debug(x) cout << #x << " is " << x << el #define el '\n' using namespace std; using ll = long long; using ii = pair<int,int>; using iii = tuple<int,int,int>; void solution(); int main() {ios::sync_with_stdio(0); cin.tie(0); solution();} const int N = 100003; int n, h[N]; bool isA[N]; void print() { vector<int> a, b; REP(i, 1, n) { if (isA[i]) a.push_back(h[i]); else b.push_back(h[i]); } cout << SZ(a) << el; for (auto p : a) cout << p << ' '; cout << el << SZ(b) << el; for (auto p : b) cout << p << ' '; } void input() { cin >> n; REP(i,1,n) cin >> h[i]; } void solution() { input(); sort(h+1,h+n+1); bool chk; //first, A: h[1], h[3],... isA[1] = true; chk = true; for (int preA = h[1], rA = h[3]-h[1], i = 3; i <= n; ++i) { if (h[i] == preA+rA) { isA[i] = true; preA += rA; } } int preB = h[2], rB = 1000000; REP(i,4,n) { if (!isA[i]) { rB = h[i]-preB; break; } } REP(i,4,n) { if (!isA[i]) { if (h[i] != preB+rB) {chk = false; break;} preB += rB; } } if (chk) {print(); return;} //second, A: h[1], h[2],... fill(isA,isA+n+1,0); isA[1] = true; chk = true; for (int preA = h[1], rA = h[2]-h[1], i = 2; i <= n; ++i) { if (h[i] == preA+rA) { isA[i] = true; preA += rA; } } preB = 0, rB = 1000000; int i; for(i = 1; i <= n; ++i) if (!isA[i]) {preB = h[i]; break;} for (++i; i <= n; ++i) if (!isA[i]) {rB = h[i]-preB; break;} for (; i <= n; ++i) { if (!isA[i]) { if (h[i] != preB+rB) {chk = false; break;} preB += rB; } } if (chk) {print(); return;} cout << -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...