Submission #2730070


Source Code Expand

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

public class Main {
    FastScanner in;
    PrintWriter out;

    void solve() {
        Random rnd = new Random(123);
        final long p = (long) 1e9 + 7;
        BigInteger MODULO = BigInteger.valueOf(2).pow(64);
        final long pInv = BigInteger.valueOf(p).modInverse(MODULO).longValue();
        final int MAX = 500010;
        long[] vals = new long[MAX];
        vals[MAX / 2] = 1;
        for (int i = MAX / 2 + 1; i < MAX; i++) {
            vals[i]= vals[i - 1] * p;
        }
        for (int i = MAX / 2 - 1; i >= 0; i--) {
            vals[i] = vals[i + 1] * pInv;
        }
        in.nextInt();
        String s = in.next();
        long[] hashes = new long[s.length() + 1];
        int curPos = MAX / 2;
        int[] myPos = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            myPos[i] = curPos - MAX / 2;
            hashes[i + 1] = hashes[i];
            if (c == '<') {
                curPos--;
            } else if (c == '>') {
                curPos++;
            } else if (c == '-') {
                hashes[i + 1] -= vals[curPos];
            } else {
                hashes[i + 1] += vals[curPos];
            }
        }
//        System.err.println(Arrays.toString(hashes));
        long expectedHash = hashes[hashes.length - 1];
        long mul = 1, add = 0;
        int realPower = 0;
        HashMap<Long, Integer> count = new HashMap<>();
        long result = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            long nothingHash = -add * vals[MAX / 2 - realPower];
            long check = nothingHash * mul + add;
            if (check != 0) {
                throw new AssertionError();
            }
            Integer now = count.get(nothingHash);
            count.put(nothingHash, now == null ? 1 : (now + 1));
            char c = s.charAt(i);
            if (c == '<') {
                mul *= pInv;
                realPower--;
                add *= pInv;
            } else if (c == '>') {
                mul *= p;
                realPower++;
                add *= p;
            } else if (c == '-') {
                add--;
            } else {
                add++;
            }
            long need = expectedHash;
//            need *= vals[MAX / 2 - myPos[i]];
            long inMap = (need - add) * vals[MAX / 2 - realPower];
            Integer cou = count.get(inMap);
            if (cou != null) {
                result += cou;
//                System.err.println(i + "-> " + cou);
            }
        }
        out.println(result);
    }

    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 F - Eating Symbols Hard
User qwerty787788
Language Java8 (OpenJDK 1.8.0)
Score 1200
Code Size 4907 Byte
Status
Exec Time 374 ms
Memory 59464 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 1200 / 1200 sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 4.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 5.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 6.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 7.txt, 70.txt, 71.txt, 72.txt, 73.txt, 74.txt, 75.txt, 76.txt, 77.txt, 78.txt, 8.txt, 9.txt, a.txt, b.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt 95 ms 23892 KB
10.txt 322 ms 44900 KB
11.txt 245 ms 44028 KB
12.txt 222 ms 45468 KB
13.txt 286 ms 47092 KB
14.txt 213 ms 41040 KB
15.txt 240 ms 40080 KB
16.txt 224 ms 44128 KB
17.txt 223 ms 43396 KB
18.txt 215 ms 47768 KB
19.txt 198 ms 42212 KB
2.txt 85 ms 23124 KB
20.txt 217 ms 43300 KB
21.txt 184 ms 42520 KB
22.txt 220 ms 42804 KB
23.txt 216 ms 44060 KB
24.txt 198 ms 43440 KB
25.txt 228 ms 43688 KB
26.txt 248 ms 46360 KB
27.txt 279 ms 42996 KB
28.txt 208 ms 46040 KB
29.txt 229 ms 44296 KB
3.txt 116 ms 24020 KB
30.txt 219 ms 46740 KB
31.txt 243 ms 45260 KB
32.txt 186 ms 44816 KB
33.txt 176 ms 39924 KB
34.txt 225 ms 43192 KB
35.txt 184 ms 44708 KB
36.txt 229 ms 42648 KB
37.txt 193 ms 48528 KB
38.txt 178 ms 44160 KB
39.txt 211 ms 42996 KB
4.txt 205 ms 45916 KB
40.txt 230 ms 44604 KB
41.txt 183 ms 44292 KB
42.txt 216 ms 44204 KB
43.txt 197 ms 44480 KB
44.txt 187 ms 42448 KB
45.txt 183 ms 39568 KB
46.txt 217 ms 38872 KB
47.txt 181 ms 36112 KB
48.txt 153 ms 35700 KB
49.txt 207 ms 46248 KB
5.txt 193 ms 43564 KB
50.txt 217 ms 56412 KB
51.txt 149 ms 32972 KB
52.txt 267 ms 43668 KB
53.txt 210 ms 44380 KB
54.txt 215 ms 42520 KB
55.txt 196 ms 42860 KB
56.txt 184 ms 46144 KB
57.txt 187 ms 40396 KB
58.txt 323 ms 45108 KB
59.txt 333 ms 48632 KB
6.txt 212 ms 44136 KB
60.txt 203 ms 47052 KB
61.txt 176 ms 45756 KB
62.txt 233 ms 59464 KB
63.txt 255 ms 56900 KB
64.txt 191 ms 41456 KB
65.txt 300 ms 45496 KB
66.txt 199 ms 46120 KB
67.txt 222 ms 44672 KB
68.txt 183 ms 44656 KB
69.txt 198 ms 44968 KB
7.txt 202 ms 45920 KB
70.txt 273 ms 49468 KB
71.txt 215 ms 45976 KB
72.txt 215 ms 44220 KB
73.txt 356 ms 54208 KB
74.txt 298 ms 53784 KB
75.txt 374 ms 58732 KB
76.txt 358 ms 55036 KB
77.txt 229 ms 51948 KB
78.txt 258 ms 56052 KB
8.txt 247 ms 46056 KB
9.txt 216 ms 48024 KB
a.txt 80 ms 25172 KB
b.txt 82 ms 23636 KB
sample1.txt 81 ms 23252 KB
sample2.txt 80 ms 26196 KB
sample3.txt 82 ms 27348 KB