제출 #262380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
262380		my99n	Gap (APIO16_gap)	C++14	30 / 100	3037 ms	139164 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<long long> a;
void findarr (long long low, long long high) {
  long long mnl = -1, mxl = -1, mnr = -1, mxr = -1;
  int mid = (low+high)/2;
  if (low <= mid) MinMax(low, mid, &mnl, &mxl);
  if (mid+1 <= high) MinMax(mid+1, high, &mnr, &mxr);
  if (mnl != -1) {
    a.push_back(mnl);
    if (mxl != mnl) {
      a.push_back(mxl);
      findarr(mnl+1, mxl-1);
    }
  }
  if (mnr != -1) {
    a.push_back(mnr);
    if (mxr != mnr) {
      a.push_back(mxr);
      findarr(mnr+1, mxr-1);
    }
  }
}
 
long long findGap(int T, int N) {
  long long ans = 0;
  if (T == 1) {
    a.resize(N);
    long long mn, mx;
    long long l = 0, r = 1e18;
    int indl = 0, indr = N-1;
    while (indl <= indr) {
      MinMax(l, r, &mn, &mx);
      if (mn != -1) {
        a[indl++] = mn;
        a[indr--] = mx;
      }
      l = mn+1; r = mx-1;
    }
    for (int i = 1; i < N; i++) {
      ans = max(ans, a[i]-a[i-1]);
    }
  }
  else {
    findarr(0, 1e18);
    // assert(a.size() == N);
    sort(a.begin(), a.end());
    for (int i = 1; i < a.size()-1; i++) {
      ans = max(ans, a[i]-a[i-1]);
    }
  }
	return ans;
}

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

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

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