Submission #152775

#	Time	Username	Problem	Language	Result	Execution time	Memory
152775		mhy908	Gap (APIO16_gap)	C++14	100 / 100	85 ms	3364 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define llinf 8987654321987654321
#define inf 1987654321
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
vector<LL> vc;
LL subt1(int n)
{
    LL fr=0, re=1e18, st, fin;
    while(fr<=re&&n){
        MinMax(fr, re, &st, &fin);
        vc.pb(st);
        n--;
        if(st!=fin){
            vc.pb(fin);
            n--;
        }
        fr=st+1;
        re=fin-1;
    }
    sort(all(vc));
    LL ans=0;
    for(int i=0; i<vc.size()-1; i++){
        ans=max(ans, vc[i+1]-vc[i]);
    }
    return ans;
}
LL subt2(int n)
{
    LL minn, maxx;
    MinMax(0, 1e18, &minn, &maxx);
    LL t=(maxx-minn)/(n-1);
    for(int i=1; ; i++){
        LL temp1, temp2;
        LL a=minn+t*(i-1)+i-1, b=min(a+t, maxx);
        MinMax(a, b, &temp1, &temp2);
        vc.pb(temp1);
        vc.pb(temp2);
        if(b>=maxx)break;
    }
    LL ans=0;
    sort(all(vc));
    for(int i=0; i<vc.size()-1; i++){
        ans=max(ans, vc[i+1]-vc[i]);
    }
    return ans;
}
LL findGap(int T, int N)
{
	if(T==1)return subt1(N);
	return subt2(N);
}

Compilation message (stderr)

gap.cpp: In function 'LL subt1(int)':
gap.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<vc.size()-1; i++){
                  ~^~~~~~~~~~~~
gap.cpp: In function 'LL subt2(int)':
gap.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<vc.size()-1; i++){
                  ~^~~~~~~~~~~~

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