oj.uz

Submission #834015

# Submission time Handle Problem Language Result Execution time Memory
834015 2023-08-22T10:09:15 Z finn__ Comparing Plants (IOI20_plants) C++17
19 / 100
 4000 ms 5112 KB 
#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 - 1; ++i)
        {
            int conseq_nonzero = 0, next_max = 0;
            for (size_t j = 0; j < 2 * n;)
            {
                while (j < 2 * n && !r[j % n])
                    ++j;
                size_t k = j;
                while (k < 2 * n && r[k % n])
                    ++k;
                if (k - j > conseq_nonzero)
                    conseq_nonzero = k - j, next_max = k % n;
                j = k;
            }

            h[next_max] = n - i;
            r[next_max] = -1;

            for (int j = next_max - k + 1; j < next_max; ++j)
                r[(j + (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

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:36:27: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |                 if (k - j > conseq_nonzero)
      |                     ~~~~~~^~~~~~~~~~~~~~~~
plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:55:83: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         return !z ? 1 : (z == y - x ? -1 : (!(s[n - 1] - z) ? -1 : ((s[n - 1] - z == n - (y - x) ? 1 : 0))));
      |                                                                      ~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 54 ms 3052 KB Output is correct
7 Correct 58 ms 3264 KB Output is correct
8 Correct 79 ms 4980 KB Output is correct
9 Correct 75 ms 4976 KB Output is correct
10 Correct 58 ms 4976 KB Output is correct
11 Correct 61 ms 5040 KB Output is correct
12 Correct 84 ms 4976 KB Output is correct
13 Correct 72 ms 4952 KB Output is correct
14 Correct 55 ms 4940 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 260 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 14 ms 340 KB Output is correct
7 Correct 347 ms 4996 KB Output is correct
8 Correct 2 ms 464 KB Output is correct
9 Correct 14 ms 340 KB Output is correct
10 Correct 353 ms 5092 KB Output is correct
11 Correct 311 ms 5108 KB Output is correct
12 Correct 308 ms 5112 KB Output is correct
13 Correct 364 ms 5032 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 260 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 14 ms 340 KB Output is correct
7 Correct 347 ms 4996 KB Output is correct
8 Correct 2 ms 464 KB Output is correct
9 Correct 14 ms 340 KB Output is correct
10 Correct 353 ms 5092 KB Output is correct
11 Correct 311 ms 5108 KB Output is correct
12 Correct 308 ms 5112 KB Output is correct
13 Correct 364 ms 5032 KB Output is correct
14 Execution timed out 4090 ms 5068 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 82 ms 3064 KB Output is correct
4 Execution timed out 4046 ms 4244 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 54 ms 3052 KB Output is correct
7 Correct 58 ms 3264 KB Output is correct
8 Correct 79 ms 4980 KB Output is correct
9 Correct 75 ms 4976 KB Output is correct
10 Correct 58 ms 4976 KB Output is correct
11 Correct 61 ms 5040 KB Output is correct
12 Correct 84 ms 4976 KB Output is correct
13 Correct 72 ms 4952 KB Output is correct
14 Correct 55 ms 4940 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 260 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 14 ms 340 KB Output is correct
21 Correct 347 ms 4996 KB Output is correct
22 Correct 2 ms 464 KB Output is correct
23 Correct 14 ms 340 KB Output is correct
24 Correct 353 ms 5092 KB Output is correct
25 Correct 311 ms 5108 KB Output is correct
26 Correct 308 ms 5112 KB Output is correct
27 Correct 364 ms 5032 KB Output is correct
28 Execution timed out 4090 ms 5068 KB Time limit exceeded
29 Halted 0 ms 0 KB -