Submission #753486

#TimeUsernameProblemLanguageResultExecution timeMemory
753486KN200711Gap (APIO16_gap)C++14
70 / 100
46 ms2656 KiB
#include "gap.h" # include <bits/stdc++.h> # define ll long long using namespace std; ll solve2(int N) { ll lw = 0ll, hg = 0ll; MinMax(0ll, 1ll * 1e18, &lw, &hg); ll diff = hg - lw; diff = (diff + 1ll * N - 2ll) / (N - 1ll); ll ls = -1; while(lw < hg) { ll mn, mx; MinMax(lw, min(1ll * lw + 1ll * diff, (ll) 1e18), &mn, &mx); lw += diff + 1ll; if(mn == mx && mn == -1) continue; if(ls == -1) ls = mx; else { diff = max(diff, mn - ls); ls = mx; } } return diff; } long long findGap(int T, int N) { if(T == 2) return solve2(N); vector<ll> arr, arr1; arr.clear(); arr1.clear(); ll lw = 0ll, hg = 1e18; for(; (int) arr.size() + (int) arr1.size() < (int) N ;) { MinMax(lw, hg, &lw, &hg); if(lw != hg) { arr.push_back(lw); arr1.push_back(hg); lw++; hg--; } else { arr.push_back(lw); } } ll diff = 0ll; for(int c=0;c<arr1.size();c++) { arr.push_back(arr1[c]); } for(int c=0;c + 1<(int) arr.size();c++) { diff = max(diff, arr[c + 1] - arr[c]); } return diff; }

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int c=0;c<arr1.size();c++) {
      |              ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...