Submission #2846392


Source Code Expand

Copy
import java.io.*;
import java.util.*;

public class Main {
    FastScanner in;
    PrintWriter out;

    final int mod = (int) 1e9 + 7;

    int add(int x, int y) {
        x += y;
        return x >= mod ? (x - mod) : x;
    }

    int mul(int x, int y) {
        return (int) ((x * 1L * y) % mod);
    }

    int pow(int x, int y) {
        if (y == 0) {
            return 1;
        }
        int t = pow(x, y / 2);
        t = mul(t, t);
        if (y % 2 == 1) {
            t = mul(t, x);
        }
        return t;
    }

    class Position {
        int left, right, h;
        int lValue, rValue;
        boolean changed;

        public Position(int left, int right, int h, int lValue, int rValue, boolean changed) {
            this.left = left;
            this.right = right;
            this.h = h;
            this.lValue = lValue;
            this.rValue = rValue;
            this.changed = changed;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Position position = (Position) o;
            return left == position.left &&
                    right == position.right &&
                    h == position.h &&
                    lValue == position.lValue &&
                    rValue == position.rValue &&
                    changed == position.changed;
        }

        @Override
        public int hashCode() {
            return Objects.hash(left, right, h, lValue, rValue, changed);
        }

        @Override
        public String toString() {
            return "Position{" +
                    "left=" + left +
                    ", right=" + right +
                    ", h=" + h +
                    ", lValue=" + lValue +
                    ", rValue=" + rValue +
                    ", changed=" + changed +
                    '}';
        }
    }

    HashMap<Position, Integer> ans = new HashMap<>();

    int calcAns(Position p) {
        if (p.left == p.right && p.lValue != p.rValue) {
            return 0;
        }
//        if (p.h == 1 && p.lValue == 0 && p.rValue == 0 && p.changed == false && p.left == 0 && p.right== 1) {
//            System.err.println("!!!");
//        }
        int cnt = p.right - p.left + 1;
        if (cnt == 2 && p.changed == false && p.lValue != p.rValue) {
            return 0;
        }
        if (cnt == 1 && p.changed == false) {
            return 0;
        }
        if (p.changed) {
            if (cnt % 2 == 0) {
                if (p.lValue == p.rValue) {
                    return 0;
                }
            } else {
                if (p.lValue != p.rValue) {
                    return 0;
                }
            }
        }
        int min = minH[p.left][p.right];
        if (min != p.h) {
            if (p.changed) {
                int diff = min - p.h;
                int mul = pow(2, diff - 1);
                int res = 0;
                for (int lVal = 0; lVal < 2; lVal++) {
                    for (int rVal = 0; rVal < 2; rVal++) {
                        res = add(res, getAns(new Position(p.left, p.right, min, lVal, rVal, true)));
                    }
                }
                return mul(mul, res);
            } else {
                int diff = (min - p.h) % 2;
                return getAns(new Position(p.left, p.right, min, p.lValue ^ diff, p.rValue ^ diff, p.changed));
            }
        } else {
            if (maxH[p.left][p.right] == p.h) {
                if (p.changed) {
                    return 1;
                } else {
                    int res =  pow(2, cnt - 2);
                    if (cnt % 2 == 0) {
                        if (p.lValue != p.rValue) {
                            res--;
                        }
                    } else {
                        if (p.lValue == p.rValue) {
                            res--;
                        }
                    }
                    if (res < 0) {
                        res += mod;
                    }
                    return res;
                }
            } else {
                boolean eqH = h[p.left] == p.h;
                for (int pos = p.left + 1; pos <= p.right; pos++) {
                    boolean curEqH = (h[pos] == p.h);
                    if (curEqH != eqH) {
                        int res = 0;
                        for (int x = 0; x < 2; x++) {
                            for (int y = 0; y < 2; y++) {
                                for (int z1 = 0; z1 < 2; z1++) {
                                    for (int z2 = 0; z2 < 2; z2++) {
                                        boolean c1 = z1 == 0, c2 = z2 == 0;
                                        boolean nextChange = c1 && c2 && (x != y);
                                        if (nextChange != p.changed) {
                                            continue;
                                        }
                                        int f = mul(getAns(new Position(p.left, pos - 1, p.h, p.lValue, x, c1)), getAns(new Position(pos, p.right, p.h, y, p.rValue, c2)));
                                        res = add(res, f);
                                    }
                                }
                            }
                        }
                        return res;
                    }
                }
                throw new AssertionError();
            }
        }
    }

    int getAns(Position p) {
        if (ans.containsKey(p)) {
            return ans.get(p);
        }
        int r = calcAns(p);
//        if (r != 0 && p.h == 2 && p.left == 1 && p.right == 1)
//            System.err.println(p + " -> " + r);
        ans.put(p, r);
        return r;
    }

    int n;
    int[] h;
    int[][] minH;
    int[][] maxH;

    void solve() {
        n = in.nextInt();
        h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = in.nextInt();
        }
        minH = new int[n][n];
        maxH = new int[n][n];
        for (int i = 0; i < n; i++) {
            int f = Integer.MAX_VALUE;
            int g = 0;
            for (int j = i; j < n; j++) {
                f = Math.min(f, h[j]);
                g = Math.max(g, h[j]);
                minH[i][j] = f;
                maxH[i][j] = g;
            }
        }
        int res = 0;
        for (int l = 0; l < 2; l++) {
            for (int r = 0; r < 2; r++) {
                res = add(res, getAns(new Position(0, n - 1, 1, l, r, true)));
                res = add(res, getAns(new Position(0, n - 1, 1, l, r, false)));
            }
        }
        out.println(res);
    }


    void run() {
        try {
            in = new FastScanner(new File("Main.in"));
            out = new PrintWriter(new File("Main.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void main(String[] args) {
        new Main().runIO();
    }
}

Submission Info

Submission Time
Task D - Histogram Coloring
User qwerty787788
Language Java8 (OpenJDK 1.8.0)
Score 1100
Code Size 9060 Byte
Status
Exec Time 112 ms
Memory 27604 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example_0, example_1, example_2, example_3
All 1100 / 1100 bigrand_0, bigrand_1, bigrand_2, bigrand_3, bigrand_4, bigrand_5, bigrand_6, bigrand_7, bigrand_8, bigrand_9, example_0, example_1, example_2, example_3, perm2_0, perm2_1, perm2_2, perm2_3, perm2_4, perm2_5, perm_0, perm_1, perm_2, perm_3, perm_4, perm_5, rand_0, rand_1, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9, smallc_0, smallc_1, smallc_2, smallc_3, smallc_4, smallc_5, smallc_6, smallc_7, smallc_8, smallc_9
Case Name Status Exec Time Memory
bigrand_0 94 ms 24276 KB
bigrand_1 108 ms 21076 KB
bigrand_2 106 ms 21972 KB
bigrand_3 110 ms 22100 KB
bigrand_4 106 ms 19668 KB
bigrand_5 106 ms 20436 KB
bigrand_6 107 ms 23892 KB
bigrand_7 104 ms 24276 KB
bigrand_8 105 ms 24148 KB
bigrand_9 110 ms 22352 KB
example_0 77 ms 17876 KB
example_1 69 ms 19412 KB
example_2 86 ms 18516 KB
example_3 79 ms 21716 KB
perm2_0 107 ms 23252 KB
perm2_1 106 ms 22356 KB
perm2_2 112 ms 23508 KB
perm2_3 83 ms 20308 KB
perm2_4 105 ms 23380 KB
perm2_5 86 ms 16724 KB
perm_0 107 ms 22740 KB
perm_1 98 ms 22868 KB
perm_2 87 ms 19540 KB
perm_3 109 ms 22228 KB
perm_4 104 ms 26068 KB
perm_5 72 ms 18900 KB
rand_0 105 ms 19412 KB
rand_1 97 ms 21972 KB
rand_2 100 ms 20308 KB
rand_3 90 ms 17748 KB
rand_4 100 ms 22096 KB
rand_5 100 ms 19540 KB
rand_6 79 ms 23764 KB
rand_7 95 ms 21844 KB
rand_8 110 ms 22612 KB
rand_9 104 ms 27604 KB
smallc_0 73 ms 19412 KB
smallc_1 107 ms 22356 KB
smallc_2 104 ms 26196 KB
smallc_3 107 ms 24148 KB
smallc_4 92 ms 24276 KB
smallc_5 102 ms 21460 KB
smallc_6 103 ms 20180 KB
smallc_7 109 ms 22100 KB
smallc_8 103 ms 22100 KB
smallc_9 105 ms 23636 KB