Submission #262379

#	Time	Username	Problem	Language	Result	Execution time	Memory
262379		my99n	Gap (APIO16_gap)	C++14	30 / 100	3051 ms	139092 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 < N; i++) {
      ans = max(ans, a[i]-a[i-1]);
    }
  }
	return ans;
}

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from gap.cpp:2:
gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:48:21: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |     assert(a.size() == N);
      |            ~~~~~~~~~^~~~

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