oj.uz

Submission #311455

# Submission time Handle Problem Language Result Execution time Memory
311455 2020-10-10T09:21:43 Z IgorI Comparing Plants (IOI20_plants) C++17
11 / 100
 95 ms 7288 KB 
#include <bits/stdc++.h>

using namespace std;

int c;

const int N = 350;

int H[N];

void call(int i, int k, int n, vector<int> &r, vector<int> &h1)
{
    for (int j = i - 1; j > i - k; j--)
    {
        int id = (j + n) % n;
        if (r[id] == 0 && h1[id] == 0)
        {
            call(id, k, n, r, h1);
        }
    }
    h1[i] = c--;
    for (int j = i - 1; j > i - k; j--)
    {
        int id = (j + n) % n;
        r[id]--;
    }
}

int higher[N][N];
int lower[N][N];

void init(int k, vector<int> r)
{
    int n = r.size();
    vector<int> h1(n);
    c = n;
    int t = 1;
    while (t)
    {
        t = 0;
        for (int i = 0; i < n; i++)
        {
            if (r[i] == 0 && h1[i] == 0)
            {
                call(i, k, n, r, h1);
                t = 1;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        H[i] = h1[i];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = i - k + 1; j < i + k; j++)
        {
            int id = (j + n) % n;
            if (H[i] > H[id]) higher[i][id] = 1;
            if (H[i] < H[id]) lower[i][id] = 1;
        }
    }
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (higher[i][k] && higher[k][j]) higher[i][j] = 1;
                if (lower[i][k] && lower[k][j]) lower[i][j] = 1;
            }
        }
    }
}

int compare_plants(int x, int y)
{
    if (higher[x][y]) return 1;
    if (lower[x][y]) return -1;
    return 0;
}

#ifdef LOCAL
int main()
{
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> r(n);
    for (int i = 0; i < n; i++) cin >> r[i];
    init(k, r);
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        cout << compare_plants(x, y) << endl;
    }
}
#endif

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 60 ms 3320 KB Output is correct
7 Runtime error 69 ms 5752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Runtime error 17 ms 2688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Runtime error 17 ms 2688 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 55 ms 7288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 56 ms 1784 KB Output is correct
8 Correct 89 ms 1860 KB Output is correct
9 Correct 64 ms 1788 KB Output is correct
10 Correct 92 ms 1784 KB Output is correct
11 Correct 57 ms 1784 KB Output is correct
12 Correct 60 ms 1784 KB Output is correct
13 Correct 95 ms 1784 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Runtime error 6 ms 2560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 60 ms 3320 KB Output is correct
7 Runtime error 69 ms 5752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -