제출 #1367500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1367500		coin_	Gap (APIO16_gap)	C++20	100 / 100	34 ms	2704 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;

const int inf = 1e18, zero = 0;

int sub2(signed n) {
	int fiNum, lastNum;
	MinMax(zero, inf, &fiNum, &lastNum);
	int len = (lastNum - fiNum + 1)/n;
	vector<pair<int, int>> minMaxSegs(n);
	int lptr = min(fiNum+1, fiNum + len - 1) , rptr = fiNum + len - 1, cur = 0;
	while(cur < n){
		if (cur == n-1) rptr = max(lastNum, rptr-1);
		MinMax(lptr, rptr, &minMaxSegs[cur].fi, &minMaxSegs[cur].se);
		cur++;
		lptr += len;
		rptr += len;
	}
	cur++;
	lptr += len;
	rptr += len;

	int i = 0, lastR, ans = 0;
	while (i < n){
		if (minMaxSegs[i].se == -1){
			i++;
		}
		else{
			ans = minMaxSegs[i].fi - fiNum;
			lastR = minMaxSegs[i].se;
			i++;
			break;
		}
	}
	for (; i < n; i++){
		if (minMaxSegs[i].fi == -1){
			continue;
		}
		ans = max(ans, minMaxSegs[i].fi - lastR);
		lastR = minMaxSegs[i].se;
	}
	ans = max(ans, lastNum - lastR);
	return ans;
}

int sub1(signed n){
	int lptr = 0, rptr = n-1, fiNum = zero, lastNum = inf;
	vector<int> ans(n);
	while (lptr <= rptr){
		MinMax(fiNum, lastNum, &ans[lptr], &ans[rptr]);
		fiNum = ans[lptr]+1;
		lastNum = ans[rptr]-1;
		lptr++;
		rptr--;
	}

	int ret = 0;
	for (int i = 1; i < n; i++){
		ret = max(ret, ans[i] - ans[i-1]);
	}
	return ret;
}

long long findGap(signed t, signed n)
{
	if (t == 2){
		return sub2(n);
	}
	return sub1(n);
}

• 서브태스크 1: 30 / 30
• 서브태스크 2: 70 / 70