Submission #163880

#	Time	Username	Problem	Language	Result	Execution time	Memory
163880		Kubalionzzale	Gap (APIO16_gap)	C++14	100 / 100	106 ms	4208 KiB

gap

#include "gap.h"
#include <vector>
#include <algorithm>
#include <assert.h>
#include <iostream>

long long findGap(int T, int n)
{
    long long int minValue = 0, maxValue = 1e18;
    std::vector<long long int> vec;
    if (T == 1)
    {
        long long int left = 0, right = 0;

        do
        {
            MinMax(minValue, maxValue, &left, &right);

            if (left != -1)
                vec.push_back(left);
            if (right != left)
                vec.push_back(right);

            minValue = left + 1;
            maxValue = right - 1;
        } while (minValue <= maxValue && left != -1 && right != -1 && vec.size() < n);

        std::sort(vec.begin(), vec.end());
        long long int maxi = 0;
        for (int i = 1; i < vec.size(); ++i)
        {
            if (vec[i] - vec[i - 1] > maxi)
                maxi = vec[i] - vec[i - 1];
        }

        return maxi;
    }
    else
    {
        long long int left = 0, right = 0;

        MinMax(minValue, maxValue, &left, &right);
        if (n == 2)
            return right - left;
        vec.push_back(left);
        vec.push_back(right);
        left = left + 1;
        right = right - 1;

        long long int dist = (right - left + 1) / (n - 2);
        long long int modul = (right - left + 1) % (n - 2);

        long long int nxt;
        long long int l, r;
        int cnt = 0;
        long long int i = left;
//        std::cout << left << " " << dist << " " << modul << " " << right << "\n";
        for (int cnt = 0; cnt < n - 2; ++cnt)
        {
            if (modul > 0)
            {
                nxt = i + dist;
                --modul;
            }
            else
                nxt = i + dist - 1;

            MinMax(i, nxt, &l, &r);
            if (l != -1)
            {
                vec.push_back(l);
                if (l != r)
                    vec.push_back(r);
            }

            i = nxt + 1;
        }

        std::sort(vec.begin(), vec.end());
        long long int maxi = 0;
        for (int i = 1; i < vec.size(); ++i)
        {
            if (vec[i] - vec[i - 1] > maxi)
                maxi = vec[i] - vec[i - 1];
        }

        return maxi;
    }
}

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int, int)':
gap.cpp:26:82: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         } while (minValue <= maxValue && left != -1 && right != -1 && vec.size() < n);
                                                                       ~~~~~~~~~~~^~~
gap.cpp:30:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1; i < vec.size(); ++i)
                         ~~^~~~~~~~~~~~
gap.cpp:81:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 1; i < vec.size(); ++i)
                         ~~^~~~~~~~~~~~
gap.cpp:55:13: warning: unused variable 'cnt' [-Wunused-variable]
         int cnt = 0;
             ^~~

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