Submission #3011168


Source Code Expand

Copy
#include<bits/stdc++.h>

using namespace std;

using int64 = long long;

const int mod0 = 1e9 + 7;
const int mod1 = 1e9 + 9;
const int mod2 = 1e9 + 21;
const int base = 10007;

int64_t power(int64_t x, int64_t n, int64_t mod) {
  int64_t ret = 1;
  while(n > 0) {
    if(n & 1) (ret *= x) %= mod;
    (x *= x) %= mod;
    n >>= 1;
  }
  return ret;
}


int64 h0[550001], g0[550001];
int64 h1[550001], g1[550001];
int64 h2[550001], g2[550001];


int main() {

  h0[0] = h1[0] = h2[0] = 1;
  for(int i = 1; i < 550001; i++) {
    h0[i] = h0[i - 1] * base % mod0;
    h1[i] = h1[i - 1] * base % mod1;
    h2[i] = h2[i - 1] * base % mod2;
  }
  g0[550000] = power(h0[550000], mod0 - 2, mod0);
  g1[550000] = power(h1[550000], mod1 - 2, mod1);
  g2[550000] = power(h2[550000], mod2 - 2, mod2);
  for(int i = 549999; i >= 0; i--) {
    g0[i] = g0[i + 1] * (i + 1) % mod0;
    g1[i] = g1[i + 1] * (i + 1) % mod1;
    g2[i] = g2[i + 1] * (i + 1) % mod2;
  }

  int N;
  string S;

  cin >> N;
  cin >> S;

  vector< int64 > latte0, malta0;
  vector< int64 > latte1, malta1;
  vector< int64 > latte2, malta2;
  int64 beet = 0, pos = 250001;
  latte0.push_back(pos), malta0.push_back(beet);
  latte1.push_back(pos), malta1.push_back(beet);
  latte2.push_back(pos), malta2.push_back(beet);
  for(int i = 0; i < N; i++) {
    char c = S[i];
    if(c == '+') (beet += h0[pos]) %= mod0;
    else if(c == '-') (beet += mod0 - h0[pos]) %= mod0;
    else if(c == '<') --pos;
    else ++pos;
    latte0.push_back(pos), malta0.push_back(beet);
  }
  beet = 0, pos = 250001;
  for(int i = 0; i < N; i++) {
    char c = S[i];
    if(c == '+') (beet += h1[pos]) %= mod1;
    else if(c == '-') (beet += mod1 - h1[pos]) %= mod1;
    else if(c == '<') --pos;
    else ++pos;
    latte1.push_back(pos), malta1.push_back(beet);
  }
  beet = 0, pos = 250001;

  for(int i = 0; i < N; i++) {
    char c = S[i];
    if(c == '+') (beet += h2[pos]) %= mod2;
    else if(c == '-') (beet += mod2 - h2[pos]) %= mod2;
    else if(c == '<') --pos;
    else ++pos;
    latte2.push_back(pos), malta2.push_back(beet);
  }


  map< tuple< int64, int64, int64 >, int > mp;
  int64 ret = 0;
  for(int i = N; i >= 0; i--) {
    int64 dx = latte0[i] - latte0[0];
    int64 mul0, mul1, mul2;
    if(dx >= 0) mul0 = h0[dx], mul1 = h1[dx], mul2 = h1[dx];
    else mul0 = g0[-dx], mul1 = g1[-dx], mul2 = g2[-dx];
    ret += mp[make_tuple((malta0[i] + malta0[N] * mul0) % mod0, (malta1[i] + malta1[N] * mul1) % mod1, (malta2[i] + malta2[N] * mul2) % mod2)];
    ++mp[make_tuple(malta0[i], malta1[i], malta2[i])];
  }
  cout << ret << endl;
}

Submission Info

Submission Time
Task F - Eating Symbols Hard
User ei13333
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2690 Byte
Status
Exec Time 368 ms
Memory 77288 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 0 / 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 14 ms 25984 KB
10.txt 95 ms 43368 KB
11.txt 95 ms 43752 KB
12.txt 61 ms 39528 KB
13.txt 62 ms 39528 KB
14.txt 51 ms 39656 KB
15.txt 52 ms 39528 KB
16.txt 199 ms 57576 KB
17.txt 64 ms 39912 KB
18.txt 87 ms 41448 KB
19.txt 137 ms 49768 KB
2.txt 15 ms 26112 KB
20.txt 61 ms 39528 KB
21.txt 51 ms 39528 KB
22.txt 193 ms 57576 KB
23.txt 63 ms 39784 KB
24.txt 87 ms 41448 KB
25.txt 110 ms 45928 KB
26.txt 61 ms 39528 KB
27.txt 52 ms 39528 KB
28.txt 193 ms 57576 KB
29.txt 64 ms 39912 KB
3.txt 18 ms 27264 KB
30.txt 87 ms 41448 KB
31.txt 189 ms 56552 KB
32.txt 62 ms 39528 KB
33.txt 51 ms 39528 KB
34.txt 193 ms 57576 KB
35.txt 64 ms 39912 KB
36.txt 87 ms 41448 KB
37.txt 129 ms 49000 KB
38.txt 61 ms 39528 KB
39.txt 52 ms 39528 KB
4.txt 194 ms 57448 KB
40.txt 196 ms 57576 KB
41.txt 63 ms 39784 KB
42.txt 87 ms 41448 KB
43.txt 121 ms 47848 KB
44.txt 61 ms 39528 KB
45.txt 52 ms 39528 KB
46.txt 49 ms 39528 KB
47.txt 39 ms 39528 KB
48.txt 38 ms 39528 KB
49.txt 86 ms 44648 KB
5.txt 196 ms 57576 KB
50.txt 259 ms 77288 KB
51.txt 37 ms 39528 KB
52.txt 195 ms 57704 KB
53.txt 64 ms 39912 KB
54.txt 87 ms 41448 KB
55.txt 151 ms 52328 KB
56.txt 61 ms 39528 KB
57.txt 52 ms 39528 KB
58.txt 221 ms 61672 KB
59.txt 221 ms 61672 KB
6.txt 63 ms 39784 KB
60.txt 207 ms 59496 KB
61.txt 208 ms 59496 KB
62.txt 368 ms 75496 KB
63.txt 365 ms 75496 KB
64.txt 97 ms 44008 KB
65.txt 98 ms 44136 KB
66.txt 98 ms 44264 KB
67.txt 236 ms 62568 KB
68.txt 141 ms 49516 KB
69.txt 165 ms 53864 KB
7.txt 64 ms 40040 KB
70.txt 187 ms 57064 KB
71.txt 229 ms 58728 KB
72.txt 229 ms 60520 KB
73.txt 220 ms 60008 KB
74.txt 210 ms 60648 KB
75.txt 202 ms 59496 KB
76.txt 232 ms 62952 KB
77.txt 189 ms 57448 KB
78.txt 247 ms 63720 KB
8.txt 87 ms 41448 KB
9.txt 87 ms 41448 KB
a.txt 14 ms 25984 KB
b.txt 14 ms 25984 KB
sample1.txt 14 ms 25984 KB
sample2.txt 14 ms 25984 KB
sample3.txt 14 ms 25984 KB