Submission #321773

#	Time	Username	Problem	Language	Result	Execution time	Memory
321773		grt	Comparing Plants (IOI20_plants)	C++17	14 / 100	166 ms	11756 KiB

plants

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ll = long long;
using pi = pair<int,int>;

#define ST first
#define ND second
#define PB push_back

const int nax = 5000 + 10, INF = 1e9 + 10;
int n, k;
int val[nax];
int num[nax];

void upd(int a, int b, int x) {
    for(int i = a; i <= b; ++i) val[i] += x;
}

int qr() {
    vi zero = {};
    for(int i = 0; i < n; ++i) if(val[i] == 0) zero.PB(i);
    if((int)zero.size() == 1) return zero[0];
    for(int i = 1; i < (int)zero.size(); ++i) {
        if(zero[i] - zero[i - 1] >= k) {
            return zero[i];
        }
    }
    return zero[0];
}

void init(int K, vi r) {
    k = K;
    n = (int)r.size();
    for(int i = 0; i < n; ++i) val[i] = r[i];
    int cur = n;
    for(int step = 0; step < n; ++step) {
        int x = qr();
        upd(x, x, INF);
        num[x] = cur--;
        upd(max(0, x - k + 1),x-1, -1);
        upd(x - k + 1 + n, n - 1, -1);
    }
}

int compare_plants(int x, int y) {
    if(num[x] < num[y]) return -1;
    else return 1;
}

//int main() {
//    init(3, {0, 1, 1, 2});
//    cout << compare_plants(0, 2) << "\n";
//    cout << compare_plants(1, 2) << "\n";
//}

• 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