QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#362815 | #8512. Harmonic Operations | ucup-team1055# | WA | 0ms | 3860kb | C++20 | 8.2kb | 2024-03-23 17:13:07 | 2024-03-23 17:13:07 |
Judging History
answer
#line 2 "/Users/noya2/Desktop/Noya2_library/template/template.hpp"
using namespace std;
#include<bits/stdc++.h>
#line 1 "/Users/noya2/Desktop/Noya2_library/template/inout_old.hpp"
namespace noya2 {
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p){
os << p.first << " " << p.second;
return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p){
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
int s = (int)v.size();
for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v){
for (auto &x : v) is >> x;
return is;
}
void in() {}
template <typename T, class... U>
void in(T &t, U &...u){
cin >> t;
in(u...);
}
void out() { cout << "\n"; }
template <typename T, class... U, char sep = ' '>
void out(const T &t, const U &...u){
cout << t;
if (sizeof...(u)) cout << sep;
out(u...);
}
template<typename T>
void out(const vector<vector<T>> &vv){
int s = (int)vv.size();
for (int i = 0; i < s; i++) out(vv[i]);
}
struct IoSetup {
IoSetup(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
cerr << fixed << setprecision(7);
}
} iosetup_noya2;
} // namespace noya2
#line 1 "/Users/noya2/Desktop/Noya2_library/template/const.hpp"
namespace noya2{
const int iinf = 1'000'000'007;
const long long linf = 2'000'000'000'000'000'000LL;
const long long mod998 = 998244353;
const long long mod107 = 1000000007;
const long double pi = 3.14159265358979323;
const vector<int> dx = {0,1,0,-1,1,1,-1,-1};
const vector<int> dy = {1,0,-1,0,1,-1,-1,1};
const string ALP = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string alp = "abcdefghijklmnopqrstuvwxyz";
const string NUM = "0123456789";
void yes(){ cout << "Yes\n"; }
void no(){ cout << "No\n"; }
void YES(){ cout << "YES\n"; }
void NO(){ cout << "NO\n"; }
void yn(bool t){ t ? yes() : no(); }
void YN(bool t){ t ? YES() : NO(); }
} // namespace noya2
#line 1 "/Users/noya2/Desktop/Noya2_library/template/utils.hpp"
namespace noya2{
unsigned long long inner_binary_gcd(unsigned long long a, unsigned long long b){
if (a == 0 || b == 0) return a + b;
int n = __builtin_ctzll(a); a >>= n;
int m = __builtin_ctzll(b); b >>= m;
while (a != b) {
int mm = __builtin_ctzll(a - b);
bool f = a > b;
unsigned long long c = f ? a : b;
b = f ? b : a;
a = (c - b) >> mm;
}
return a << min(n, m);
}
template<typename T> T gcd_fast(T a, T b){ return static_cast<T>(inner_binary_gcd(abs(a),abs(b))); }
long long sqrt_fast(long long n) {
if (n <= 0) return 0;
long long x = sqrt(n);
while ((x + 1) * (x + 1) <= n) x++;
while (x * x > n) x--;
return x;
}
template<typename T> T floor_div(const T n, const T d) {
assert(d != 0);
return n / d - static_cast<T>((n ^ d) < 0 && n % d != 0);
}
template<typename T> T ceil_div(const T n, const T d) {
assert(d != 0);
return n / d + static_cast<T>((n ^ d) >= 0 && n % d != 0);
}
template<typename T> void uniq(vector<T> &v){
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
}
template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T> inline bool range(T l, T x, T r){ return l <= x && x < r; }
} // namespace noya2
#line 8 "/Users/noya2/Desktop/Noya2_library/template/template.hpp"
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define repp(i,m,n) for (int i = (m); i < (int)(n); i++)
#define reb(i,n) for (int i = (int)(n-1); i >= 0; i--)
#define all(v) (v).begin(),(v).end()
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
namespace noya2{
/* ~ (. _________ . /) */
}
using namespace noya2;
#line 2 "c.cpp"
#line 2 "/Users/noya2/Desktop/Noya2_library/string/rolling_hash.hpp"
#line 4 "/Users/noya2/Desktop/Noya2_library/string/rolling_hash.hpp"
namespace noya2{
struct RollingHash {
using ull = unsigned long long;
RollingHash(const string &s = ""){ build(s);}
ull get(int l, int r){
assert(0 <= l && l <= r && r <= n);
return cal_mod(inner_hash[r] + POSITIVISER - mul_mod(inner_hash[l], pow_base[r-l]));
}
static ull get_hash(const string &s){
int len = s.size();
set_hash();
extend_pow_base(len);
ull res = 0;
for (int i = 0; i < len; i++) res = cal_mod(mul_mod(res,BASE) + s[i]);
return res;
}
size_t size() const { return n; }
template<class... Hash_Lengths> static ull concat(const Hash_Lengths&... hash_length){
return inner_concat(0ULL,hash_length...);
}
private:
static ull inner_concat(const ull& temp){
return temp;
}
template<class... Tail> static ull inner_concat(const ull& temp, const ull& hash, const int& len, const Tail&... tail){
return inner_concat(cal_mod(cal_mod(mul_mod(temp,pow_base[len]))+hash),tail...);
}
static constexpr ull MASK30 = (1ULL << 30) - 1;
static constexpr ull MASK31 = (1ULL << 31) - 1;
static constexpr ull MASK61 = (1ULL << 61) - 1;
static constexpr ull MOD = (1ULL << 61) - 1;
static constexpr ull POSITIVISER = MOD * 4;
static ull BASE;
static vector<ull> pow_base;
static ull mul_mod(ull a, ull b){
ull au = a >> 31, ad = a & MASK31;
ull bu = b >> 31, bd = b & MASK31;
ull mid = ad * bu + au * bd;
ull midu = mid >> 30, midd = mid & MASK30;
return (au * bu * 2 + midu + (midd << 31) + ad * bd);
}
static ull cal_mod(ull x){
ull xu = x >> 61;
ull xd = x & MASK61;
ull res = xu + xd;
if (res >= MOD) res -= MOD;
return res;
}
static void set_hash(){
if (BASE == 0) BASE = (1UL<<31) + (random_device()() & MASK31);
}
static void extend_pow_base(int len){
int nlen = pow_base.size();
if (nlen > len) return ;
pow_base.resize(len+1);
for (int i = nlen; i <= len; i++){
pow_base[i] = cal_mod(mul_mod(pow_base[i-1],BASE));
}
}
string str;
int n;
vector<ull> inner_hash;
void build(const string &s){
set_hash();
str = s;
n = s.size();
extend_pow_base(n);
inner_hash.resize(n+1);
inner_hash[0] = 0;
for (int i = 0; i < n; i++) inner_hash[i+1] = cal_mod(mul_mod(inner_hash[i],BASE) + s[i]);
}
};
using ull = unsigned long long;
ull RollingHash::BASE = 0;
vector<ull> RollingHash::pow_base = vector<ull>(1,1);
using roriha = RollingHash;
} // namespace noya2
#line 4 "c.cpp"
void solve(){
string s; in(s);
int n = s.size();
roriha hs(s);
roriha ihs([&]{
string t = s;
reverse(all(t));
return t;
}());
auto calc = [&](int inv, int l){
if (inv == 0){
return roriha::concat(hs.get(l,n),n-l,hs.get(0,l),l);
}
else {
return roriha::concat(ihs.get(l,n),n-l,ihs.get(0,l),l);
}
};
int inv = 0;
int l = 0;
map<ull,ll> mp;
mp[calc(inv,l)]++;
int q; in(q);
while (q--){
char t; in(t);
if (t == 'I'){
l = n-l;
if (l == n) l = 0;
inv ^= 1;
}
if (t == 'L'){
int x; in(x);
l = (l + x) % n;
}
if (t == 'R'){
int x; in(x);
l = (l - x + n) % n;
}
mp[calc(inv,l)]++;
}
ll ans = 0;
for (auto [h, c] : mp){
ans += c*(c-1)/2;
}
out(ans);
}
int main(){
int t = 1; //in(t);
while (t--) { solve(); }
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3532kb
input:
pda 2 R 2 L 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3784kb
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: 3552kb
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: 3784kb
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: 3540kb
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: 3860kb
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'