제출 #1288619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288619		zagaro	Gap (APIO16_gap)	C++20	89.04 / 100	46 ms	3236 KiB

gap

#include<bits/stdc++.h>
#include "gap.h"
#include<ext/pb_ds/assoc_container.hpp>
/**zagaro & lauren <3**/
#define mod 1000000007 //1e9 + 7
#define pi acos(-1)
#define wl while
#define str string
#define ENDL "\n"
#define sal ' '
#define tp_set ll
#define prc(n) cout.precision(n);cout<<fixed;
#define ord_set tree<tp_set, null_type, less<tp_set>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef bool bl;
typedef char car;
using namespace std;
using namespace __gnu_pbds;
ll findGap(int T, int N){
    ll a, b, x, y, r=0, p, A;
    MinMax(ll(1), ll(1000000000000000000), &a, &b);
    if(T == 1){
        N-=2;
        wl(N > 0){
            MinMax(a+1, b-1, &x, &y);
            if(x == -1)break;
            r = max(r, max(x-a, b-y));
            a=x;b=y;
            N-=2;
        }
        r = max(r, b-a);
        return r;
    }
    p = (b-a)/(N-1);
    r=p;
    A=a;
    for(ll i=a;i+p<b;i+=p){
        MinMax(i+1, i+p, &x, &y);
        if(x != -1){
            r = max(r, x-A);
            A = y;
        }
    }
    MinMax(A+1, b-1, &x, &y);
    if(x != -1){
        r = max(r, x-A);
        A = y;
    }
    r = max(r, b-A);
	return r;
}

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