제출 #1012049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1012049		zsombor	Gap (APIO16_gap)	C++17	89.04 / 100	41 ms	4392 KiB

gap

#include "gap.h"
#include <vector>
using namespace std;
using ll = long long;

const ll m = 1000000000000000000;

ll solve1(ll n) {
	ll l = 0, r = m, mn, mx, ans = 0;
	vector <ll> v;
	vector <ll> v2;
	while (v.size() + v2.size() < n) {
		MinMax(l, r, &mn, &mx);
		l = mn + 1;
		r = mx - 1;
		v.push_back(mn);
		v2.push_back(mx);
	}
	while (v2.size()) { v.push_back(v2.back()); v2.pop_back(); }
	for (int i = 1; i < v.size(); i++) ans = max(ans, v[i] - v[i - 1]);
	return ans;
}

ll solve2(ll n) {
	ll a1, an, mn, mx, ans = 0;
	MinMax(0, m, &a1, &an);
	ll d = a1, u = a1, l = (an - a1) / (n - 1);
	vector <ll> v;
	while (d < an - 1) {
		MinMax(d + 1, min(d + l, an - 1), &mn, &mx);
		d += l;
		if (mn == -1) continue;
		ans = max(ans, mn - u);
		u = mx;
	}
	ans = max(ans, an - u);
	return ans;
}

ll findGap(int T, int N) {
	return (T == 1 ? solve1(N) : solve2(N));
}

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

gap.cpp: In function 'll solve1(ll)':
gap.cpp:12:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   12 |  while (v.size() + v2.size() < n) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~
gap.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (int i = 1; i < v.size(); i++) ans = max(ans, v[i] - v[i - 1]);
      |                  ~~^~~~~~~~~~

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