Submission #574221

#	Time	Username	Problem	Language	Result	Execution time	Memory
574221		cadmiumsky	Gap (APIO16_gap)	C++14	70 / 100	91 ms	5780 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
ll findGap(int t, int n) {
  // cerr << t << ' ' << n << '\n';
    ll l = 0, r = 1e18;
  if(t == 1) {
    set<ll> elem;
    for(int i = 1; i <= n; i++)
      MinMax(l, r, &l, &r);
    l--;
    r++;
    while(l <= r && n > 0) {
      if(l + 1 > r - 1)
        break;
      MinMax(l + 1, r - 1, &l, &r);
      if(l == -1)
        break;
      elem.insert(l);
      elem.insert(r);
      n -= 1 + (l != r);
      // cerr << n << ' ' ;
    }
    auto it = elem.begin();
    it++;
    ll mx = - 1;
    for(auto i = next(it); i != elem.end(); i++)
      mx = max(mx, *it - *prev(it));
    return mx;
  }
  MinMax(l, r, &l, &r);
  ll mx = r;
  vector<pii> v;
  ll minl = (r - l + n - 2) / (n - 1);
  v.emplace_back(l, l);
  // cerr << l << ' ' << r << ' ' << minl << '\n';
  for(ll i = l; i < mx; i += minl) {
    // cerr << i << ' ' << i + minl << ' ' << mx << '\n';
    MinMax(i, min(mx, i + minl) - 1, &l, &r);
    if(l == -1)
      continue;
    v.emplace_back(l, r);
  }
  v.emplace_back(mx, mx);
  mx = -1;
  for(int i = 1; i < v.size(); i++)
    mx = max(v[i].first - v[i - 1].second, mx);
	return mx;
}

Compilation message (stderr)

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i = 1; i < v.size(); i++)
      |                  ~~^~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 70 / 70