Submission #563513

#	Time	Username	Problem	Language	Result	Execution time	Memory
563513		penguin133	Gap (APIO16_gap)	C++14	44.71 / 100	72 ms	3444 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
long long B[100005];
long long findGap(int T, int N)
{
	if(T == 1){
		long long ans = 0, mini, maxi;
		B[N+1] = (long long)1e18 + 5, B[0] = -1;
		int j = N;
		for(int i=1;i<=j;i++){
			//cout << B[i-1] << " " << B[j+1] << '\n';
			MinMax(B[i-1]+1, B[j+1]-1, &mini, &maxi);
			//cout << mini << '\n';
			B[i] = mini, B[j] = maxi;
			//cout << *mini << " " << *maxi << '\n';
			j--;
		}
		for(int i=1;i<N;i++)ans = max(ans, B[i+1] - B[i]);
		return ans;
	}
	else{
		long long ans = 0, mini, maxi;
		B[N+1] = (long long)1e18 +1;
		queue<pair<long long, long long > > q;
		q.push({0ll, B[N+1]});
		vector<long long>v;
		while(!q.empty()){
			long long y = q.front().first, z = q.front().second;
			q.pop();
          if(y > z)continue;
			//cout << y << " " << z << '\n';
			long long m = (y + z)/2;
			MinMax(y, m, &mini, &maxi);
			if(mini != -1){
				if(mini == maxi)v.push_back(mini);
				else q.push({mini-1, maxi-1}), v.push_back(mini), v.push_back(maxi);
			}
			if(m == z)continue;
			MinMax(m+1, z, &mini, &maxi);
			if(mini != -1){
				if(mini == maxi)v.push_back(mini);
				else q.push({mini+1,maxi-1}), v.push_back(mini), v.push_back(maxi);
			}
		}
		sort(v.begin(), v.end());
		for(int i=0;i<v.size()-1;i++)ans = max(ans, v[i+1] - v[i]);
		return ans;
	}
	return 0;
}

Compilation message (stderr)

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

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