Submission #573969

#	Time	Username	Problem	Language	Result	Execution time	Memory
573969		cadmiumsky	Gap (APIO16_gap)	C++14	70 / 100	52 ms	3220 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) {
    vector<ll> elem[2];
    while(l <= r) {
      MinMax(l, r, &l, &r);
      if(l == -1)
        break;
      elem[0].push_back(l);
      if(l != r)
        elem[1].push_back(r);
      l++;
      r--;
    }
    reverse(all(elem[1]));
    copy(all(elem[1]), back_inserter(elem[0]));
    ll mx = -1; 
    for(int i = 1; i < elem[0].size(); i++)
      mx = max(mx, elem[0][i] - elem[0][i - 1]);
    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:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 1; i < elem[0].size(); i++)
      |                    ~~^~~~~~~~~~~~~~~~
gap.cpp:44: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]
   44 |   for(int i = 1; i < v.size(); i++)
      |                  ~~^~~~~~~~~~

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