QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#362811#8512. Harmonic Operationsucup-team133#WA 2ms4508kbC++175.6kb2024-03-23 17:12:212024-03-23 17:12:22

Judging History

你现在查看的是最新测评结果

  • [2024-03-23 17:12:22]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4508kb
  • [2024-03-23 17:12:21]
  • 提交

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'