Submission #311455

#	Time	Username	Problem	Language	Result	Execution time	Memory
311455		IgorI	Comparing Plants (IOI20_plants)	C++17	11 / 100	95 ms	7288 KiB

plants

#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
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25