Submission #1257350

#TimeUsernameProblemLanguageResultExecution timeMemory
1257350tvgkDrvca (COCI19_drvca)C++20
110 / 110
811 ms11080 KiB
#include<bits/stdc++.h> using namespace std; #define task "NOEL" #define se second #define fi first #define ll long long #define ii pair<ll, ll> const long mxN = 2e5 + 7, inf = 1e9 + 7; int n, a[mxN]; multiset<int> s; map<int, int> dif; void decre(int j) { dif[j]--; if (!dif[j]) dif.erase(j); } void Add(int j) { int r = *s.lower_bound(j); int l = *(--s.lower_bound(j)); if (l && r != inf) decre(r - l); if (l) dif[j - l]++; if (r != inf) dif[r - j]++; s.insert(j); } bool era(int j) { if (s.find(j) == s.end()) return 0; s.erase(s.find(j)); int r = *s.lower_bound(j); int l = *(--s.lower_bound(j)); if (l && r != inf) dif[r - l]++; if (l) decre(j - l); if (r != inf) decre(r - j); return 1; } void Check() { if (dif.size() > 1) return; s.erase(0); s.erase(inf); multiset<int> ans; for (int i = 1; i <= n; i++) ans.insert(a[i]); cout << s.size() << '\n'; for (int i : s) { cout << i << " "; ans.erase(ans.find(i)); } cout << '\n' << ans.size() << '\n'; for (int i : ans) cout << i << " "; exit(0); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // 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 + n + 1); s.insert(0); s.insert(inf); for (int i = 2; i <= n; i++) Add(a[i]); Check(); for (int i = 2; i <= n; i++) { int cur = a[i]; while (era(cur)) { Check(); cur += a[i] - a[1]; } while (cur != a[i]) { cur -= a[i] - a[1]; Add(cur); } } 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...