oj.uz

Submission #163880

# Submission time Handle Problem Language Result Execution time Memory
163880 2019-11-15T23:03:17 Z Kubalionzzale Gap (APIO16_gap) C++14
100 / 100
 106 ms 4208 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 448 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 21 ms 876 KB Output is correct
17 Correct 16 ms 1400 KB Output is correct
18 Correct 17 ms 1404 KB Output is correct
19 Correct 17 ms 1272 KB Output is correct
20 Correct 14 ms 1144 KB Output is correct
21 Correct 61 ms 3568 KB Output is correct
22 Correct 63 ms 3900 KB Output is correct
23 Correct 106 ms 3440 KB Output is correct
24 Correct 63 ms 4108 KB Output is correct
25 Correct 54 ms 3568 KB Output is correct
26 Correct 61 ms 4080 KB Output is correct
27 Correct 61 ms 4140 KB Output is correct
28 Correct 62 ms 4208 KB Output is correct
29 Correct 61 ms 4188 KB Output is correct
30 Correct 47 ms 3016 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 4 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 3 ms 380 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 20 ms 888 KB Output is correct
17 Correct 20 ms 888 KB Output is correct
18 Correct 20 ms 1016 KB Output is correct
19 Correct 20 ms 1144 KB Output is correct
20 Correct 10 ms 760 KB Output is correct
21 Correct 78 ms 3960 KB Output is correct
22 Correct 80 ms 4060 KB Output is correct
23 Correct 76 ms 4076 KB Output is correct
24 Correct 76 ms 3184 KB Output is correct
25 Correct 70 ms 3440 KB Output is correct
26 Correct 77 ms 3824 KB Output is correct
27 Correct 76 ms 3696 KB Output is correct
28 Correct 77 ms 3700 KB Output is correct
29 Correct 77 ms 3728 KB Output is correct
30 Correct 40 ms 2040 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 376 KB Output is correct