제출 #219833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219833		MKopchev	Gap (APIO16_gap)	C++14	100 / 100	82 ms	3412 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
const long long nmax=1e5+42,inf=1e18+42;

int n;
long long inp[nmax];
/*
void MinMax(long long low,long long up,long long &a,long long &b)
{
    cout<<low<<" "<<up<<endl;
    cin>>a;
    cin>>b;
}
*/
void ask(long long low,long long up,long long &mini,long long &maxi)
{
    MinMax(low,up,&mini,&maxi);//!
}
long long findGap(int T,int N)
{
    n=N;
    long long mini,maxi;

    ask(0,inf,mini,maxi);

    //cout<<"mini= "<<mini<<" maxi= "<<maxi<<endl;

    if(T==1)
    {
        inp[1]=mini;
        inp[n]=maxi;
        for(int le=2;le<=n+1-le;le++)
        {
            int ri=n+1-le;
            ask(inp[le-1]+1,inp[ri+1]-1,mini,maxi);
            inp[le]=mini;
            inp[ri]=maxi;
        }

        long long ret=0;
        for(int i=2;i<=n;i++)
            ret=max(ret,inp[i]-inp[i-1]);
        return ret;
    }
    //T=2

    if(n==2)return maxi-mini;

    long long low=(maxi-mini)/(n-1);

    vector<long long> noted={mini,maxi};

    for(long long mini_new=mini+1;mini_new<=noted[1];mini_new+=(low+1))
    {
        ask(mini_new,mini_new+low,mini,maxi);
        if(mini!=-1){noted.push_back(mini);noted.push_back(maxi);}
    }

    sort(noted.begin(),noted.end());

    long long ret=0;
    for(int i=1;i<noted.size();i++)
        ret=max(ret,noted[i]-noted[i-1]);

    return ret;
}
/*
int main()
{
    cout<<findGap(2,4)<<endl;
}
*/

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

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:63:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<noted.size();i++)
                 ~^~~~~~~~~~~~~

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