Submission #876163

#	Time	Username	Problem	Language	Result	Execution time	Memory
876163		PagodePaiva	Gap (APIO16_gap)	C++17	0 / 100	3087 ms	1460 KiB

gap

    #include<bits/stdc++.h>
    #define MAXN 100010
     
    using namespace std;
     
    #include "gap.h"
     
    int query(long long a, long long b, long long &x, long long &y){
        MinMax(a, b, &x, &y);
        return 0;
    }
     
    long long res[MAXN];
     
    long long findGap(int T, int n){
        long long l = 0, r = 1e18;

        query(l, r, res[0], res[n-1]);

        long long difmax = res[n-1] - res[0];
        long long resp = difmax/n;

        long long val = res[0];

        while(val <= res[n-1]){
            long long x, y;
            query(val+1, val+resp, x, y);

            if(x == -1){
                l = resp+1; r = res[n-1] - val;

                while(l < r){
                    int mid = (l+r)/2;

                    query(val+1, val+mid, x, y);

                    if(x == -1){
                        l = mid+1;
                    }

                    else{
                        r = y-val-1;
                    }
                }

                // cout << val << ' ' << l << ' ' << r << '\n';
                resp = max(l, r)+1;
                query(val+1, val+resp, x, y);
                val = y+1;
            }

            else{
                val = y+1;
            }
        }

        return resp;
    }

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