QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#362811 | #8512. Harmonic Operations | ucup-team133# | WA | 2ms | 4508kb | C++17 | 5.6kb | 2024-03-23 17:12:21 | 2024-03-23 17:12:22 |
Judging History
answer
// -fsanitize=undefined,
//#define _GLIBCXX_DEBUG
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <random>
#include <stdio.h>
#include <fstream>
#include <functional>
#include <cassert>
#include <unordered_map>
#include <bitset>
#include <chrono>
using namespace std;
#define rep(i,n) for (int i=0;i<n;i+=1)
#define rrep(i,n) for (int i=n-1;i>-1;i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << " )\n";
template<class T>
using vec = vector<T>;
template<class T>
using vvec = vec<vec<T>>;
template<class T>
using vvvec = vec<vvec<T>>;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<class T>
bool chmin(T &a, T b){
if (a>b){
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b){
if (a<b){
a = b;
return true;
}
return false;
}
template<class T>
T sum(vec<T> x){
T res=0;
for (auto e:x){
res += e;
}
return res;
}
template<class T>
void printv(vec<T> x){
for (auto e:x){
cout<<e<<" ";
}
cout<<endl;
}
template<class T,class U>
ostream& operator<<(ostream& os, const pair<T,U>& A){
os << "(" << A.first <<", " << A.second << ")";
return os;
}
template<class T>
ostream& operator<<(ostream& os, const set<T>& S){
os << "set{";
for (auto a:S){
os << a;
auto it = S.find(a);
it++;
if (it!=S.end()){
os << ", ";
}
}
os << "}";
return os;
}
template<class T>
ostream& operator<<(ostream& os, const tuple<T,T,T>& a){
auto [x,y,z] = a;
os << "(" << x << ", " << y << ", " << z << ")";
return os;
}
template<class T>
ostream& operator<<(ostream& os, const map<int,T>& A){
os << "map{";
for (auto e:A){
os << e.first;
os << ":";
os << e.second;
os << ", ";
}
os << "}";
return os;
}
template<class T>
ostream& operator<<(ostream& os, const vec<T>& A){
os << "[";
rep(i,A.size()){
os << A[i];
if (i!=A.size()-1){
os << ", ";
}
}
os << "]" ;
return os;
}
const int INF = 1e9;
using ull = unsigned long long;
const ull MASK30 = (1ull << 30) - 1;
const ull MASK31 = (1ull << 31) - 1;
const ull MOD = (1ull << 61) - 1;
const ull MASK61 = MOD;
//mod 2^61-1を計算する関数
ull CalcMod(ull x)
{
ull xu = x >> 61;
ull xd = x & MASK61;
ull res = xu + xd;
if (res >= MOD) res -= MOD;
return res;
}
//a*b mod 2^61-1を返す関数(最後にModを取る)
ull Mul(ull a, ull b)
{
ull au = a >> 31;
ull ad = a & MASK31;
ull bu = b >> 31;
ull bd = b & MASK31;
ull mid = ad * bu + au * bd;
ull midu = mid >> 30;
ull midd = mid & MASK30;
return CalcMod(au * bu * 2 + midu + (midd << 31) + ad * bd);
}
const int B = 400;
struct RandomNumberGenerator {
mt19937 mt;
RandomNumberGenerator() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}
ull operator()(ull a, ull b) { // [a, b)
uniform_int_distribution< ull > dist(a, b - 1);
return dist(mt);
}
int operator()(int b) { // [0, b)
return (*this)(0, b);
}
};
const int M = 2e5 + 10;
void solve(){
RandomNumberGenerator RRR;
ull base = RRR(2,(1ull<<61) -1);
vec<ull> b_pow(M,1);
for (int i=1;i<M;i++){
b_pow[i] = Mul(base,b_pow[i-1]);
}
string S;
cin>>S;
int N = S.size();
ull S_hash = 0,revS_hash;
rep(i,N){
int a = S[i] - 'a' + 1;
int b = S[N-1-i] - 'a' + 1;
S_hash = CalcMod(S_hash+Mul(b_pow[i],a));
revS_hash = CalcMod(Mul(base,revS_hash)+b);
}
int period = 0;
ull tmp_hash = S_hash;
for (int p=1;p<=N;p++){
int a = S[N-p] - 'a' + 1;
tmp_hash = Mul(CalcMod(tmp_hash+(MOD-Mul(b_pow[N-1],a))),base);
tmp_hash = CalcMod(tmp_hash+a);
if (tmp_hash == S_hash){
period = p;
break;
}
}
int diff = -1;
ull tmp_revhash = revS_hash;
for (int d=0;d<period;d++){
if (tmp_revhash == revS_hash){
diff = d;
break;
}
int a = S[N-1-d] = 'a' + 1;
tmp_revhash = Mul(CalcMod(tmp_revhash+(MOD-Mul(b_pow[N-1],a))),base);
tmp_revhash = CalcMod(tmp_revhash+a);
}
//debug(diff);
vector<pair<int,int>> ope;
int K;
cin>>K;
rep(i,K){
char c;
cin>>c;
if (c == 'I'){
ope.push_back({0,0});
continue;
}
int k;
cin>>k;
if (c == 'L'){
ope.push_back({1,(period-k) % period});
}
else{
ope.push_back({1,k % period});
}
}
vec<ll> even_flip_cnt(period,0),odd_flip_cnt(period,0);
int even_add = 0, odd_add = 0;
ll res = 0;
for (auto [t,x]:ope){
if (t == 1){
even_add += x;
even_add %= period;
even_flip_cnt[(x+period-even_add) % period]++;
odd_add += period - x;
odd_add %= period;
}
else{
swap(even_flip_cnt,odd_flip_cnt);
swap(even_add,odd_add);
odd_flip_cnt[(period-odd_add) % period]++;
}
res += even_flip_cnt[(period-even_add) % period];
if (diff!=-1){
res += odd_flip_cnt[(diff+period-odd_add) % period];
}
}
cout << res << "\n";
}
int main(){
int T;
T = 1;
while (T--){
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4480kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 2ms
memory: 4508kb
input:
aaa 4 R 1 I I R 1
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 4484kb
input:
caso 6 L 1 I I R 1 I I
output:
9
result:
wrong answer 1st numbers differ - expected: '4', found: '9'