Submission #240393

#	Time	Username	Problem	Language	Result	Execution time	Memory
240393		ctziapo	Gap (APIO16_gap)	C++14	30 / 100	78 ms	3272 KiB

gap

#include "gap.h"
#include<algorithm>
#include<cmath>
#include<vector>

using namespace std;


long long findGap(int T, int N)
{
    if(T==1){

	long long int mi,ma;
    int n=N;
	MinMax(1,1000000000000000000,&mi,&ma);

    long long int a[n+3];
	//cout<<mi<<" "<<ma<<endl;
	a[1]=mi;
	a[n]=ma;

	for(int i=2;i<=n/2;i++){
        //cout<<1;
        mi++;
        ma--;
        //cout<<" 22 "<<mi<<" "<<ma;
        MinMax(mi,ma,&mi,&ma);
      //  cout<<mi<<" "<<ma<<endl;
        a[i]=mi;
        a[n-i+1]=ma;
	}
	mi++;
	ma--;
	if(n%2==1){
        MinMax(mi,ma,&mi,&ma);
        a[n/2+1]=mi;
	}
	long long int ans=0;
	for(int i=2;i<=n;i++){
        ans=max(ans,a[i]-a[i-1]);
	}
	return ans;


    }
    else
    {

        long long int mi,ma;
        int n=N;
        MinMax(1,2000000000000000000,&mi,&ma);

        long long int a[n+3];

        vector <long long int > v;
        v.push_back(mi);
        long long int d=(ma-mi+1)/n;
        long long int s=mi;

        long long int ans=0;

        while(s+d<=ma){

            long long int t1,t2;
            MinMax(s,s+d,&t1,&t2);

            if(t1!=-1)
                v.push_back(t1);
            if(t2!=-1)
                v.push_back(t2);
           // cout<<t1<<" "<<t2;

            s+=(d);
        }
        v.push_back(ma);
        sort(v.begin(),v.end());
        for(int i=1;i<v.size();i++){
            ans=max(ans,v[i]-v[i-1]);
        }
        return ans;
    }


}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=1;i<v.size();i++){
                     ~^~~~~~~~~
gap.cpp:53:23: warning: unused variable 'a' [-Wunused-variable]
         long long int a[n+3];
                       ^

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