QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#416699 | #8512. Harmonic Operations | kevinshan | WA | 3ms | 6876kb | C++14 | 2.6kb | 2024-05-22 03:31:16 | 2024-05-22 03:31:16 |
Judging History
answer
//#pragma GCC optimize("O3")
// 1200
#include <bits/stdc++.h>
#include <random>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rsz resize
#define bk back()
#define pb push_back
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define For(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define Rof(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
const int MOD = 1e9+7;
const ld PI = acos((ld)-1);
mt19937 rng; // or mt19937_64
template<class T> bool ckmin(T& a, const T& b) {
return b < a ? a = b, 1 : 0; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
cerr << h; if (sizeof...(t)) cerr << ", ";
DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif
#define vl vector<ll>
const int MX = 4e5+5;
ll p=97;
ll pows[MX];
vl hashstr(string S) {
vl hsh(sz(S)+1);
For(i,sz(S)) {
hsh[i+1] = (hsh[i]+(S[i]-'a'+1)*pows[i])%MOD;
}
return hsh;
}
void solve() {
string S;cin>>S;
int n = sz(S);
string S2 = S+S;
pows[0] = 1;
FOR(i,1,MX) pows[i] = pows[i-1]*p%MOD;
vector<vl> hsh(2);
hsh[0] = hashstr(S2);
reverse(all(S2));
hsh[1] = hashstr(S2);
reverse(all(S2));
map<ll, vpi> M;
For(k,2) For(i,sz(S)) {
ll tmp = hsh[k][n+i+1] - hsh[k][i];
tmp = ((tmp%MOD)+MOD)%MOD;
tmp = (tmp*pows[n-i])%MOD;
M[tmp].pb({k,i});
}
vector<vl> gr(2, vl(n+1));
int cnt = 1;
trav(x,M) {
dbg(x.f, sz(x.s));
trav(y,x.s) {
dbg(cnt,y.f,y.s);
gr[y.f][y.s] = cnt;
}
cnt++;
}
int K; cin>>K;
vpi pre(K+1);
ll ans = 0;
vi grCnt(cnt+5);
grCnt[gr[0][0]]++;
For(i,K) {
char c;cin>>c;
if(c=='I') {
pre[i+1] = {1^pre[i].f,-pre[i].s%n+n};
} else if(c=='R') {
int x;cin>>x;
pre[i+1] = {pre[i].f,(pre[i].s+x)%n};
} else {
int x;cin>>x;
pre[i+1] = {pre[i].f,(pre[i].s-x)%n};
}
int grId = gr[pre[i+1].f][(pre[i+1].s%n+n)%n];
dbg(i,grId);
ans += grCnt[grId];
grCnt[grId]++;
}
cout << ans << endl;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
solve();
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6608kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 3ms
memory: 6584kb
input:
aaa 4 R 1 I I R 1
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 0ms
memory: 6800kb
input:
caso 6 L 1 I I R 1 I I
output:
4
result:
ok 1 number(s): "4"
Test #4:
score: 0
Accepted
time: 3ms
memory: 6876kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq 100 L 12 I R 47 L 54 I I R 80 L 86 L 19 R 5 L 53 L 40 R 20 L 11 R 40 I I R 66 R 6 L 76 L 93 R 39 I I L 24 R 59 R 99 L 52 I I R 77 L 11 R 60 L 16 I L 40 I R 35 L 64 R 11 L 34 I R 35 I L 87 I I L 42 L ...
output:
5050
result:
ok 1 number(s): "5050"
Test #5:
score: 0
Accepted
time: 3ms
memory: 6588kb
input:
wewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewewe 100 R 83 R 34 I I R 87 R 74 L 98 I L 77 L 8 R 23 L 94 I I L 79 L 87 L 47 L 85 L 49 L 7 I I R 97 R 15 I R 66 L 8 R 62 R 68 I I R 32 R 24 R 36 L 60 R 75 R 77 I L 42 I L 61 I I R 78 R 51 L 98 I L 77 I I...
output:
2556
result:
ok 1 number(s): "2556"
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 6604kb
input:
rtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtrtr 100 R 27 R 68 I L 29 L 51 L 19 L 12 L 10 L 52 L 38 L 17 R 30 L 29 L 51 L 17 R 29 I R 96 R 50 R 56 I I I L 73 L 15 I R 1 R 81 L 94 R 27 R 52 R 57 R 44 I I L 53 I R 87 L 39 L 25 I I R 25 I I I L 88 L ...
output:
58
result:
wrong answer 1st numbers differ - expected: '116', found: '58'