oj.uz

Submission #741410

# Submission time Handle Problem Language Result Execution time Memory
741410 2023-05-14T04:03:38 Z josanneo22 Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 10712 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int n_max = 10100;
bitset<n_max> adj[n_max];
vector<int> permutation;
void init(int k, std::vector<int> r) {
    int n = r.size();
    permutation.resize(n);
    for(int i=0; i<n; i++) {
        int streak = -n-1;
        for(int j=n-1; j>=0; j--) {
            if(r[j]==0) {
                streak = 0;
            } else {
                streak++;
            }
            if(streak==k-1) {
               for(int l=j; l<j+k-1; l++) {
                    r[l]--;
               }
               r[j+k-1] = 1e6;
               permutation[j+k-1] = i;
               break;
            }
            if(j==0) {
                for(int l=0; l<=streak; l++) {
                    r[l]--;
                }
                for(int l=n-k+streak+1; l<n; l++) {
                    r[l]--;
                }
                r[streak] = 1e6;
                permutation[streak] = i;
            }
        }
    }

    for(int i=0; i<n; i++) {
        for(int j=(i+n-k+1)%n; j!=i; j=(j+1)%n) {
            if(permutation[i]<permutation[j]) {
                adj[i][j] = true;
            } else {
                adj[j][i] = true;
            }
        }
    }

    for(int l=0; l<n; l++) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                adj[i][j] = adj[i][j] || (adj[i][l] && adj[l][j]);
            }
        }
    }
}

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

Subtask #1
0 / 5.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 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 43 ms 4060 KB Output is correct
7 Runtime error 180 ms 7784 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 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 4 ms 340 KB Output is correct
6 Correct 3852 ms 1628 KB Output is correct
7 Execution timed out 4041 ms 10712 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 304 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 4 ms 340 KB Output is correct
6 Correct 3852 ms 1628 KB Output is correct
7 Execution timed out 4041 ms 10712 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 81 ms 1512 KB Output is correct
8 Correct 104 ms 1536 KB Output is correct
9 Correct 81 ms 1528 KB Output is correct
10 Correct 116 ms 1516 KB Output is correct
11 Correct 76 ms 1516 KB Output is correct
12 Correct 79 ms 1516 KB Output is correct
13 Correct 102 ms 1520 KB Output is correct

Subtask #6
0 / 15.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 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3115 ms 1556 KB Output is correct
6 Execution timed out 4051 ms 7116 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 43 ms 4060 KB Output is correct
7 Runtime error 180 ms 7784 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -