#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 1000001;
map <vector <int>, bool> used;
vector <vector <int> > vec;
vector <int> op(vector <int> &a, vector <int> &b){
vector <int> ans;
for(int i = 0; i < a.size(); i++){
int x = a[i] + b[i];
x = -x;
x %= 3;
x += 3;
x %= 3;
ans.pb(x);
}
return ans;
}
void rec(vector <int> &v){
used[v] = true;
vec.pb(v);
vector <vector <int> > q;
for(auto to : vec){
vector <int> x = op(to, v);
if(used[x]) continue;
q.push_back(x);
used[x] = true;
}
for(auto to : q)
rec(to);
}
int L[nmax], R[nmax];
int blsize = 501;
bool good[nmax][10];
int val[nmax];
int opt[nmax][10];
vector <int> b;
void update_block(int ind, int v, int bl){
if(opt[bl][ind] == v)
good[bl][ind] = true;
else good[bl][ind] = false;
val[bl] = v;
}
void fil(int bl){
if(val[bl] == -1) return;
for(int i = L[bl]; i <= R[bl]; i++)
b[i] = val[bl];
val[bl] = -1;
}
bool check(int bl, int ind){
for(int i = L[bl]; i <= R[bl]; i++){
if(b[i] != vec[ind][i]) return false;
}
return true;
}
void update_ran(int ind, int l, int r, int v){
int bl = l / blsize;
good[bl][ind] = false;
fil(bl);
for(int i = l; i <= r; i++)
b[i] = v;
good[bl][ind] = check(bl, ind);
}
bool CH(int sz){
bool ans = false;
for(int j = 0; j < vec.size(); j++){
bool cur = true;
for(int i= 0; i <= sz; i++){
cur &= good[i][j];
}
ans |= cur;
}
return ans;
}
int main(){
// ios_base::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
int cur = 0;
int curbl = 0;
L[0] = 0;
blsize = sqrt(n);
for(int i = 1; i < n; i++){
if(cur + 1 > blsize){
R[curbl] = i - 1;
cur = 1;
L[++curbl] = i;
}
else cur++;
}
R[curbl] = n - 1;
for(int i = 0; i <= curbl ;i++)
val[i] = -1;
string a[3];
for(int i = 0; i < 3; i++){
vector<int> v;
cin >> a[i];
for(int j = 0; j < n; j++){
if(a[i][j] == 'O')
v.pb(0);
if(a[i][j] == 'J')
v.pb(1);
if(a[i][j] == 'I')
v.pb(2);
}
//used[v] = true;
rec(v);
//vec.pb(v);
}
// cout << vec.size() << "\n";
for(int j = 0; j < vec.size(); j++){
for(int to : vec[j])
cerr << to << ' ';
cerr << "\n";
}
int q; cin >> q;
for(int i = 0; i < n; i++){
char c; cin >> c;
if(c == 'J')
b.pb(1);
if(c == 'O')
b.pb(0);
if(c == 'I')
b.pb(2);
}
// cout << vec.size();
for(int i = 0; i < n; i++){
for(int j = 0; j < vec.size(); j++)
update_ran(j, i, i, b[i]);
}
for(int j = 0; j < vec.size(); j++){
for(int i = 0; i <= curbl; i++){
opt[i][j] = vec[j][L[i]];
for(int x = L[i] + 1; x <= R[i]; x++)
if(vec[j][x] != vec[j][x - 1])
opt[i][j] = -1;
}
}
CH(curbl) ? cout << "Yes\n" : cout << "No\n";
while(q--){
int l,r; cin >> l >> r;
char c; cin >> c;
int x;
if(c == 'O')
x = 0;
if(c == 'J')
x = 1;
if(c == 'I')
x = 2;
l--, r--;
int X = l / blsize;
int Y = r / blsize;
if(X == Y){
for(int j = 0; j < vec.size(); j++)
update_ran(j, l, r, x);
}
else{
for(int i = X + 1; i < Y; i++){
for(int j = 0; j < vec.size(); j++)
update_block(j, x, i);
}
for(int j = 0; j < vec.size(); j++){
update_ran(j, l, R[X], x);
update_ran(j, L[Y], r, x);
}
}
CH(curbl) ? cout << "Yes\n" : cout << "No\n";
}
return 0;
}
Compilation message
Main.cpp: In function 'std::vector<int> op(std::vector<int>&, std::vector<int>&)':
Main.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i = 0; i < a.size(); i++){
| ~~^~~~~~~~~~
Main.cpp: In function 'bool CH(int)':
Main.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int j = 0; j < vec.size(); j++){
| ~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:129:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int j = 0; j < vec.size(); j++){
| ~~^~~~~~~~~~~~
Main.cpp:146:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for(int j = 0; j < vec.size(); j++)
| ~~^~~~~~~~~~~~
Main.cpp:149:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int j = 0; j < vec.size(); j++){
| ~~^~~~~~~~~~~~
Main.cpp:172:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for(int j = 0; j < vec.size(); j++)
| ~~^~~~~~~~~~~~
Main.cpp:177:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for(int j = 0; j < vec.size(); j++)
| ~~^~~~~~~~~~~~
Main.cpp:180:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
180 | for(int j = 0; j < vec.size(); j++){
| ~~^~~~~~~~~~~~
Main.cpp:53:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
53 | if(opt[bl][ind] == v)
| ^~
Main.cpp:161:13: note: 'x' was declared here
161 | int x;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
330 ms |
796 KB |
Output is correct |
| 2 |
Correct |
345 ms |
1028 KB |
Output is correct |
| 3 |
Correct |
356 ms |
880 KB |
Output is correct |
| 4 |
Incorrect |
332 ms |
828 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
330 ms |
796 KB |
Output is correct |
| 2 |
Correct |
345 ms |
1028 KB |
Output is correct |
| 3 |
Correct |
356 ms |
880 KB |
Output is correct |
| 4 |
Incorrect |
332 ms |
828 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
330 ms |
796 KB |
Output is correct |
| 2 |
Correct |
345 ms |
1028 KB |
Output is correct |
| 3 |
Correct |
356 ms |
880 KB |
Output is correct |
| 4 |
Incorrect |
332 ms |
828 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
330 ms |
796 KB |
Output is correct |
| 2 |
Correct |
345 ms |
1028 KB |
Output is correct |
| 3 |
Correct |
356 ms |
880 KB |
Output is correct |
| 4 |
Incorrect |
332 ms |
828 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
