#include <bits/stdc++.h>
#define lli long long int
using namespace std;
vector<lli> pow3sum;
lli mod = 1000000009;
lli toInt(char c) {
switch (c) {
case 'J':
return 0;
case 'O':
return 1;
case 'I':
return 2;
default:
return -1;
}
}
vector<lli> toVec(string s) {
vector<lli> v;
for (char c: s) v.push_back(toInt(c));
return v;
}
lli toHash(vector<lli> v) {
lli hash = 0;
for (int i = 0; i < v.size(); ++i) {
hash += (pow3sum[i + 1] - pow3sum[i] + mod) * v[i];
hash %= mod;
}
return hash;
}
vector<bool> check(lli mod) {
}
int main() {
vector<lli> seq[9];
int n;
cin >> n;
pow3sum.push_back(0);
for (int i = 0; i < n; ++i) pow3sum.push_back((pow3sum[i] * 3 + 1) % mod);
string input[3];
for (int i = 0; i < 3; ++i) cin >> input[i];
vector<lli> in[3];
for (int i = 0; i < 3; ++i) in[i] = toVec(input[i]);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 9; ++j) {
switch (j / 3) {
case 0:
seq[j].push_back(in[j][i]);
break;
case 1:
seq[j].push_back((- in[j % 3][i] - in[(j + 1) % 3][i] + 6) % 3);
break;
case 2:
seq[j].push_back((in[j % 3][i] + in[(j + 1) % 3][i] - in[(j + 2) % 3][i] + 3) % 3);
break;
}
}
}
vector<lli> hashes;
for (int i = 0; i < 9; ++i) {
hashes.push_back(toHash(seq[i]));
}
int m;
cin >> m;
set<vector<lli>> intervals;
intervals.insert({-1, 0});
intervals.insert({n, 0});
string q;
cin >> q;
lli hash = 0;
for (int i = 0; i < n; ++i) {
intervals.insert({i, toInt(q[i])});
hash += (pow3sum[i + 1] - pow3sum[i] + mod) * toInt(q[i]);
hash %= mod;
}
vector<vector<lli>> erase;
vector<vector<lli>> insert;
char ch;
lli s, e, c, d;
cout << (std::find(hashes.begin(), hashes.end(), toHash(toVec(q))) != hashes.end() ? "Yes" : "No") << "\n";
for (int i = 0; i < m; ++i) {
cin >> s >> e >> ch;
s--;
e--;
c = toInt(ch);
erase = vector<vector<lli>>();
insert = vector<vector<lli>>();
for (auto index = --intervals.lower_bound({s - 1, 3}); (*index)[0] <= e; ++index) {
d = (*index)[1];
index++;
hash = hash + (- pow3sum[min((*index)[0], e + 1)] + mod) * d;
index--;
hash = hash + (pow3sum[max((*index)[0], s)] + mod) * d;
hash %= mod;
index++;
if ((*index)[0] > e + 1) insert.push_back({e + 1, d});
index--;
if ((*index)[0] >= s) erase.push_back(*index);
}
for (const auto& era: erase) intervals.erase(era);
for (const auto& ins: insert) intervals.insert(ins);
intervals.insert({s, c});
hash += (pow3sum[e + 1] - pow3sum[s] + mod) * c;
hash %= mod;
fill(q.begin() + s, q.begin() + e + 1, ch);
if (hash != toHash(toVec(q))) {
return 1;
}
cout << (std::find(hashes.begin(), hashes.end(), toHash(toVec(q))) != hashes.end() ? "Yes" : "No") << "\n";
}
}
Compilation message
Main.cpp: In function 'long long int toHash(std::vector<long long int>)':
Main.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for (int i = 0; i < v.size(); ++i) {
| ~~^~~~~~~~~~
Main.cpp: In function 'std::vector<bool> check(long long int)':
Main.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
39 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
753 ms |
812 KB |
Output is correct |
2 |
Correct |
943 ms |
808 KB |
Output is correct |
3 |
Correct |
900 ms |
856 KB |
Output is correct |
4 |
Correct |
829 ms |
784 KB |
Output is correct |
5 |
Correct |
865 ms |
836 KB |
Output is correct |
6 |
Correct |
816 ms |
864 KB |
Output is correct |
7 |
Correct |
799 ms |
856 KB |
Output is correct |
8 |
Correct |
939 ms |
832 KB |
Output is correct |
9 |
Correct |
924 ms |
820 KB |
Output is correct |
10 |
Incorrect |
876 ms |
888 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
753 ms |
812 KB |
Output is correct |
2 |
Correct |
943 ms |
808 KB |
Output is correct |
3 |
Correct |
900 ms |
856 KB |
Output is correct |
4 |
Correct |
829 ms |
784 KB |
Output is correct |
5 |
Correct |
865 ms |
836 KB |
Output is correct |
6 |
Correct |
816 ms |
864 KB |
Output is correct |
7 |
Correct |
799 ms |
856 KB |
Output is correct |
8 |
Correct |
939 ms |
832 KB |
Output is correct |
9 |
Correct |
924 ms |
820 KB |
Output is correct |
10 |
Incorrect |
876 ms |
888 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
753 ms |
812 KB |
Output is correct |
2 |
Correct |
943 ms |
808 KB |
Output is correct |
3 |
Correct |
900 ms |
856 KB |
Output is correct |
4 |
Correct |
829 ms |
784 KB |
Output is correct |
5 |
Correct |
865 ms |
836 KB |
Output is correct |
6 |
Correct |
816 ms |
864 KB |
Output is correct |
7 |
Correct |
799 ms |
856 KB |
Output is correct |
8 |
Correct |
939 ms |
832 KB |
Output is correct |
9 |
Correct |
924 ms |
820 KB |
Output is correct |
10 |
Incorrect |
876 ms |
888 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
753 ms |
812 KB |
Output is correct |
2 |
Correct |
943 ms |
808 KB |
Output is correct |
3 |
Correct |
900 ms |
856 KB |
Output is correct |
4 |
Correct |
829 ms |
784 KB |
Output is correct |
5 |
Correct |
865 ms |
836 KB |
Output is correct |
6 |
Correct |
816 ms |
864 KB |
Output is correct |
7 |
Correct |
799 ms |
856 KB |
Output is correct |
8 |
Correct |
939 ms |
832 KB |
Output is correct |
9 |
Correct |
924 ms |
820 KB |
Output is correct |
10 |
Incorrect |
876 ms |
888 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |