Submission #3011198


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 = power(h0[-dx], mod0 - 2, mod0), mul1 = power(h1[-dx], mod1 - 2, mod1), mul2 = power(h2[-dx], mod2 - 2, mod2);
    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 2759 Byte
Status
Exec Time 369 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 181 ms 43368 KB
11.txt 134 ms 43752 KB
12.txt 106 ms 39528 KB
13.txt 102 ms 39528 KB
14.txt 87 ms 39528 KB
15.txt 88 ms 39528 KB
16.txt 286 ms 57576 KB
17.txt 87 ms 39912 KB
18.txt 153 ms 41448 KB
19.txt 206 ms 49768 KB
2.txt 15 ms 26112 KB
20.txt 108 ms 39528 KB
21.txt 88 ms 39528 KB
22.txt 223 ms 57704 KB
23.txt 109 ms 39784 KB
24.txt 97 ms 41448 KB
25.txt 134 ms 45928 KB
26.txt 106 ms 39528 KB
27.txt 89 ms 39528 KB
28.txt 303 ms 57576 KB
29.txt 140 ms 39912 KB
3.txt 19 ms 27264 KB
30.txt 95 ms 41448 KB
31.txt 253 ms 56552 KB
32.txt 110 ms 39528 KB
33.txt 89 ms 39528 KB
34.txt 201 ms 57576 KB
35.txt 65 ms 39912 KB
36.txt 125 ms 41448 KB
37.txt 152 ms 49000 KB
38.txt 106 ms 39528 KB
39.txt 89 ms 39528 KB
4.txt 294 ms 57576 KB
40.txt 197 ms 57576 KB
41.txt 121 ms 39912 KB
42.txt 117 ms 41448 KB
43.txt 160 ms 47848 KB
44.txt 106 ms 39528 KB
45.txt 87 ms 39528 KB
46.txt 47 ms 39528 KB
47.txt 67 ms 39528 KB
48.txt 37 ms 39528 KB
49.txt 85 ms 44648 KB
5.txt 260 ms 57576 KB
50.txt 248 ms 77288 KB
51.txt 35 ms 39528 KB
52.txt 200 ms 57704 KB
53.txt 115 ms 39912 KB
54.txt 86 ms 41448 KB
55.txt 156 ms 52328 KB
56.txt 103 ms 39528 KB
57.txt 88 ms 39528 KB
58.txt 220 ms 61672 KB
59.txt 216 ms 61672 KB
6.txt 136 ms 39784 KB
60.txt 201 ms 59496 KB
61.txt 199 ms 59496 KB
62.txt 369 ms 75496 KB
63.txt 366 ms 75496 KB
64.txt 184 ms 44008 KB
65.txt 152 ms 44136 KB
66.txt 126 ms 44264 KB
67.txt 312 ms 62568 KB
68.txt 192 ms 49516 KB
69.txt 192 ms 53864 KB
7.txt 107 ms 39912 KB
70.txt 233 ms 57064 KB
71.txt 261 ms 58728 KB
72.txt 279 ms 60520 KB
73.txt 302 ms 60008 KB
74.txt 302 ms 60648 KB
75.txt 279 ms 59496 KB
76.txt 295 ms 63080 KB
77.txt 281 ms 57448 KB
78.txt 327 ms 63720 KB
8.txt 174 ms 41448 KB
9.txt 92 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