제출 #107342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107342		maruii	Gap (APIO16_gap)	C++14	100 / 100	77 ms	3352 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;

long long findGap(int T, int N){
	long long mn, mx, s=0, e=1e18, ans = 0;
	if(T==1){
		int i=0, j=N-1;
		vector<long long> vec(N);
		while(i<=j){
			MinMax(s, e, &mn, &mx);
			vec[i++] = mn, vec[j--] = mx;
			s = mn+1, e = mx-1;
		}
		for(int i=1; i<N; ++i) ans = max(ans, abs(vec[i]-vec[i-1]));
		return ans;
	}
	MinMax(0, 1e18, &mn, &mx);
	s = mn, e = mx;
	if(N==2) return e-s;
	long long d = (e-s-1)/(N-1)+1;
	vector<pair<long long, long long> > vec;
	vec.emplace_back(s, s);
	for(int i=1; i<N; ++i){
		MinMax(s+1+(i-1)*d, s+1+i*d-1, &mn, &mx);
		if(mn != -1) vec.emplace_back(mn, mx);
	}
	for(int i=1; i<vec.size(); ++i) ans = max(ans, vec[i].first - vec[i-1].second);
	return ans;
}

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

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<vec.size(); ++i) ans = max(ans, vec[i].first - vec[i-1].second);
               ~^~~~~~~~~~~

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