제출 #838673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838673		tch1cherin	Gap (APIO16_gap)	C++17	100 / 100	46 ms	3060 KiB

gap

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

long long findGap(int T, int N) {
  if (T == 1) {
		long long Min = -1, Max = 1e18l + 1;
		vector<long long> front, back;
		for (int i = 0; i < (N + 1) / 2; i++) {
			MinMax(Min + 1, Max - 1, &Min, &Max);
			if (Min != Max) {
				front.push_back(Min);
			}
			back.push_back(Max);
		}
		reverse(back.begin(), back.end());
		vector<long long> A;
		for (auto v : front) {
			A.push_back(v);
		}
		for (auto v : back) {
			A.push_back(v);
		}
		long long gap = 0;
		for (int i = 0; i < N - 1; i++) {
			gap = max(gap, A[i + 1] - A[i]);
		}
		return gap;
  } else {
    long long x, y;
    MinMax(0, 1e18, &x, &y);
    long long size = (y - x - 1) / (N - 1) + 1;
    long long left = x + 1;
    long long gap = 0, max_pos = x;
    while (left < y) {
      long long right = min(y - 1, left + size - 1);
      long long Min, Max;
      MinMax(left, right, &Min, &Max);
      if (Min != -1) {
        gap = max(gap, Min - max_pos);
        max_pos = Max; 
      }
      left += size;
    }
    return max(gap, y - max_pos);
  }
}

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