Submission #3011175


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 = 133333;

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 2691 Byte
Status
Exec Time 392 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 93 ms 43368 KB
11.txt 94 ms 43752 KB
12.txt 60 ms 39528 KB
13.txt 61 ms 39528 KB
14.txt 51 ms 39528 KB
15.txt 51 ms 39528 KB
16.txt 193 ms 57576 KB
17.txt 63 ms 39912 KB
18.txt 86 ms 41448 KB
19.txt 135 ms 49768 KB
2.txt 15 ms 26112 KB
20.txt 61 ms 39528 KB
21.txt 51 ms 39528 KB
22.txt 194 ms 57576 KB
23.txt 63 ms 39784 KB
24.txt 86 ms 41448 KB
25.txt 109 ms 45928 KB
26.txt 60 ms 39528 KB
27.txt 51 ms 39528 KB
28.txt 208 ms 57576 KB
29.txt 64 ms 39912 KB
3.txt 19 ms 27264 KB
30.txt 86 ms 41576 KB
31.txt 200 ms 56552 KB
32.txt 60 ms 39784 KB
33.txt 51 ms 39528 KB
34.txt 205 ms 57576 KB
35.txt 63 ms 40040 KB
36.txt 87 ms 41448 KB
37.txt 127 ms 49000 KB
38.txt 61 ms 39528 KB
39.txt 51 ms 39528 KB
4.txt 203 ms 57448 KB
40.txt 200 ms 57576 KB
41.txt 64 ms 39912 KB
42.txt 86 ms 41448 KB
43.txt 123 ms 47848 KB
44.txt 60 ms 39528 KB
45.txt 51 ms 39528 KB
46.txt 48 ms 39528 KB
47.txt 39 ms 39528 KB
48.txt 38 ms 39528 KB
49.txt 83 ms 44648 KB
5.txt 205 ms 57576 KB
50.txt 237 ms 77288 KB
51.txt 35 ms 39528 KB
52.txt 225 ms 57704 KB
53.txt 64 ms 39912 KB
54.txt 87 ms 41448 KB
55.txt 156 ms 52328 KB
56.txt 61 ms 39528 KB
57.txt 51 ms 39528 KB
58.txt 238 ms 61672 KB
59.txt 239 ms 61672 KB
6.txt 63 ms 39784 KB
60.txt 226 ms 59496 KB
61.txt 220 ms 59496 KB
62.txt 392 ms 75496 KB
63.txt 390 ms 75496 KB
64.txt 96 ms 44008 KB
65.txt 97 ms 44136 KB
66.txt 97 ms 44264 KB
67.txt 272 ms 62568 KB
68.txt 160 ms 49516 KB
69.txt 187 ms 53864 KB
7.txt 64 ms 39912 KB
70.txt 206 ms 57064 KB
71.txt 208 ms 58728 KB
72.txt 240 ms 60520 KB
73.txt 219 ms 60008 KB
74.txt 237 ms 60648 KB
75.txt 218 ms 59496 KB
76.txt 252 ms 63080 KB
77.txt 203 ms 57448 KB
78.txt 287 ms 63720 KB
8.txt 89 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