oj.uz

Submission #307266

# Submission time Handle Problem Language Result Execution time Memory
307266 2020-09-27T13:41:11 Z VEGAnn Comparing Plants (IOI20_plants) C++14
14 / 100
 591 ms 28024 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;
    return (per[x] > per[y] ? 1 : -1);
}

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 Incorrect 1 ms 384 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 1 ms 256 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 768 KB Output is correct
6 Correct 21 ms 5248 KB Output is correct
7 Correct 507 ms 27896 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 21 ms 5240 KB Output is correct
10 Correct 497 ms 27896 KB Output is correct
11 Correct 376 ms 27256 KB Output is correct
12 Correct 324 ms 27512 KB Output is correct
13 Correct 591 ms 28024 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 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 768 KB Output is correct
6 Correct 21 ms 5248 KB Output is correct
7 Correct 507 ms 27896 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 21 ms 5240 KB Output is correct
10 Correct 497 ms 27896 KB Output is correct
11 Correct 376 ms 27256 KB Output is correct
12 Correct 324 ms 27512 KB Output is correct
13 Correct 591 ms 28024 KB Output is correct
14 Runtime error 63 ms 5624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 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 384 KB Output is correct
3 Correct 89 ms 11188 KB Output is correct
4 Runtime error 90 ms 9204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.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 Incorrect 0 ms 384 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 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -