Submission #1257606

#TimeUsernameProblemLanguageResultExecution timeMemory
1257606knhatdevDrvca (COCI19_drvca)C++20
110 / 110
181 ms12104 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)

drvca.cpp:182:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  182 | main(){
      | ^~~~
drvca.cpp: In function 'int main()':
drvca.cpp:185:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
drvca.cpp:186:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  186 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...