Submission #1222184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222184		kargneq	Comparing Plants (IOI20_plants)	C++20	0 / 100	0 ms	328 KiB

plants

#include <bits/stdc++.h>
using namespace std;

vector<int> r;
int n, k;

void init(int kk, std::vector<int> rr) {
    r = rr;
    n = r.size();
    k = kk;
}

int compare_plants(int x, int y) {
    // For all i, check if both x and y are in the window of i
    // Window: (i+1)%n, ..., (i+k-1)%n
    for (int i = 0; i < n; ++i) {
        vector<int> window;
        for (int j = 1; j < k; ++j) {
            window.push_back((i + j) % n);
        }
        bool has_x = false, has_y = false;
        for (int v : window) {
            if (v == x) has_x = true;
            if (v == y) has_y = true;
        }
        if (has_x && has_y) {
            // If r[i] == 0, all in window are shorter than i, can't compare x and y
            // If r[i] == k-1, all in window are taller than i, can't compare x and y
            // If r[i] == 1, exactly one in window is taller than i
            if (r[i] == 1) {
                // Try x is the only taller
                if (x != y) {
                    // Try x is the only taller
                    bool x_taller = true;
                    for (int v : window) {
                        if (v != x && v != y) x_taller = false;
                    }
                    if (x_taller) return 1;
                    // Try y is the only taller
                    bool y_taller = true;
                    for (int v : window) {
                        if (v != x && v != y) y_taller = false;
                    }
                    if (y_taller) return -1;
                }
            }
        }
    }
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25