#include <bits/stdc++.h>
#define se second
#define fs first
#define mp make_pair
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 1e6 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e9;
const int BASE = 1337;
int n, Q;
ll pw[N], hs[30][N];
void initHS () {
pw[0] = 1;
rep (i, 1, n * 2) pw[i] = pw[i - 1] * BASE;
rep (i, 0, 29) hs[i][0] = 1;
vector<char> c = {'J', 'O', 'I'};
rep (i, 1, n)
iter (id, c)
hs[id - 'A'][i] = (hs[id - 'A'][i - 1] * BASE % Mod + id - 'A') % Mod;
}
ll getHS (string S) {
ll res = 0;
rep (i, 1, n) res = (res * BASE % Mod + S[i - 1] - 'A') % Mod;
return res;
}
void solution () {
cin >> n;
string A, B, C;
vector<char> c = {'J', 'O', 'I'};
rep (i, 1, n) A += c[Rand(0, 2)];
rep (i, 1, n) B += c[Rand(0, 2)];
rep (i, 1, n) C += c[Rand(0, 2)];
set<string> S = {A, B, C};
auto Merge = [] (string A, string B) {
static string res;
res.resize(SZ(A));
rep (i, 0, SZ(A) - 1)
if (A[i] == B[i]) res[i] = A[i];
else {
static set<char> c;
c = {'J', 'O', 'I'};
c.erase(A[i]);
c.erase(B[i]);
res[i] = *c.begin();
}
return res;
};
int prevsz = SZ(S);
while (1) {
static set<string> newStr;
newStr.clear();
iter (&id1, S)
iter( &id2, S) newStr.insert(Merge(id1, id2));
iter (&id, newStr) S.insert(id);
if (SZ(S) == prevsz) break;
else prevsz = SZ(S);
}
cout << SZ(S) <<"\n";
return;
set<ll> vecHS;
initHS();
iter (&id, S) vecHS.insert(getHS(id));
cin >> Q;
string T; cin >> T;
if (vecHS.find(getHS(T)) != vecHS.end()) cout <<"Yes\n";
else cout <<"No\n";
rep (i, 1, Q) {
int L, R;
char C;
cin >> L >> R >> C;
rep (i, L - 1, R - 1) T[i] = C;
if (vecHS.find(getHS(T)) != vecHS.end()) cout <<"Yes\n";
else cout <<"No\n";
}
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
// file("c");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll num_Test = 1;
// cin >> num_Test;
while(num_Test--)
solution();
}
/*
18 3
2 5
6 21
13 19
9 17
14 17
19 20
2 16
2 10
9 14
19 20
14 16
1 3
17 19
14 21
18 19
4 7
5 12
1 13
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
