Submission #978514

#	Time	Username	Problem	Language	Result	Execution time	Memory
978514		IUA_Hasin	Gap (APIO16_gap)	C++17	89.02 / 100	44 ms	3868 KiB

gap

#include "gap.h"

#include <bits/stdc++.h>

#define ll						long long

using namespace std;

long long findGap(int T, int N)
{
	if(T==1){
		ll tempa = 0;
		ll tempb = 1e18;
		ll arr[N];
		ll l = 0;
		ll r = N-1;

		// cout<<tempa<< " " << tempb<<endl;

		while(true){
			if(l<=r){
				ll mn, mx;
				MinMax(tempa, tempb, &mn, &mx);
				// cout<<mn<<" "<<mx<<endl;
				mn = (ll)mn;
				mx = (ll)mx;
				if(mn==-1 || mx==-1){
					break;
				} else if(mn==mx){
					arr[l] = mn;
					break;
				} else {
					tempa = (ll)(mn+1);
					tempb = (ll)(mx-1);
					arr[l] = (ll)mn;
					arr[r] = (ll)mx;
					l++;
					r--;
				}
			} else {
				break;
			}
		}

		ll ans = 0;

		// for(int i=0; i<N; i++){
		// 	cout << arr[i] << " ";
		// }
		// cout<<endl;

		for(int i=1; i<N; i++){
			ll temp = (ll)(arr[i]-arr[i-1]);
			ans = (ll)(max(temp, ans));
		}

		ans = (ll)(ans);
		
		return ans;
	} else if(T==2){
		ll mn, mx;
		ll a = 0;
		ll b = 1e18;
		MinMax(a, b, &mn, &mx);

		ll c = mx-mn;
		ll step;
		if(c%(N-1)==0){
			step = c/(N-1);
		} else {
			step = floor(c/N-1)+1;
		}
		
		ll ans = step;
		ll left = mn;
		ll l = mn+1;
		ll r = mx;
		ll x, y;
		while(true){
			ll templ = l;
			ll tempr = l+step;
			if(tempr<mx){
				MinMax(templ, tempr, &x, &y);
				if(x!=-1){
					ans = max(ans, x-left);
					left = y;
				}
			} else {
				break;
			}
			l = tempr+1;
		}

		ll templ = l;
		ll tempr = mx;
		if(templ!=tempr){
			MinMax(templ, tempr, &x, &y);
			if(x!=-1){
				ans = max(ans, x-left);
			}
		}
		return ans;

	}

}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:77:6: warning: unused variable 'r' [-Wunused-variable]
   77 |   ll r = mx;
      |      ^
gap.cpp:106:1: warning: control reaches end of non-void function [-Wreturn-type]
  106 | }
      | ^

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