Submission #3606392
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define maxn 250020 #define rep(i,l,r) for(register int i = l ; i <= r ; i++) #define repd(i,r,l) for(register int i = r ; i >= l ; i--) #define rvc(i,S) for(register int i = 0 ; i < (int)S.size() ; i++) #define rvcd(i,S) for(register int i = ((int)S.size()) - 1 ; i >= 0 ; i--) #define fore(i,x)for (register int i = head[x] ; i ; i = e[i].next) #define pb push_back #define prev prev_ #define stack stack_ #define mp make_pair #define fi first #define se second #define inf 0x3f3f3f3f typedef long long ll; typedef pair<int,int> pr; const ll mod = 1e9 + 7; const ll p[7] = {19,37,59,97,107,109,91}; ll inv[7]; inline ll add(ll x,ll y){ return (x + y + mod) % mod; } struct node{ ll a[7]; node() { memset(a,0,sizeof(a)); } bool operator < (node x)const{ rep(i,0,6) if ( a[i] != x.a[i] ) return a[i] < x.a[i]; return 0; } node operator + (node x){ node y; rep(i,0,6) y.a[i] = add(a[i],x.a[i]); return y; } node operator - (node x){ node y; rep(i,0,6) y.a[i] = add(a[i],-x.a[i]); return y; } node operator * (const ll p[]){ node y; rep(i,0,6) y.a[i] = a[i] * p[i] % mod; return y; } node operator * (node x){ node y; rep(i,0,6) y.a[i] = a[i] * x.a[i] % mod; return y; } void print(){ rep(i,0,6) cout<<a[i]<<" "; cout<<endl; } }hash_[maxn],pos[maxn]; map <node,int> num; char s[maxn]; int n; ll ans; inline ll power(ll x,ll y){ ll res = 1; while ( y ){ if ( y & 1 ) res = res * x % mod; x = x * x % mod; y >>= 1; } return res; } void init(){ rep(i,0,6) inv[i] = power(p[i],mod - 2); } void solve(){ rep(i,0,6) pos[0].a[i] = 1; rep(i,1,n){ hash_[i] = hash_[i - 1] , pos[i] = pos[i - 1]; if ( s[i] == '+' ) hash_[i] = hash_[i] + pos[i]; else if ( s[i] == '-' ) hash_[i] = hash_[i] - pos[i]; else if ( s[i] == '>' ) pos[i] = pos[i] * p; else if ( s[i] == '<' ) pos[i] = pos[i] * inv; } repd(i,n,1){ num[hash_[i]]++; node cur = hash_[n] * pos[i - 1] + hash_[i - 1]; ans += num[cur]; } cout<<ans<<endl; } int main(){ scanf("%d",&n); scanf("%s",s + 1); init(); solve(); }
Submission Info
Submission Time | |
---|---|
Task | F - Eating Symbols Hard |
User | zhangqingqi |
Language | C++14 (GCC 5.4.1) |
Score | 1200 |
Code Size | 2192 Byte |
Status | AC |
Exec Time | 466 ms |
Memory | 82560 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:90:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d",&n); ^ ./Main.cpp:91:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%s",s + 1); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1200 / 1200 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt |
All | 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 | AC | 12 ms | 27648 KB |
10.txt | AC | 106 ms | 35200 KB |
11.txt | AC | 109 ms | 35712 KB |
12.txt | AC | 69 ms | 29440 KB |
13.txt | AC | 70 ms | 29696 KB |
14.txt | AC | 57 ms | 28032 KB |
15.txt | AC | 57 ms | 28032 KB |
16.txt | AC | 257 ms | 55040 KB |
17.txt | AC | 75 ms | 30208 KB |
18.txt | AC | 101 ms | 32256 KB |
19.txt | AC | 157 ms | 44032 KB |
2.txt | AC | 12 ms | 27648 KB |
20.txt | AC | 69 ms | 29568 KB |
21.txt | AC | 56 ms | 28032 KB |
22.txt | AC | 254 ms | 54912 KB |
23.txt | AC | 73 ms | 30080 KB |
24.txt | AC | 102 ms | 32384 KB |
25.txt | AC | 123 ms | 38656 KB |
26.txt | AC | 69 ms | 29568 KB |
27.txt | AC | 57 ms | 28032 KB |
28.txt | AC | 244 ms | 55040 KB |
29.txt | AC | 75 ms | 30336 KB |
3.txt | AC | 16 ms | 28672 KB |
30.txt | AC | 104 ms | 32384 KB |
31.txt | AC | 239 ms | 53504 KB |
32.txt | AC | 70 ms | 29568 KB |
33.txt | AC | 57 ms | 28032 KB |
34.txt | AC | 252 ms | 55040 KB |
35.txt | AC | 75 ms | 30336 KB |
36.txt | AC | 102 ms | 32384 KB |
37.txt | AC | 158 ms | 42880 KB |
38.txt | AC | 69 ms | 29568 KB |
39.txt | AC | 58 ms | 28032 KB |
4.txt | AC | 262 ms | 54912 KB |
40.txt | AC | 256 ms | 54912 KB |
41.txt | AC | 74 ms | 30208 KB |
42.txt | AC | 102 ms | 32384 KB |
43.txt | AC | 143 ms | 41216 KB |
44.txt | AC | 70 ms | 29440 KB |
45.txt | AC | 57 ms | 28032 KB |
46.txt | AC | 54 ms | 27904 KB |
47.txt | AC | 39 ms | 27776 KB |
48.txt | AC | 39 ms | 27776 KB |
49.txt | AC | 112 ms | 36992 KB |
5.txt | AC | 266 ms | 55040 KB |
50.txt | AC | 329 ms | 82560 KB |
51.txt | AC | 38 ms | 27776 KB |
52.txt | AC | 276 ms | 55040 KB |
53.txt | AC | 75 ms | 30336 KB |
54.txt | AC | 105 ms | 32384 KB |
55.txt | AC | 195 ms | 47616 KB |
56.txt | AC | 69 ms | 29568 KB |
57.txt | AC | 57 ms | 28032 KB |
58.txt | AC | 296 ms | 60672 KB |
59.txt | AC | 300 ms | 60672 KB |
6.txt | AC | 74 ms | 30080 KB |
60.txt | AC | 277 ms | 57600 KB |
61.txt | AC | 283 ms | 57600 KB |
62.txt | AC | 463 ms | 80000 KB |
63.txt | AC | 466 ms | 80000 KB |
64.txt | AC | 106 ms | 35968 KB |
65.txt | AC | 106 ms | 36096 KB |
66.txt | AC | 107 ms | 36352 KB |
67.txt | AC | 312 ms | 64512 KB |
68.txt | AC | 181 ms | 51840 KB |
69.txt | AC | 212 ms | 54400 KB |
7.txt | AC | 74 ms | 30336 KB |
70.txt | AC | 242 ms | 58368 KB |
71.txt | AC | 255 ms | 60032 KB |
72.txt | AC | 285 ms | 62208 KB |
73.txt | AC | 256 ms | 58368 KB |
74.txt | AC | 274 ms | 59264 KB |
75.txt | AC | 280 ms | 57728 KB |
76.txt | AC | 304 ms | 62592 KB |
77.txt | AC | 245 ms | 54784 KB |
78.txt | AC | 314 ms | 63616 KB |
8.txt | AC | 104 ms | 32384 KB |
9.txt | AC | 103 ms | 32384 KB |
a.txt | AC | 12 ms | 27648 KB |
b.txt | AC | 12 ms | 27648 KB |
sample1.txt | AC | 12 ms | 27648 KB |
sample2.txt | AC | 12 ms | 27648 KB |
sample3.txt | AC | 12 ms | 27648 KB |