Submission #1258113

#TimeUsernameProblemLanguageResultExecution timeMemory
1258113_rain_Drvca (COCI19_drvca)C++20
110 / 110
20 ms3140 KiB
#include<bits/stdc++.h> using namespace std; typedef long long LL; #define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i) #define BIT(maks , x) (((mask) >> (x)) & (1)) #define MASK(x) ((LL)(1)<<(x)) template<class X,class Y> bool maximize(X &x , Y y){ if (x < y) return x = y , true; else return false; } template<class X,class Y> bool minimize(X &x,Y y){ if (x > y) return x = y , true; else return false; } const int N = (int) 1e5; int h[N + 2]; int mark[N + 2] = {}; int n; bool check_possible(vector<int>&data){ if (data.size() < 3) return true; for(int i = 2; i < data.size(); ++i) if (h[data[i]] - h[data[i - 1]] != h[data[i - 1]] - h[data[i - 2]]) return false; return true; } void print(vector<int>v , vector<int>nxt){ if (nxt.size() == 0) nxt.push_back(v.back()) , v.pop_back(); cout << nxt.size() << '\n'; for(auto& x : nxt) cout << h[x] << ' '; cout << '\n'; cout << v.size() << '\n'; for(auto& x : v) cout << h[x] << ' '; cout << '\n'; return; } bool check(int id1 , int id2){ vector<int>v , nxt; for(int i = 1; i <= n; ++i) mark[i] = -1; v.push_back(id1) , v.push_back(id2); int cur_sz = 1; for(int i = id2 + 1; i <= n; ++i) { if (h[i] - h[v[cur_sz]] == h[v[cur_sz]] - h[v[cur_sz - 1]]) { v.push_back(i); ++cur_sz; } } for(int i = 0; i < v.size(); ++i) mark[v[i]] = i + 1; for(int i = 1; i <= n; ++i){ if (mark[i]!=-1) continue; if (nxt.size() < 2) nxt.push_back(i) , mark[i] = 0; else{ if (h[i] - h[nxt.back()] == h[nxt.back()] - h[nxt[nxt.size() - 2]]){ nxt.push_back(i); mark[i] = 0; } } } bool ok = true; for(int i = 1; i <= n; ++i) if (mark[i]==-1) ok = false; if (ok){ print(v,nxt); return true; } while (v.size() && nxt.size() && v.back() > nxt.back()) { mark[v.back()] = -1; v.pop_back(); } int t; t = (nxt.size() ? nxt.back() : 0); for(int i = t + 1; i <= n; ++i){ if (mark[i]!=-1) continue; if (nxt.size() < 2) nxt.push_back(i) , mark[i] = 0; else{ if (h[i] - h[nxt.back()] == h[nxt.back()] - h[nxt[nxt.size() - 2]]){ nxt.push_back(i); mark[i] = 0; } } } t = (v.size() ? v.back() : 0); // for(int i = t + 1; i <= n; ++i){ if (mark[i]!=-1) continue; if (v.size() < 2) nxt.push_back(i) , mark[i] = 0; else{ if (h[i] - h[v.back()] == h[v.back()] - h[v[v.size() - 2]]){ v.push_back(i); mark[i] = 0; } } } for(int i = 1; i <= n; ++i) if (mark[i]==-1) return false; print(v,nxt); return true; } int main(){ ios::sync_with_stdio(false); cin.tie(0) ; cout.tie(0) ; #define name "main" if (fopen(name".inp","r")){ freopen(name".inp","r",stdin); freopen(name".out","w",stdout); } cin >> n; for(int i = 1; i <= n; ++i) cin >> h[i]; sort(h+1,h+n+1); // for(int i = 1; i <= n; ++i) cout << h[i] << ' '; cout << '\n'; if (check(1,2)) return 0; if (check(1,3)) return 0; if (check(2,3)) return 0; // if (n > 3 && check(2,4)) return 0; cout << -1; return 0; }

Compilation message (stderr)

drvca.cpp: In function 'int main()':
drvca.cpp:110:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
drvca.cpp:111:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |                         freopen(name".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...