Submission #282644

#TimeUsernameProblemLanguageResultExecution timeMemory
282644AaronNaiduGap (APIO16_gap)C++14
43.01 / 100
118 ms6184 KiB
#include <bits/stdc++.h> #include "gap.h" using namespace std; typedef long long ll; ll mn = 0; ll mx = 0; ll n; vector<ll> v; unordered_map<ll, bool> taken; /*void MinMax(ll left, ll right, ll *mn, ll *mx) { ll x, y; cin >> x >> y; *mn = x; *mx = y; }*/ void binSearch(ll left, ll right) { if (v.size() == n) { return; } if (right < left) { return; } MinMax(left, right, &mn, &mx); if (mn == -1) { return; } if (taken.find(mn) == taken.end()) { taken.insert({mn, true}); v.push_back(mn); } if (taken.find(mx) == taken.end()) { taken.insert({mx, true}); v.push_back(mx); } if (mn == mx or mn == mx -1) { return; } left = mn+1; right = mx-1; if (right - left <= 2) { binSearch(left, right); return; } ll med = (left+right)/2; binSearch(left, med); binSearch(med+1, right); } ll findGap(int t, int N) { n = N; ll leftPointer = 0; ll rightPointer = 1000000000000000000; if (t == 1) { while (v.size() < n) { MinMax(leftPointer, rightPointer, &mn, &mx); v.push_back(mn); v.push_back(mx); leftPointer = mn+1; rightPointer = mx-1; } sort(v.begin(), v.end()); ll maxDiff = 0; for (int i = 0; i < v.size()-1; i++) { maxDiff = max(maxDiff, v[i+1]-v[i]); } return maxDiff; } binSearch(leftPointer, rightPointer); sort(v.begin(), v.end()); ll maxDiff = 0; for (int i = 0; i < v.size()-1; i++) { maxDiff = max(maxDiff, v[i+1]-v[i]); } return maxDiff; }

Compilation message (stderr)

gap.cpp: In function 'void binSearch(ll, ll)':
gap.cpp:20:18: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   20 |     if (v.size() == n)
      |         ~~~~~~~~~^~~~
gap.cpp: In function 'll findGap(int, int)':
gap.cpp:67:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   67 |         while (v.size() < n)
      |                ~~~~~~~~~^~~
gap.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for (int i = 0; i < v.size()-1; i++)
      |                         ~~^~~~~~~~~~~~
gap.cpp:86:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i = 0; i < v.size()-1; i++)
      |                     ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...