oj.uz

Submission #303230

# Submission time Handle Problem Language Result Execution time Memory
303230 2020-09-20T03:21:49 Z llaki Comparing Plants (IOI20_plants) Java 11
0 / 100
 81 ms 10308 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 10140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 10232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 10232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 10308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 10228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 10280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 10140 KB Output isn't correct
2 Halted 0 ms 0 KB -