oj.uz

Submission #303231

# Submission time Handle Problem Language Result Execution time Memory
303231 2020-09-20T03:24:27 Z llaki Comparing Plants (IOI20_plants) Java 11
5 / 100
 498 ms 28908 KB 
import java.util.Arrays;

public class plants {
    int n;
    int[] nxt;
    int[] r;

    void init(int k, int[] r) {
        n = r.length;
        nxt = new int[n];
        this.r = r;
        // r[i] = (a[i] > a[(i + 1)%n] ? 1 : 0)
        // x -> find smallest z on circle clockwise s.t. r[z] != r[x].
        // If y is between x and z (clockwise), than ans(x,y) = r[x].

        // r[x] = r[x+1] = ... = r[s] = 1 => a[x] > a[x+1] > a[x+2] > ... > a[s + 1]
        // r[x] = r[x+1] = ... = r[s] = -1 => a[x] < a[x+1] < a[x+2] > ... < a[s + 1]
        // nxt[x] = smallest y s.t. nxt[y] != nxt[x]. for query z s.t. x < z <= nxt[x] + 1, comp(x,z) known.
        for (int i = 0; i < n; i++) {
            int j = i;
            boolean jump = false;
            while (r[(j + 1) % n] == r[i]) {
                j = (j + 1) % n;
                if (j == 0) jump = true;
            }
            // r[i] = r[i+1] = ... = r[j] != r[j + 1].
            if (i <= j) {
                for (int x = i; x <= j; x++) {
                    nxt[x] = (j + 1) % n;
                }
            } else {
                for (int x = i; x <= n - 1; x++) {
                    nxt[x] = (j + 1) % n;
                }
                for (int x = 0; x <= j; x++) {
                    nxt[x] = (j + 1) % n;
                }
            }
            if (jump) break;
            i = j;
        }
        //System.out.println(Arrays.toString(nxt));
    }

    boolean between(int l, int r, int x) {
        if (l <= r) {
            return l <= x && x <= r;
        }
        return (l <= x && x <= n - 1) || (0 <= x && x <= r);
    }

    int compare_plants(int x, int y) {
        // r[x] > r[x+1] > ... > r[j].
        if (between(x, nxt[x], y)) {
            return r[x] > 0 ? -1 : +1;
        }
        if (between(y, nxt[y], x)) {
            return r[y] > 0 ? +1 : -1;
        }
        return 0;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10352 KB Output is correct
2 Correct 75 ms 10104 KB Output is correct
3 Correct 78 ms 10224 KB Output is correct
4 Correct 78 ms 10228 KB Output is correct
5 Correct 86 ms 10180 KB Output is correct
6 Correct 355 ms 26696 KB Output is correct
7 Correct 345 ms 26924 KB Output is correct
8 Correct 362 ms 27652 KB Output is correct
9 Correct 423 ms 28908 KB Output is correct
10 Correct 498 ms 28184 KB Output is correct
11 Correct 415 ms 26356 KB Output is correct
12 Correct 380 ms 26540 KB Output is correct
13 Correct 318 ms 28028 KB Output is correct
14 Correct 420 ms 28636 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 10328 KB Output is correct
2 Correct 78 ms 10100 KB Output is correct
3 Incorrect 79 ms 10216 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 10328 KB Output is correct
2 Correct 78 ms 10100 KB Output is correct
3 Incorrect 79 ms 10216 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 10220 KB Output is correct
2 Incorrect 82 ms 10340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 10236 KB Output is correct
2 Correct 79 ms 10240 KB Output is correct
3 Correct 83 ms 10456 KB Output is correct
4 Incorrect 82 ms 10104 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 10228 KB Output is correct
2 Correct 77 ms 10232 KB Output is correct
3 Correct 76 ms 10108 KB Output is correct
4 Incorrect 77 ms 10360 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 10352 KB Output is correct
2 Correct 75 ms 10104 KB Output is correct
3 Correct 78 ms 10224 KB Output is correct
4 Correct 78 ms 10228 KB Output is correct
5 Correct 86 ms 10180 KB Output is correct
6 Correct 355 ms 26696 KB Output is correct
7 Correct 345 ms 26924 KB Output is correct
8 Correct 362 ms 27652 KB Output is correct
9 Correct 423 ms 28908 KB Output is correct
10 Correct 498 ms 28184 KB Output is correct
11 Correct 415 ms 26356 KB Output is correct
12 Correct 380 ms 26540 KB Output is correct
13 Correct 318 ms 28028 KB Output is correct
14 Correct 420 ms 28636 KB Output is correct
15 Correct 84 ms 10328 KB Output is correct
16 Correct 78 ms 10100 KB Output is correct
17 Incorrect 79 ms 10216 KB Output isn't correct
18 Halted 0 ms 0 KB -