Submission #152924

#TimeUsernameProblemLanguageResultExecution timeMemory
152924arnold518Gap (APIO16_gap)C++14
100 / 100
76 ms3308 KiB
#include "gap.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 1e5; int T, N; ll A[MAXN+10], ans; ll findGap(int _T, int _N) { int i, j; T=_T; N=_N; if(T==1) { ll s=0, t=1e18; for(i=1, j=N; i<=j; i++, j--) { ll a, b; MinMax(s, t, &a, &b); A[i]=a; A[j]=b; s=a+1; t=b-1; } for(i=2; i<=N; i++) ans=max(ans, A[i]-A[i-1]); return ans; } else { ll s, e; MinMax(0, 1e18, &s, &e); if(N==2) return e-s; ll g=(e-s+N-2)/(ll)(N-1); ll a, b, p=s, q=s+g; vector<pll> V; while(1) { if(p>e) break; if(p>q) break; MinMax(p, q, &a, &b); if(a!=-1) V.push_back({a, b}); p=q+1; q=p+g; q=min(q, e); } //for(i=0; i<V.size(); i++) printf("%lld %lld\n", V[i].first, V[i].second); for(i=1; i<V.size(); i++) ans=max(ans, V[i].first-V[i-1].second); return ans; } }

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=1; i<V.size(); i++) ans=max(ans, V[i].first-V[i-1].second);
                  ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...