Submission #3011190


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 = 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 2760 Byte
Status
Exec Time 375 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 182 ms 43368 KB
11.txt 135 ms 43752 KB
12.txt 106 ms 39528 KB
13.txt 102 ms 39528 KB
14.txt 87 ms 39528 KB
15.txt 89 ms 39528 KB
16.txt 292 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 237 ms 57576 KB
23.txt 110 ms 39784 KB
24.txt 97 ms 41448 KB
25.txt 134 ms 45928 KB
26.txt 107 ms 39528 KB
27.txt 90 ms 39528 KB
28.txt 305 ms 57576 KB
29.txt 141 ms 39912 KB
3.txt 19 ms 27264 KB
30.txt 96 ms 41448 KB
31.txt 256 ms 56552 KB
32.txt 110 ms 39528 KB
33.txt 89 ms 39528 KB
34.txt 203 ms 57576 KB
35.txt 65 ms 40040 KB
36.txt 125 ms 41448 KB
37.txt 153 ms 49000 KB
38.txt 106 ms 39528 KB
39.txt 89 ms 39528 KB
4.txt 297 ms 57576 KB
40.txt 211 ms 57576 KB
41.txt 122 ms 39912 KB
42.txt 117 ms 41448 KB
43.txt 165 ms 47848 KB
44.txt 107 ms 39528 KB
45.txt 88 ms 39528 KB
46.txt 48 ms 39528 KB
47.txt 68 ms 39528 KB
48.txt 38 ms 39528 KB
49.txt 83 ms 44648 KB
5.txt 258 ms 57576 KB
50.txt 229 ms 77288 KB
51.txt 36 ms 39528 KB
52.txt 205 ms 57704 KB
53.txt 116 ms 39912 KB
54.txt 86 ms 41448 KB
55.txt 156 ms 52328 KB
56.txt 103 ms 39528 KB
57.txt 87 ms 39784 KB
58.txt 222 ms 61672 KB
59.txt 225 ms 61672 KB
6.txt 136 ms 39784 KB
60.txt 201 ms 59624 KB
61.txt 210 ms 59496 KB
62.txt 367 ms 75496 KB
63.txt 375 ms 75496 KB
64.txt 185 ms 44008 KB
65.txt 159 ms 44136 KB
66.txt 127 ms 44264 KB
67.txt 310 ms 62568 KB
68.txt 195 ms 49516 KB
69.txt 196 ms 53864 KB
7.txt 107 ms 40040 KB
70.txt 249 ms 57064 KB
71.txt 282 ms 58728 KB
72.txt 307 ms 60520 KB
73.txt 333 ms 60008 KB
74.txt 304 ms 60648 KB
75.txt 292 ms 59496 KB
76.txt 299 ms 62952 KB
77.txt 296 ms 57448 KB
78.txt 333 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