Submission #40155

#	Time	Username	Problem	Language	Result	Execution time	Memory
40155		SpaimaCarpatilor	Gap (APIO16_gap)	C++14	30 / 100	105 ms	9280 KiB

gap

#include "gap.h"
#include<bits/stdc++.h>

using namespace std;

long long x[100009];
const long long xmax = 1e18;

long long rand15 () {return rand () & 32767;}
long long rand30 () {return (rand15 () << 15LL) | rand15 ();}
long long rand60 () {return (rand30 () << 30LL) | rand30 ();}

vector < long long > divide (long long a, long long b)
{
    if (a > b) return {};
    long long mid = a + rand60 () % (b - a);
    long long x, y, z, t;
    MinMax (a, mid, &x, &y);
    MinMax (mid + 1, b, &z, &t);
    vector < long long > ans;
    if (x == -1) ;
    else
    {
        ans.push_back (x);
        if (x != y)
        {
            vector < long long > curr;
            curr = divide (x + 1, y - 1);
            for (auto it : curr)
                ans.push_back (it);
            curr.clear ();
            ans.push_back (y);
        }
    }
    if (z == -1) ;
    else
    {
        ans.push_back (z);
        if (z != t)
        {
            vector < long long > curr;
            curr = divide (z + 1, t - 1);
            for (auto it : curr)
                ans.push_back (it);
            curr.clear ();
            ans.push_back (t);
        }
    }
    return ans;
}

long long findGap(int T, int N)
{
    srand (time (0));
    if (T == 1)
    {
        long long a = 0, b = xmax;
        for (int i = 1, j = N; i<=j; i ++, j --)
            MinMax (a, b, &x[i], &x[j]), a = x[i] + 1, b = x[j] - 1;
        long long ans = x[2] - x[1];
        for (int i=1; i<N; i++)
            if (x[i + 1] - x[i] > ans)
                ans = x[i + 1] - x[i];
        return ans;
    }
    vector < long long > v = divide (0, xmax);
    long long ans = v[1] - v[0];
    for (int i=0; i<v.size () - 1; i++)
        ans = max (ans, v[i + 1] - v[i]);
	return ans;
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<v.size () - 1; i++)
                    ^

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