#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
map<vector<int>, bool> visited;
vector<vector<int> > val2;
int L[N], R[N];
int blsize = 501;
bool works[N][10];
int values[N];
int opt[N][10];
vector <int> b;
vector<int> val(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.push_back(x);
}
return ans;
}
void dp(vector <int> &u){
visited[u] = true;
val2.push_back(u);
vector<vector <int> > q;
for(auto v : val2){
vector<int> next2 = val(v, u);
if(visited[next2]){
continue;
}
q.push_back(next2);
visited[next2] = true;
}
for(auto to : q){
dp(to);
}
}
void update_block(int ind, int v, int bl){
if(opt[bl][ind] == v){
works[bl][ind] = true;
}
else{
works[bl][ind] = false;
}
values[bl] = v;
}
void fil(int bl){
if(values[bl] == -1){
return;
}
for(int i = L[bl]; i <= R[bl]; i++){
b[i] = values[bl];
}
values[bl] = -1;
}
bool check(int bl, int ind){
for(int i = L[bl]; i <= R[bl]; i++){
if(b[i] != val2[ind][i]){
return false;
}
}
return true;
}
void update_ran(int ind, int l, int r, int v){
int bl = l / blsize;
works[bl][ind] = false;
fil(bl);
for(int i = l; i <= r; i++){
b[i] = v;
}
works[bl][ind] = check(bl, ind);
}
bool solve(int sz){
bool ans = false;
for(int j = 0; j < val2.size(); j++){
bool cur = true;
for(int i= 0; i <= sz; i++){
cur &= works[i][j];
}
ans |= cur;
}
return ans;
}
int main(){
int n;
cin >> n;
int cur = 1;
int curbl = 0;
L[0] = 0;
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++){
values[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.push_back(0);
}
else if(a[i][j] == 'J'){
v.push_back(1);
}
else{
v.push_back(2);
}
}
dp(v);
}
int q;
cin >> q;
for(int i = 0; i < n; i++){
char x;
cin >> x;
if(x == 'J'){
b.push_back(1);
}
else if(x == 'O'){
b.push_back(0);
}
else{
b.push_back(2);
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < val2.size(); j++){
update_ran(j, i, i, b[i]);
}
}
for(int j = 0; j < val2.size(); j++){
for(int i = 0; i <= curbl; i++){
opt[i][j] = val2[j][L[i]];
for(int x = L[i] + 1; x <= R[i]; x++)
if(val2[j][x] != val2[j][x - 1])
opt[i][j] = -1;
}
}
solve(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 < val2.size(); j++)
update_ran(j, l, r, x);
}
else{
for(int i = X + 1; i < Y; i++){
for(int j = 0; j < val2.size(); j++)
update_block(j, x, i);
}
for(int j = 0; j < val2.size(); j++){
update_ran(j, l, R[X], x);
update_ran(j, L[Y], r, x);
}
}
solve(curbl) ? cout << "Yes\n" : cout << "No\n";
}
return 0;
}
Compilation message
Main.cpp: In function 'std::vector<int> val(std::vector<int>&, std::vector<int>&)':
Main.cpp:14:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for(int i = 0; i < a.size(); i++){
| ~~^~~~~~~~~~
Main.cpp: In function 'bool solve(int)':
Main.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int j = 0; j < val2.size(); j++){
| ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:141:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
141 | for(int j = 0; j < val2.size(); j++){
| ~~^~~~~~~~~~~~~
Main.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for(int j = 0; j < val2.size(); j++){
| ~~^~~~~~~~~~~~~
Main.cpp:168:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | for(int j = 0; j < val2.size(); j++)
| ~~^~~~~~~~~~~~~
Main.cpp:173:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | for(int j = 0; j < val2.size(); j++)
| ~~^~~~~~~~~~~~~
Main.cpp:176:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | for(int j = 0; j < val2.size(); j++){
| ~~^~~~~~~~~~~~~
Main.cpp:41:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
41 | if(opt[bl][ind] == v){
| ^~
Main.cpp:157:13: note: 'x' was declared here
157 | int x;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
262 ms |
2256 KB |
Output is correct |
2 |
Correct |
319 ms |
2444 KB |
Output is correct |
3 |
Correct |
314 ms |
2212 KB |
Output is correct |
4 |
Correct |
273 ms |
2268 KB |
Output is correct |
5 |
Correct |
271 ms |
2304 KB |
Output is correct |
6 |
Correct |
268 ms |
2296 KB |
Output is correct |
7 |
Correct |
284 ms |
2300 KB |
Output is correct |
8 |
Correct |
284 ms |
2448 KB |
Output is correct |
9 |
Correct |
291 ms |
2360 KB |
Output is correct |
10 |
Correct |
282 ms |
2420 KB |
Output is correct |
11 |
Correct |
280 ms |
2396 KB |
Output is correct |
12 |
Correct |
287 ms |
2536 KB |
Output is correct |
13 |
Correct |
278 ms |
2352 KB |
Output is correct |
14 |
Correct |
291 ms |
2504 KB |
Output is correct |
15 |
Correct |
278 ms |
2432 KB |
Output is correct |
16 |
Correct |
277 ms |
2448 KB |
Output is correct |
17 |
Correct |
296 ms |
2348 KB |
Output is correct |
18 |
Correct |
308 ms |
2372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
262 ms |
2256 KB |
Output is correct |
2 |
Correct |
319 ms |
2444 KB |
Output is correct |
3 |
Correct |
314 ms |
2212 KB |
Output is correct |
4 |
Correct |
273 ms |
2268 KB |
Output is correct |
5 |
Correct |
271 ms |
2304 KB |
Output is correct |
6 |
Correct |
268 ms |
2296 KB |
Output is correct |
7 |
Correct |
284 ms |
2300 KB |
Output is correct |
8 |
Correct |
284 ms |
2448 KB |
Output is correct |
9 |
Correct |
291 ms |
2360 KB |
Output is correct |
10 |
Correct |
282 ms |
2420 KB |
Output is correct |
11 |
Correct |
280 ms |
2396 KB |
Output is correct |
12 |
Correct |
287 ms |
2536 KB |
Output is correct |
13 |
Correct |
278 ms |
2352 KB |
Output is correct |
14 |
Correct |
291 ms |
2504 KB |
Output is correct |
15 |
Correct |
278 ms |
2432 KB |
Output is correct |
16 |
Correct |
277 ms |
2448 KB |
Output is correct |
17 |
Correct |
296 ms |
2348 KB |
Output is correct |
18 |
Correct |
308 ms |
2372 KB |
Output is correct |
19 |
Correct |
639 ms |
11880 KB |
Output is correct |
20 |
Correct |
770 ms |
11800 KB |
Output is correct |
21 |
Correct |
538 ms |
9828 KB |
Output is correct |
22 |
Correct |
415 ms |
9264 KB |
Output is correct |
23 |
Correct |
334 ms |
3696 KB |
Output is correct |
24 |
Correct |
323 ms |
3512 KB |
Output is correct |
25 |
Correct |
480 ms |
11896 KB |
Output is correct |
26 |
Correct |
490 ms |
11916 KB |
Output is correct |
27 |
Correct |
702 ms |
11832 KB |
Output is correct |
28 |
Correct |
563 ms |
11872 KB |
Output is correct |
29 |
Correct |
642 ms |
10156 KB |
Output is correct |
30 |
Correct |
353 ms |
3592 KB |
Output is correct |
31 |
Correct |
650 ms |
11844 KB |
Output is correct |
32 |
Correct |
500 ms |
9748 KB |
Output is correct |
33 |
Correct |
325 ms |
3560 KB |
Output is correct |
34 |
Correct |
536 ms |
11896 KB |
Output is correct |
35 |
Correct |
408 ms |
8860 KB |
Output is correct |
36 |
Correct |
325 ms |
3520 KB |
Output is correct |
37 |
Correct |
319 ms |
3544 KB |
Output is correct |
38 |
Correct |
787 ms |
11664 KB |
Output is correct |
39 |
Correct |
624 ms |
11924 KB |
Output is correct |
40 |
Correct |
431 ms |
7948 KB |
Output is correct |
41 |
Correct |
927 ms |
12192 KB |
Output is correct |
42 |
Correct |
847 ms |
11336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
262 ms |
2256 KB |
Output is correct |
2 |
Correct |
319 ms |
2444 KB |
Output is correct |
3 |
Correct |
314 ms |
2212 KB |
Output is correct |
4 |
Correct |
273 ms |
2268 KB |
Output is correct |
5 |
Correct |
271 ms |
2304 KB |
Output is correct |
6 |
Correct |
268 ms |
2296 KB |
Output is correct |
7 |
Correct |
284 ms |
2300 KB |
Output is correct |
8 |
Correct |
284 ms |
2448 KB |
Output is correct |
9 |
Correct |
291 ms |
2360 KB |
Output is correct |
10 |
Correct |
282 ms |
2420 KB |
Output is correct |
11 |
Correct |
280 ms |
2396 KB |
Output is correct |
12 |
Correct |
287 ms |
2536 KB |
Output is correct |
13 |
Correct |
278 ms |
2352 KB |
Output is correct |
14 |
Correct |
291 ms |
2504 KB |
Output is correct |
15 |
Correct |
278 ms |
2432 KB |
Output is correct |
16 |
Correct |
277 ms |
2448 KB |
Output is correct |
17 |
Correct |
296 ms |
2348 KB |
Output is correct |
18 |
Correct |
308 ms |
2372 KB |
Output is correct |
19 |
Correct |
287 ms |
2284 KB |
Output is correct |
20 |
Correct |
432 ms |
2288 KB |
Output is correct |
21 |
Correct |
283 ms |
2380 KB |
Output is correct |
22 |
Correct |
310 ms |
2148 KB |
Output is correct |
23 |
Correct |
294 ms |
2376 KB |
Output is correct |
24 |
Correct |
283 ms |
2276 KB |
Output is correct |
25 |
Correct |
288 ms |
2376 KB |
Output is correct |
26 |
Correct |
273 ms |
2344 KB |
Output is correct |
27 |
Correct |
320 ms |
2464 KB |
Output is correct |
28 |
Correct |
287 ms |
2136 KB |
Output is correct |
29 |
Correct |
296 ms |
2408 KB |
Output is correct |
30 |
Correct |
262 ms |
2260 KB |
Output is correct |
31 |
Correct |
312 ms |
2352 KB |
Output is correct |
32 |
Correct |
302 ms |
2556 KB |
Output is correct |
33 |
Correct |
312 ms |
2456 KB |
Output is correct |
34 |
Correct |
282 ms |
2248 KB |
Output is correct |
35 |
Correct |
303 ms |
2368 KB |
Output is correct |
36 |
Correct |
299 ms |
2464 KB |
Output is correct |
37 |
Correct |
303 ms |
2428 KB |
Output is correct |
38 |
Correct |
306 ms |
2540 KB |
Output is correct |
39 |
Correct |
302 ms |
2428 KB |
Output is correct |
40 |
Correct |
300 ms |
2408 KB |
Output is correct |
41 |
Correct |
303 ms |
2556 KB |
Output is correct |
42 |
Correct |
320 ms |
2452 KB |
Output is correct |
43 |
Correct |
313 ms |
2384 KB |
Output is correct |
44 |
Correct |
302 ms |
2452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
262 ms |
2256 KB |
Output is correct |
2 |
Correct |
319 ms |
2444 KB |
Output is correct |
3 |
Correct |
314 ms |
2212 KB |
Output is correct |
4 |
Correct |
273 ms |
2268 KB |
Output is correct |
5 |
Correct |
271 ms |
2304 KB |
Output is correct |
6 |
Correct |
268 ms |
2296 KB |
Output is correct |
7 |
Correct |
284 ms |
2300 KB |
Output is correct |
8 |
Correct |
284 ms |
2448 KB |
Output is correct |
9 |
Correct |
291 ms |
2360 KB |
Output is correct |
10 |
Correct |
282 ms |
2420 KB |
Output is correct |
11 |
Correct |
280 ms |
2396 KB |
Output is correct |
12 |
Correct |
287 ms |
2536 KB |
Output is correct |
13 |
Correct |
278 ms |
2352 KB |
Output is correct |
14 |
Correct |
291 ms |
2504 KB |
Output is correct |
15 |
Correct |
278 ms |
2432 KB |
Output is correct |
16 |
Correct |
277 ms |
2448 KB |
Output is correct |
17 |
Correct |
296 ms |
2348 KB |
Output is correct |
18 |
Correct |
308 ms |
2372 KB |
Output is correct |
19 |
Correct |
639 ms |
11880 KB |
Output is correct |
20 |
Correct |
770 ms |
11800 KB |
Output is correct |
21 |
Correct |
538 ms |
9828 KB |
Output is correct |
22 |
Correct |
415 ms |
9264 KB |
Output is correct |
23 |
Correct |
334 ms |
3696 KB |
Output is correct |
24 |
Correct |
323 ms |
3512 KB |
Output is correct |
25 |
Correct |
480 ms |
11896 KB |
Output is correct |
26 |
Correct |
490 ms |
11916 KB |
Output is correct |
27 |
Correct |
702 ms |
11832 KB |
Output is correct |
28 |
Correct |
563 ms |
11872 KB |
Output is correct |
29 |
Correct |
642 ms |
10156 KB |
Output is correct |
30 |
Correct |
353 ms |
3592 KB |
Output is correct |
31 |
Correct |
650 ms |
11844 KB |
Output is correct |
32 |
Correct |
500 ms |
9748 KB |
Output is correct |
33 |
Correct |
325 ms |
3560 KB |
Output is correct |
34 |
Correct |
536 ms |
11896 KB |
Output is correct |
35 |
Correct |
408 ms |
8860 KB |
Output is correct |
36 |
Correct |
325 ms |
3520 KB |
Output is correct |
37 |
Correct |
319 ms |
3544 KB |
Output is correct |
38 |
Correct |
787 ms |
11664 KB |
Output is correct |
39 |
Correct |
624 ms |
11924 KB |
Output is correct |
40 |
Correct |
431 ms |
7948 KB |
Output is correct |
41 |
Correct |
927 ms |
12192 KB |
Output is correct |
42 |
Correct |
847 ms |
11336 KB |
Output is correct |
43 |
Correct |
287 ms |
2284 KB |
Output is correct |
44 |
Correct |
432 ms |
2288 KB |
Output is correct |
45 |
Correct |
283 ms |
2380 KB |
Output is correct |
46 |
Correct |
310 ms |
2148 KB |
Output is correct |
47 |
Correct |
294 ms |
2376 KB |
Output is correct |
48 |
Correct |
283 ms |
2276 KB |
Output is correct |
49 |
Correct |
288 ms |
2376 KB |
Output is correct |
50 |
Correct |
273 ms |
2344 KB |
Output is correct |
51 |
Correct |
320 ms |
2464 KB |
Output is correct |
52 |
Correct |
287 ms |
2136 KB |
Output is correct |
53 |
Correct |
296 ms |
2408 KB |
Output is correct |
54 |
Correct |
262 ms |
2260 KB |
Output is correct |
55 |
Correct |
312 ms |
2352 KB |
Output is correct |
56 |
Correct |
302 ms |
2556 KB |
Output is correct |
57 |
Correct |
312 ms |
2456 KB |
Output is correct |
58 |
Correct |
282 ms |
2248 KB |
Output is correct |
59 |
Correct |
303 ms |
2368 KB |
Output is correct |
60 |
Correct |
299 ms |
2464 KB |
Output is correct |
61 |
Correct |
303 ms |
2428 KB |
Output is correct |
62 |
Correct |
306 ms |
2540 KB |
Output is correct |
63 |
Correct |
302 ms |
2428 KB |
Output is correct |
64 |
Correct |
300 ms |
2408 KB |
Output is correct |
65 |
Correct |
303 ms |
2556 KB |
Output is correct |
66 |
Correct |
320 ms |
2452 KB |
Output is correct |
67 |
Correct |
313 ms |
2384 KB |
Output is correct |
68 |
Correct |
302 ms |
2452 KB |
Output is correct |
69 |
Correct |
966 ms |
23316 KB |
Output is correct |
70 |
Correct |
1510 ms |
27260 KB |
Output is correct |
71 |
Correct |
366 ms |
3932 KB |
Output is correct |
72 |
Correct |
331 ms |
3740 KB |
Output is correct |
73 |
Correct |
335 ms |
3808 KB |
Output is correct |
74 |
Correct |
538 ms |
11108 KB |
Output is correct |
75 |
Correct |
335 ms |
3764 KB |
Output is correct |
76 |
Correct |
505 ms |
13504 KB |
Output is correct |
77 |
Correct |
492 ms |
11312 KB |
Output is correct |
78 |
Correct |
329 ms |
3744 KB |
Output is correct |
79 |
Correct |
336 ms |
3816 KB |
Output is correct |
80 |
Correct |
616 ms |
20140 KB |
Output is correct |
81 |
Correct |
384 ms |
4352 KB |
Output is correct |
82 |
Correct |
744 ms |
27228 KB |
Output is correct |
83 |
Correct |
764 ms |
23592 KB |
Output is correct |
84 |
Correct |
389 ms |
4420 KB |
Output is correct |
85 |
Correct |
378 ms |
4428 KB |
Output is correct |
86 |
Correct |
844 ms |
21088 KB |
Output is correct |
87 |
Correct |
1000 ms |
27312 KB |
Output is correct |
88 |
Correct |
482 ms |
4368 KB |
Output is correct |
89 |
Correct |
781 ms |
24792 KB |
Output is correct |
90 |
Correct |
861 ms |
27248 KB |
Output is correct |
91 |
Correct |
422 ms |
4448 KB |
Output is correct |
92 |
Correct |
614 ms |
20960 KB |
Output is correct |
93 |
Correct |
388 ms |
4352 KB |
Output is correct |
94 |
Correct |
385 ms |
4368 KB |
Output is correct |
95 |
Correct |
387 ms |
4460 KB |
Output is correct |
96 |
Correct |
913 ms |
11688 KB |
Output is correct |
97 |
Correct |
1279 ms |
27368 KB |
Output is correct |
98 |
Correct |
761 ms |
18448 KB |
Output is correct |
99 |
Correct |
1361 ms |
27500 KB |
Output is correct |
100 |
Correct |
1495 ms |
26832 KB |
Output is correct |