제출 #112245

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
112245	2019-05-18 04:49:31	user202729	Gap (APIO16_gap)	C++17	70 / 100	61 ms	1272 KiB

gap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "gap.h"
#include<vector>
// #include<iostream>
using ll=long long;
ll findGap(int t, int n)
{
  if(t==2){
    ll a0,an;
    MinMax(0,1000000000000000000LL,&a0,&an);
    int n_gap=n-1;
    ll const sum_gap=an-a0;
    ll const min_gap=(sum_gap+n_gap-1)/n_gap;
    // std::cerr<<"a0 an min_gap="<<a0<<' '<<an<<' '<<min_gap<<'\n';
    // divide [a0..an] into [a0..a0+min_gap[, [a0+min_gap..a0+2*min_gap[, ...
    // the last segment should contain an
    ll _,prev_end; // max value of last segment
    MinMax(a0+1,a0+min_gap-1,&_,&prev_end);
    if(prev_end==-1)prev_end=a0;
    ll start_next=a0+min_gap;
    ll ans=min_gap;
    while(an>=start_next){
      ll cur_start,cur_end;
      MinMax(start_next,start_next+min_gap-1,&cur_start,&cur_end);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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