Submission #200733

#	Time	Username	Problem	Language	Result	Execution time	Memory
200733		Rakhmand	Gap (APIO16_gap)	C++14	30 / 100	139 ms	5888 KiB

gap

#include "gap.h"

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

using namespace std;
typedef long long llong;

long long a[100010];
set<llong> st;

void upd(llong l, llong r){
    //cout << "hey, you what you do? " << l << ' ' << r << endl;
    if(l >= r) return ;
    llong div = (r - l + 9) / 10;
    for(llong tl = l; tl <= r; tl += div){
        llong tr = min(tl + div - 1, r);
        //cout << "yoyy, I am here " << tl << ' ' << tr << endl;
        llong mn = NULL, mx = NULL;
        MinMax(tl, tr, &mn, &mx);
        if(mn == -1){
            continue;
        }else{
            st.insert(mn);
            if(mn != mx){
                st.insert(mx);
            }
            upd(mn + 1, mx - 1);
        }
    }
    
}

long long findGap(int T, int N)
{
    if(T == 1){
        int L = 1, R = N;
        long long l = 0, r = 1e18;
        while(R >= L){
            long long mn = NULL, mx = NULL;
            //cout << L << ' ' << R << ' ' << l << ' ' << r << endl;
            MinMax(l, r, &mn, &mx);
            //cout << mn << ' ' << mx << endl;
            a[L++] = mn;
            a[R--] = mx;
            l = mn + 1;
            r = mx - 1;
        }
        long long ans = 0;
        for(int i = 1; i < N; i++){
            //std::cout << a[i] << ' ';
            if(a[i + 1] - a[i] > ans){
                ans = a[i + 1] - a[i];
            }
        }
        return ans;
    }else{
        upd(1, (llong) 1e18);
        llong ans = 0;
        int last = -1;
        for(auto it : st){
            if(last != -1){
                if(it - last > ans){
                    ans = it - last;
                }
            }
            last = it;
        }
        return ans;
    }
    return 0;
}

Compilation message (stderr)

gap.cpp: In function 'void upd(llong, llong)':
gap.cpp:39:20: warning: converting to non-pointer type 'llong {aka long long int}' from NULL [-Wconversion-null]
         llong mn = NULL, mx = NULL;
                    ^~~~
gap.cpp:39:31: warning: converting to non-pointer type 'llong {aka long long int}' from NULL [-Wconversion-null]
         llong mn = NULL, mx = NULL;
                               ^~~~
gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:60:28: warning: converting to non-pointer type 'long long int' from NULL [-Wconversion-null]
             long long mn = NULL, mx = NULL;
                            ^~~~
gap.cpp:60:39: warning: converting to non-pointer type 'long long int' from NULL [-Wconversion-null]
             long long mn = NULL, mx = NULL;
                                       ^~~~

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