oj.uz

Submission #307267

# Submission time Handle Problem Language Result Execution time Memory
307267 2020-09-27T13:41:30 Z VEGAnn Comparing Plants (IOI20_plants) C++14
11 / 100
 4000 ms 27856 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
const int N = 5010;
const int oo = 2e9;
queue<int> q;
vector<int> vc;
int per[N], mrk[N], tt = 0, n;
bool sml[N][N], g[N][N];

int dist(int fi, int se){
    if (se > fi)
        return se - fi;
    else return se - fi + n;
}

void init(int k, vector<int> r) {
    n = sz(r);

    for (int it = n - 1; it >= 0; it--){
        vc.clear();

        for (int i = 0; i < n; i++)
            if (r[i] == 0)
                vc.PB(i);

        int cand = -1, mx = -1;

        for (int it = 0; it < sz(vc); it++){
            int cur = vc[it];
            int pre = vc[(it + sz(vc) - 1) % sz(vc)];

            int dst = dist(pre, cur);

            if (dst > mx){
                mx = dst;
                cand = cur;
            }
        }

        per[cand] = it;
        r[cand] = oo;

        for (int i = 1, loc = cand; i < k; i++){
            loc = (loc + n - 1) % n;

            r[loc]--;

            if (r[loc] < oo / 2)
                g[cand][loc] = 1;
        }

        for (int i = 1, loc = cand; i < k; i++){
            loc = (loc + 1) % n;

            if (r[loc] < oo / 2)
                g[cand][loc] = 1;
        }
    }

    for (int i = 0; i < n; i++){
        tt++;

        q.push(i);
        mrk[i] = tt;

        while (sz(q)){
            int v = q.front(); q.pop();

            sml[i][v] = 1;

            for (int u = 0; u < n; u++)
                if (g[v][u] && mrk[u] < tt){
                    mrk[u] = tt;
                    q.push(u);
                }
        }
    }

    return;
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 62 ms 3320 KB Output is correct
7 Runtime error 63 ms 5756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 2312 ms 10488 KB Output is correct
7 Execution timed out 4075 ms 27856 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 3 ms 1152 KB Output is correct
6 Correct 2312 ms 10488 KB Output is correct
7 Execution timed out 4075 ms 27856 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Execution timed out 4056 ms 14956 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 3 ms 1152 KB Output is correct
7 Correct 25 ms 3320 KB Output is correct
8 Correct 73 ms 3576 KB Output is correct
9 Correct 48 ms 3448 KB Output is correct
10 Correct 72 ms 3576 KB Output is correct
11 Correct 31 ms 3320 KB Output is correct
12 Correct 47 ms 3412 KB Output is correct
13 Correct 76 ms 3576 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1621 ms 9552 KB Output is correct
6 Runtime error 78 ms 8440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 62 ms 3320 KB Output is correct
7 Runtime error 63 ms 5756 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -