Submission #833970

#	Time	Username	Problem	Language	Result	Execution time	Memory
833970		finn__	Comparing Plants (IOI20_plants)	C++17	5 / 100	73 ms	4988 KiB

plants

#include <bits/stdc++.h>

#include "plants.h"

using namespace std;

constexpr size_t N = 200000;

size_t n;
int subtask, s[N], h[N];

void init(int k, std::vector<int> r)
{
    n = r.size();
    if (k == 2)
        subtask = 1;
    else
        subtask = 2;

    if (subtask == 1)
    {
        partial_sum(r.begin(), r.end(), s);
    }
    else
    {
        for (size_t i = 0; i < n; ++i)
        {
            size_t conseq_nonzero = 0, l = 0;
            for (size_t j = 0; j < n;)
            {
                while (j < n && !r[j])
                    ++j;
                size_t k = j;
                while (k < n && r[k])
                    ++k;
                if (k - j > conseq_nonzero)
                    conseq_nonzero = k - j, l = k;
                j = k;
            }

            int next_max;
            if (conseq_nonzero > n / 2)
            {
                next_max = l;
            }
            else
            {
                next_max = 0;
                while (r[next_max])
                    ++next_max;
            }
            h[next_max] = n - i;

            for (int i = next_max - k; i < next_max; ++i)
                r[(i + (int)n) % n]--;
        }
    }
}

int compare_plants(int x, int y)
{
    if (subtask == 1)
    {
        int z = s[y - 1] - (x ? s[x - 1] : 0);
        return !z ? 1 : (z == y - x ? -1 : (!(s[n - 1] - z) ? -1 : ((s[n - 1] - z == n - (y - x) ? 1 : 0))));
    }
    else
    {
        return h[x] > h[y] ? 1 : -1;
    }
}

Compilation message (stderr)

plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:65:83: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         return !z ? 1 : (z == y - x ? -1 : (!(s[n - 1] - z) ? -1 : ((s[n - 1] - z == n - (y - x) ? 1 : 0))));
      |                                                                      ~~~~~~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25