Submission #978508

# Submission time Handle Problem Language Result Execution time Memory
978508 2024-05-09T09:20:23 Z IUA_Hasin Gap (APIO16_gap) C++17
30 / 100
2000 ms 3788 KB
#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;
		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;
					l = tempr+1;
				}
			} else {
				break;
			}
		}

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

	}

}

Compilation message

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:104:1: warning: control reaches end of non-void function [-Wreturn-type]
  104 | }
      | ^
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 1 ms 2388 KB Output is correct
7 Correct 1 ms 2644 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2432 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 8 ms 2752 KB Output is correct
17 Correct 9 ms 2588 KB Output is correct
18 Correct 8 ms 2948 KB Output is correct
19 Correct 8 ms 2584 KB Output is correct
20 Correct 6 ms 2784 KB Output is correct
21 Correct 29 ms 3788 KB Output is correct
22 Correct 32 ms 3608 KB Output is correct
23 Correct 30 ms 3624 KB Output is correct
24 Correct 30 ms 3624 KB Output is correct
25 Correct 32 ms 3620 KB Output is correct
26 Correct 30 ms 3620 KB Output is correct
27 Correct 32 ms 3604 KB Output is correct
28 Correct 30 ms 3628 KB Output is correct
29 Correct 33 ms 3624 KB Output is correct
30 Correct 25 ms 3540 KB Output is correct
31 Correct 1 ms 2392 KB Output is correct
32 Correct 1 ms 2392 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Execution timed out 3075 ms 2392 KB Time limit exceeded
3 Execution timed out 3007 ms 2392 KB Time limit exceeded
4 Execution timed out 3041 ms 2392 KB Time limit exceeded
5 Correct 1 ms 2392 KB Output is correct
6 Execution timed out 3089 ms 2392 KB Time limit exceeded
7 Execution timed out 3029 ms 2392 KB Time limit exceeded
8 Execution timed out 3032 ms 2392 KB Time limit exceeded
9 Execution timed out 3030 ms 2400 KB Time limit exceeded
10 Execution timed out 3063 ms 2392 KB Time limit exceeded
11 Execution timed out 3045 ms 2392 KB Time limit exceeded
12 Execution timed out 3065 ms 2392 KB Time limit exceeded
13 Execution timed out 3036 ms 2392 KB Time limit exceeded
14 Execution timed out 3049 ms 2392 KB Time limit exceeded
15 Correct 1 ms 2392 KB Output is correct
16 Execution timed out 3017 ms 2588 KB Time limit exceeded
17 Execution timed out 3041 ms 2588 KB Time limit exceeded
18 Execution timed out 3042 ms 2580 KB Time limit exceeded
19 Execution timed out 3076 ms 2580 KB Time limit exceeded
20 Execution timed out 3013 ms 2572 KB Time limit exceeded
21 Execution timed out 3057 ms 2848 KB Time limit exceeded
22 Execution timed out 3028 ms 2852 KB Time limit exceeded
23 Execution timed out 3017 ms 2860 KB Time limit exceeded
24 Execution timed out 3061 ms 2732 KB Time limit exceeded
25 Correct 39 ms 2940 KB Output is correct
26 Execution timed out 3042 ms 2856 KB Time limit exceeded
27 Execution timed out 3066 ms 2856 KB Time limit exceeded
28 Execution timed out 3036 ms 2860 KB Time limit exceeded
29 Execution timed out 3100 ms 2856 KB Time limit exceeded
30 Execution timed out 3022 ms 2856 KB Time limit exceeded
31 Execution timed out 3009 ms 2476 KB Time limit exceeded
32 Execution timed out 3069 ms 2392 KB Time limit exceeded