QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363649 | #8512. Harmonic Operations | ucup-team1134# | WA | 1ms | 3876kb | C++23 | 5.0kb | 2024-03-24 01:29:56 | 2024-03-24 01:29:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod1=1030000001,mod2=1031000023,MAX=300005,INF=1<<30;
struct Rollinghash{
string S;
int n;
int base1;
int base2;
vector<ll> h1,h2,ru1,ru2;
void make(string &T,int ba1,int ba2){
S=T;
n=S.size();
h1.assign(n+1,0);
h2.assign(n+1,0);
ru1.assign(n+1,0);
ru2.assign(n+1,0);
base1=ba1;
base2=ba2;
ru1[0]=1;
ru2[0]=1;
for(int i=1;i<=n;i++){
h1[i]=h1[i-1]*base1+ll(S[i-1]-'a'+1);
h1[i]%=mod1;
h2[i]=h2[i-1]*base2+ll(S[i-1]-'a'+1);
h2[i]%=mod2;
ru1[i]=ru1[i-1]*base1%mod1;
ru2[i]=ru2[i-1]*base2%mod2;
}
}
pair<ll,ll> ha(int l,int r){
pair<ll,ll> res;
res.fi=(h1[r]-h1[l]*ru1[r-l]%mod1+mod1)%mod1;
res.se=(h2[r]-h2[l]*ru2[r-l]%mod2+mod2)%mod2;
return res;
}//開区間
};
int main(){
std::ifstream in("text.txt");
std::cin.rdbuf(in.rdbuf());
cin.tie(0);
ios::sync_with_stdio(false);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
string S;cin>>S;
ll ha1=rng()%mod1,ha2=rng()%mod2;
ll N=si(S);
ll Q;cin>>Q;
vector<pair<ll,ll>> T(Q+1);
for(int i=0;i<Q;i++){
char c;cin>>c;
T[i+1]=T[i];
if(c=='I'){
T[i+1].fi^=1;
}else if(c=='L'){
int x;cin>>x;
if(T[i].fi==0){
T[i+1].se=(T[i+1].se+x)%N;
}else{
T[i+1].se=(N+T[i+1].se-x)%N;
}
}else{
int x;cin>>x;x=N-x;
if(T[i].fi==0){
T[i+1].se=(T[i+1].se+x)%N;
}else{
T[i+1].se=(N+T[i+1].se-x)%N;
}
}
//cout<<T[i+1].fi<<" "<<T[i+1].se<<endl;
}
string A=S+S+S,B=A;
reverse(all(B));
Rollinghash ro1,ro2;
ro1.make(A,ha1,ha2);
ro2.make(B,ha1,ha2);
//cout<<A<<endl;
//cout<<B<<endl;
//for(int i=0;i<N;i++) cout<<ro1.ha(i,i+N).fi<<" "<<ro2.ha(i,i+N).fi<<endl;
ll ans=0;
vector<ll> X,Y;
for(auto [a,b]:T){
if(a==0) X.push_back(b);
else Y.push_back(b);
}
{
vector<int> OK;
for(int i=0;i<N;i++){
if(ro1.ha(0,N)==ro1.ha(i,i+N)) OK.push_back(i);
}
ll g;
if(si(OK)==1) g=N;
else g=OK[1]-OK[0];
vector<ll> CN(g);
for(ll x:X){
ans+=CN[x%g];
CN[x%g]++;
//cout<<x<<" ";
}
}
{
vector<int> OK;
for(int i=0;i<N;i++){
if(ro2.ha(0,N)==ro2.ha(i,i+N)) OK.push_back(i);
}
ll g;
if(si(OK)==1) g=N;
else g=OK[1]-OK[0];
vector<ll> CN(g);
for(ll x:Y){
ans+=CN[x%g];
CN[x%g]++;
//cout<<x<<" ";
}
}
{
vector<int> OK;
for(int i=0;i<N;i++){
if(ro1.ha(0,N)==ro2.ha(N-i,N+N-i)) OK.push_back(i);
//cout<<ro1.ha(0,N).fi<<" "<<ro1.ha(0,N).se<<endl;
//cout<<ro2.ha(N-i,N+N-i).fi<<" "<<ro2.ha(N-i,N+N-i).se<<endl;
}
//cout<<si(OK)<<endl;
if(si(OK)){
ll g,dif;
if(si(OK)==1){
g=N;
dif=OK[0];
}else{
g=(OK[1]-OK[0]);
dif=OK[0]%g;
}
vector<ll> CN(g);
for(auto [a,b]:T){
if(a==0){
CN[(g-b%g+dif)%g]++;
}else{
ans+=CN[b%g];
}
}
}
}
{
vector<int> OK;
for(int i=0;i<N;i++){
if(ro1.ha(0,N)==ro2.ha(N+i,N+N+i)) OK.push_back(i);
//cout<<ro1.ha(0,N).fi<<" "<<ro1.ha(0,N).se<<endl;
//cout<<ro2.ha(N-i,N+N-i).fi<<" "<<ro2.ha(N-i,N+N-i).se<<endl;
}
//cout<<si(OK)<<endl;
if(si(OK)){
ll g,dif;
if(si(OK)==1){
g=N;
dif=OK[0];
}else{
g=(OK[1]-OK[0]);
dif=OK[0]%g;
}
vector<ll> CN(g);
for(auto [a,b]:T){
if(a==1){
CN[(g-b%g+dif)%g]++;
}else{
ans+=CN[b%g];
}
}
}
}
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3664kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
aaa 4 R 1 I I R 1
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3596kb
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: 0ms
memory: 3876kb
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: 0ms
memory: 3588kb
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: 3588kb
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'