Submission #74724

#	Time	Username	Problem	Language	Result	Execution time	Memory
74724		goodbaton	Gap (APIO16_gap)	C++14	100 / 100	80 ms	18276 KiB

gap

#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include "gap.h"

using namespace std;
typedef long long ll;

#define mod 1000000007
#define SIZE 10000

long long findGap1(int T, int N){

  ll l = 0, r = 1e18;
  vector<ll> vec;
  
  while(1){
    ll a, b;

    MinMax(l,r,&a,&b);

    if(a==-1) break;
    
    vec.push_back(a);

    if(a==b) break;

    vec.push_back(b);

    if(a+1==b) break;

    if(vec.size() == N) break;
    
    l = a+1;
    r = b-1;
  }

  sort(vec.begin(),vec.end());

  ll ans = 0;

  for(int i=1;i<vec.size();i++)
    ans = max(ans, vec[i] - vec[i-1]);
  
  return ans;
}

long long findGap(int T, int N){

  if(T==1) return findGap1(T,N);

  ll MAX = 1e18;
  ll l, r;
  vector<ll> vec;

  MinMax(0,(ll)1e18,&l,&r); //N

  ll D = r-l+1 - N;
  ll B = (D+(N-1))/N + 2;
  
  vec.push_back(l);
  vec.push_back(r);
  
  for(ll s = l+1;s<r;s+=B){
    ll a,b;
    MinMax(s,s+B-1,&a,&b);

    if(a!=-1 && a==b){
      vec.push_back(a);
    }else if(a!=-1){
      vec.push_back(a);
      vec.push_back(b);
    }
  }
  
  sort(vec.begin(),vec.end());
  
  ll ans = 0;

  for(int i=1;i<vec.size();i++)
    ans = max(ans, vec[i] - vec[i-1]);
  
  return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap1(int, int)':
gap.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(vec.size() == N) break;
        ~~~~~~~~~~~^~~~
gap.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<vec.size();i++)
               ~^~~~~~~~~~~
gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:83:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<vec.size();i++)
               ~^~~~~~~~~~~
gap.cpp:55:6: warning: unused variable 'MAX' [-Wunused-variable]
   ll MAX = 1e18;
      ^~~

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