제출 #1147791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147791		njoop	Gap (APIO16_gap)	C++17	30 / 100	2110 ms	589824 KiB

gap

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

long long mx, mn, l, r;
vector<long long> arr;

long long findAns() {
    long long ans = 0;
    sort(arr.begin(), arr.end());
    for(int i=0; i<arr.size()-1; i++) {
        ans = max(ans, arr[i+1]-arr[i]);
    }
    return ans;
}

long long findGap(int T, int N) {
    l=0; r=1e18;
    if(T == 1) {
        for(int i=1; i<=N/2; i++) {
            MinMax(l, r, &mn, &mx);
            if(mn == -1 || mx == -1) {
                break;
            }
            arr.push_back(mn);
            arr.push_back(mx);
            l = mn+1;
            r = mx-1;
        }
        if(N%2 == 1) {
            MinMax(l, r, &mn, &mx);
            arr.push_back(mn);
        }
        return findAns();
    }
    MinMax(l, r, &mn, &mx);
    l = mn;
    r = mx;
    arr.push_back(mn);
    arr.push_back(mx);
    long long in = (r-l+N+1)/(N+1)+1;
    if((r-l)/in > 1000000) return 0; 
    for(int j=l+1; j<r; j+=in) {
        MinMax(j, j+in-1, &mn, &mx);
        if(mn != -1 && mx != -1) {
            arr.push_back(mn);
            arr.push_back(mx);
        }
    }
    return findAns();
}

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