Submission #311453

#	Time	Username	Problem	Language	Result	Execution time	Memory
311453		IgorI	Comparing Plants (IOI20_plants)	C++17	14 / 100	4059 ms	8824 KiB

plants

#include <bits/stdc++.h>

using namespace std;

int c;

const int N = 500000;

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]--;
    }
}

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];
    }
}

int compare_plants(int x, int y)
{
    if (H[x] > H[y]) return 1;
    return -1;
}

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