oj.uz

Submission #300265

# Submission time Handle Problem Language Result Execution time Memory
300265 2020-09-17T03:28:36 Z marX Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 6028 KB 
#include <vector>

using namespace std;

vector<int> xrank;

void init(int k, vector<int> r)
{
    int n = r.size();
    xrank.resize(n);

    vector<bool> used(n);

    int remaining = n;
    int pos = n;

    for (int i = 0; i < n; ++i, --remaining)
    {
        vector<int> current;
        for (int i = 0; i < n; ++i)
        {
            if (used[i])
                continue;

            if (r[i] == 0)
                current.push_back(i);
        }

        int start = 0;
        int max_diff = current[0] + n - current.back();

        for (int i = 1; i < current.size(); ++i)
        {
            int cur_diff = current[i] - current[i - 1];
            if (cur_diff > max_diff)
            {
                max_diff = cur_diff;
                start = i;
            }
        }

        if (current.empty())
            break;

        int u = current[start];
        used[u] = true;
        xrank[u] = pos--;

        for (int j = 1; j < k; ++j)
        {
            int t = (u - j + n) % n;
            r[t]--;
            // debug(t, u, r[t]);
        }

        // debug(i);
        // debug(current[start], current);
        // debug(used);
        // debug(r);
    }

    // debug(remaining);

    // if (remaining != 0)
    //     fin("FAIL!!!");
}

int compare_plants(int a, int b)
{
    return xrank[a] > xrank[b] ? +1 : -1;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:32:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i = 1; i < current.size(); ++i)
      |                         ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 10 ms 384 KB Output is correct
7 Correct 237 ms 3192 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 8 ms 384 KB Output is correct
10 Correct 225 ms 3192 KB Output is correct
11 Correct 186 ms 3192 KB Output is correct
12 Correct 166 ms 3320 KB Output is correct
13 Correct 265 ms 3192 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 10 ms 384 KB Output is correct
7 Correct 237 ms 3192 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 8 ms 384 KB Output is correct
10 Correct 225 ms 3192 KB Output is correct
11 Correct 186 ms 3192 KB Output is correct
12 Correct 166 ms 3320 KB Output is correct
13 Correct 265 ms 3192 KB Output is correct
14 Correct 2452 ms 3460 KB Output is correct
15 Execution timed out 4061 ms 4984 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 77 ms 3192 KB Output is correct
4 Execution timed out 4042 ms 6028 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 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Incorrect 0 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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