제출 #574222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
574222		cadmiumsky	Gap (APIO16_gap)	C++14	70 / 100	70 ms	5832 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;
    n = (n + 1) / 2;
    for(int i = 0; i < n; i++) {
      MinMax(l, r, &l, &r);
      elem.insert(l);
      elem.insert(r);
      l++;
      r--;
    }
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:42: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]
   42 |   for(int i = 1; i < v.size(); i++)
      |                  ~~^~~~~~~~~~

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