Submission #167877

#	Time	Username	Problem	Language	Result	Execution time	Memory
167877		stefdasca	Gap (APIO16_gap)	C++14	100 / 100	67 ms	3832 KiB

gap

#include<bits/stdc++.h>
#include "gap.h"
using namespace std;

long long v[100002];

/*

int N;

long long A[100002];
void MinMax(long long s, long long t, long long *mn, long long *mx)
{
	int lo = 1, hi = N, left = N+1, right = 0;
	while (lo <= hi){
		int mid = (lo+hi)>>1;
		if (A[mid] >= s) hi = mid - 1, left = mid;
		else lo = mid + 1;
	}
	lo = 1, hi = N;
	while (lo <= hi){
		int mid = (lo+hi)>>1;
		if (A[mid] <= t) lo = mid + 1, right = mid;
		else hi = mid - 1;
	}
	if (left > right) *mn = *mx = -1;
	else{
		*mn = A[left];
		*mx = A[right];
	}
}
*/

long long findGap(int T, int N)
{
    long long ans = 0;
    long long st = 0;
    long long dr = 1;
    for(int i = 1; i <= 18; ++i)
        dr = dr * 10LL;
    if(T == 1)
    {
        int a = 1;
        int b = N;
        while(a <= b)
        {
            long long st2;
            long long dr2;
            if(a == 1)
                MinMax(st, dr, &st2, &dr2);
            else
                MinMax(st+1, dr-1, &st2, &dr2);
            v[a] = st2;
            v[b] = dr2;
            ++a;
            --b;
            st = st2;
            dr = dr2;
        }
        for(int i = 1; i < N; ++i)
            ans = max(ans, v[i+1] - v[i]);
    }
    else
    {
        long long st2;
        long long dr2;
        MinMax(st, dr, &st2, &dr2);
        st = st2;
        dr = dr2;
        long long max_val = dr;
        ans = (dr - st) / (N - 1);
        int ic = 0;
        while(st <= max_val)
        {
            dr = min(max_val, st + ans);
            if(max_val - st <= ans)
                break;
            long long sst = st + 1;
            while(1)
            {
                long long st2;
                long long dr2;
                ++ic;
               // cout << sst << " " << dr << '\n';
                MinMax(sst, dr, &st2, &dr2);
                if(dr2 == -1)
                {
                    sst = dr + 1;
                    dr = min(max_val, dr + ans);
                }
                else
                {
                    ans = max(ans, st2 - st);
                    st = dr2;
                    break;
                }
            }
        }
      //  cout << ic << '\n';
    }
    return ans;
}
/*
int main()
{
    cin >> N;
    for(int i = 1; i <= N; ++i)
        cin >> A[i];
    cout << findGap(2, N);
    return 0;
}
*/

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