제출 #484131

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484131		beaconmc	Gap (APIO16_gap)	C++14	100 / 100	68 ms	2324 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
typedef long long ll;
#define FOR(i, x, y) for(ll i=(x); i<(y); i++)
#define MAX18 1000000000000000000
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
  
#define ordered_set tree<ll, null_type,greater_equal<int>, rb_tree_tag,tree_order_statistics_node_update>


ll findGap(int t, int n){
    if (t==1){
        vector<ll> sussy;
        sussy.clear();
        ll l=0; ll r=MAX18;
        ll lc=0; ll rc=0;
        while (l<r){
            MinMax(l,r,&lc,&rc);
            if (lc!=-1){
                sussy.push_back(lc);
                if (lc!=rc) sussy.push_back(rc);
            }
            if (sussy.size() == n) break;
            l = lc+1; r=rc-1;
        }
        sort(sussy.begin(), sussy.end());
        ll maxi=0;
        FOR(i, 0, n-1) maxi = max(maxi, sussy[i+1]-sussy[i]);
        return maxi;   
    }
    vector<ll> sussy;
    sussy.clear();
    ll l=0; ll r=MAX18;
    ll lc=0; ll rc=0;
    MinMax(l,r,&lc,&rc);

    sussy.push_back(lc);sussy.push_back(rc);
    l = lc; r = lc;
    ll rightmost = rc;
    ll gap = (rc - lc-1)/(n-1)+1;
    while (r<rightmost){
        l = r+1;r = l+gap;
        MinMax(l,min(r, rightmost-1),&lc,&rc);
        if (lc!=-1){
            sussy.push_back(lc);
            if (lc!=rc)sussy.push_back(rc);
        }
    }

    sort(sussy.begin(), sussy.end());
    ll maxi=0;
    ll prv = sussy[0];
    for (auto&i : sussy){
        maxi = max(maxi, i-prv);
        prv = i;
    }
    return maxi;

}

/*
int main(){
}
*/

컴파일 시 표준 에러 (stderr) 메시지

gap.cpp: In function 'll findGap(int, int)':
gap.cpp:27:30: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |             if (sussy.size() == n) break;
      |                 ~~~~~~~~~~~~~^~~~

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