oj.uz

Submission #800253

# Submission time Handle Problem Language Result Execution time Memory
800253 2023-08-01T12:48:42 Z PixelCat Comparing Plants (IOI20_plants) C++14
14 / 100
 4000 ms 5580 KB 
#include "plants.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 5000;

int rk[MAXN + 10];

int dist(int s, int t, int n) {
    if(s <= t) return t - s;
    else return t - s + n;
}

void init(int k, vector<int> r) {
    int n = sz(r);
    vector<int> alive(n, 1);
    int cnt = n;
    int rank = 0;
    while(cnt > 0) {
        rank++;
        vector<int> idx;
        For(i, 0, n - 1) if(alive[i]) {
            if(r[i] == 0 && (sz(idx) == 0 || dist(idx.back(), i, n) >= k)) {
                idx.eb(i);
            }
        }
        // cerr << idx << "\n";
        // For(i, 0, n - 1) cerr << r[i] << " \n"[i == n - 1];
        // for(auto &i:idx) cerr << i << " ";
        // cerr << "\n";
        reverse(all(idx));
        while(sz(idx) > 1 && dist(idx[0], idx.back(), n) < k) idx.pop_back();
        for(auto &i:idx) {
            rk[i] = rank;
            For(j, n - k + 1, n - 1) r[(i + j) % n]--;
            alive[i] = 0;
            cnt--;
        }
        // rk[idx] = rank;
        // For(i, n - k + 1, n - 1) r[(idx + i) % n]--;
        // alive[idx] = 0;
        // cnt--;
    }
}

int compare_plants(int x, int y) {
    if(rk[x] == rk[y]) return 0;
    if(rk[x] < rk[y]) return 1;
    return -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 340 KB Output is correct
7 Correct 195 ms 3108 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 7 ms 340 KB Output is correct
10 Correct 192 ms 3108 KB Output is correct
11 Correct 152 ms 3020 KB Output is correct
12 Correct 152 ms 3240 KB Output is correct
13 Correct 215 ms 3104 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 340 KB Output is correct
7 Correct 195 ms 3108 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 7 ms 340 KB Output is correct
10 Correct 192 ms 3108 KB Output is correct
11 Correct 152 ms 3020 KB Output is correct
12 Correct 152 ms 3240 KB Output is correct
13 Correct 215 ms 3104 KB Output is correct
14 Runtime error 28 ms 5580 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 4070 ms 212 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -