QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#784747 | #1131. Crossing | _8_8_# | 0 | 50ms | 9996kb | C++17 | 3.1kb | 2024-11-26 15:51:34 | 2024-11-26 15:51:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)1e6 + 12, MOD = (int)1e9 + 7;
int n, m;
int conv(char x) {
if(x == 'J') return 0;
if(x == 'O') return 1;
return 2;
}
ll st[N], pr[N];
string t;
vector<string> a(3);
map<string, bool> mem;
unordered_map<ll, bool> vis;
string nv(string x, string y) {
string ret;
for(int i = 0; i < n; i++) {
if(x[i] == y[i]) ret += x[i];
else {
char f;
if(x[i] != 'O' && y[i] != 'O') f = 'O';
else if(x[i] != 'J' && y[i] != 'J') f = 'J';
else f = 'I';
ret += f;
}
}
return ret;
}
void make() {
st[0] = 1;
pr[0] = 1;
for(int i = 1;i <= n; i++) {
st[i] = st[i - 1] * 3ll % MOD;
pr[i] = (pr[i - 1] + st[i]) % MOD;
}
queue<string> q;
q.push(a[0]);mem[a[0]];
if(!mem.count(a[1])) q.push(a[1]);mem[a[1]];
if(!mem.count(a[2])) q.push(a[2]);mem[a[2]];
while(!q.empty()) {
auto r = q.front();
q.pop();
ll _ = 0;
for(int i = 0; i < n; ++i) {
_ += st[i] * 1ll * conv(r[i]) % MOD;
_ %= MOD;
}
vis[_];
for(auto f : a) {
string k = nv(f, r);
if(!mem.count(k)) {
mem[k];
q.push(k);
}
}
a.push_back(r);
}
}
ll s[N * 4], mod[N * 4];
void build(int v = 1, int tl = 0, int tr = n - 1) {
mod[v] = -1;
if(tl == tr) {
s[v] = st[tl] * 1ll * conv(t[tl]) % MOD;
} else {
int tm = (tl + tr) >> 1;
build(v + v, tl, tm);
build(v + v + 1, tm + 1, tr);
s[v] = (s[v + v] + s[v + v + 1]) % MOD;
}
}
void assign(int v, int tl, int tr, int val) {
mod[v] = val;
ll ss = (pr[tr] - (tl ? pr[tl - 1] : 0) + MOD) % MOD;
s[v] = ss * 1ll * val % MOD;
// cout << v << ' ' << tl << ' ' << tr << ' ' << s[v] << '\n';
}
void push(int v, int tl, int tr) {
if(tl != tr && mod[v] != -1) {
int tm = (tl + tr) >> 1;
assign(v + v, tl, tm, mod[v]);
assign(v + v + 1, tm + 1, tr,mod[v]);
}
mod[v] = -1;
}
void upd(int l, int r, int val, int v = 1, int tl = 0, int tr = n - 1) {
if(l > r || tl > r || l > tr) return;
if(tl >= l && tr <= r) {
assign(v, tl, tr, val);
} else {
push(v, tl, tr);
int tm = (tl + tr) >> 1;
upd(l, r, val, v + v, tl, tm);
upd(l, r, val, v + v + 1, tm + 1, tr);
s[v] = (s[v + v] + s[v + v + 1]) % MOD;
}
}
void out() {
cout << (vis.count(s[1]) ? "Yes\n" : "No\n");
}
void test() {
cin >> n >> a[0] >> a[1] >> a[2];
cin >> m >> t;
make();
build();
out();
while(m--) {
int l, r;
char x;
cin >> l >> r >> x;
l--;r--;
upd(l, r, conv(x));
// cout << s[1] << '\n';
out();
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--)
test();
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 3
Accepted
time: 44ms
memory: 9920kb
input:
80 JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJIJIIIJIJOOIIIJIOIIOJJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJIJIIIJIJOOIIIJIOIIOJJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJIJIIIJIJOOIIIJIOIIOJJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ 185606 IIJJOJIOJOIJIJJJJIOOJIIIIIIJIOIIOJOIJOIJOIJOJOI...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 185607 lines
Test #2:
score: 3
Accepted
time: 50ms
memory: 9724kb
input:
100 OOIJOIJIIOOIOIJIJOOIIIJIIOJOJIJOJIOIJJIOJOOIOJOOIIOIOJOJIJJJJIOOIJOIOJIJOOIJOOJOJJJIIOIIIIJIOJJJOIOI OOIJOIJIIOOIOIJIJOOIIIJIIOJOJIJOJIOIJJIOJOOIOJOOIIOIOJOJIJJJJIOOIJOIOJIJOOIJOOJOJJJIIOIIIIJIOJJJOIOI OOIJOIJIIOOIOIJIJOOIIIJIIOJOJIJOJIOIJJIOJOOIOJOOIIOIOJOJIJJJJIOOIJOIOJIJOOIJOOJOJJJIIOIIIIJIOJ...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 200001 lines
Test #3:
score: 3
Accepted
time: 46ms
memory: 9716kb
input:
100 OIIJJJIIJIOJJJIIOIJIIOIJOOIJIJJJOJIIIIIOJJIIJJOOJIJIIIOOIIOJIIJOJIIJOJIJIJOOIIOIJIIJIIOOIIIOIJIOJJOO OIIJJJIIJIOJJJIIOIJIIOIJOOIJIJJJOJIIIIIOJJIIJJOOJIJIIIOOIIOJIIJOJIIJOJIJIJOOIIOIJIIJIIOOIIIOIJIOJJOO OIIJJJIIJIOJJJIIOIJIIOIJOOIJIJJJOJIIIIIOJJIIJJOOJIJIIIOOIIOJIIJOJIIJOJIJIJOOIIOIJIIJIIOOIIIOIJ...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 200001 lines
Test #4:
score: 3
Accepted
time: 41ms
memory: 9760kb
input:
97 OOOIIIJOIOOOIJIIJIIJJOJJJOIJIJIIJOOOOJOJJOJIIIOIIJIJJOJOOJJOIOIOOJOOOJJJOIIIOIIJJIJOJIJIIJJIIIOII OOOIIIJOIOOOIJIIJIIJJOJJJOIJIJIIJOOOOJOJJOJIIIOIIJIJJOJOOJJOIOIOOJOOOJJJOIIIOIIJJIJOJIJIIJJIIIOII OOOIIIJOIOOOIJIIJIIJJOJJJOIJIJIIJOOOOJOJJOJIIIOIIJIJJOJOOJJOIOIOOJOOOJJJOIIIOIIJJIJOJIJIIJJIIIOII 194...
output:
Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No N...
result:
ok 194162 lines
Test #5:
score: 3
Accepted
time: 41ms
memory: 9700kb
input:
91 JOIIOJJJOOIJJJJIJOJIIOJOJOIOIOIJJIIOJIOIJJOIJJOOIIOJIOJIJOOIIIIOOOJIJOIOIJIOJOIJOJOJOOIIJIO JOIIOJJJOOIJJJJIJOJIIOJOJOIOIOIJJIIOJIOIJJOIJJOOIIOJIOJIJOOIIIIOOOJIJOIOIJIOJOIJOJOJOOIIJIO JOIIOJJJOOIJJJJIJOJIIOJOJOIOIOIJJIIOJIOIJJOIJJOOIIOJIOJIJOOIIIIOOOJIJOIOIJIOJOIJOJOJOOIIJIO 193144 JOIIOJJJOOIJJJ...
output:
Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No N...
result:
ok 193145 lines
Test #6:
score: 3
Accepted
time: 37ms
memory: 9768kb
input:
96 JIOIIOOJOOOIOOOJIJIIIIIIJIJIJJIIJOJJIOOIOJOOIOIJJIJOJOOOOJIOJOIIOOJJJOJIJOJJJIJJIIJJIIIIOJOJIOIJ JIOIIOOJOOOIOOOJIJIIIIIIJIJIJJIIJOJJIOOIOJOOIOIJJIJOJOOOOJIOJOIIOOJJJOJIJOJJJIJJIIJJIIIIOJOJIOIJ JIOIIOOJOOOIOOOJIJIIIIIIJIJIJJIIJOJJIOOIOJOOIOIJJIJOJOOOOJIOJOIIOOJJJOJIJOJJJIJJIIJJIIIIOJOJIOIJ 189200...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No...
result:
ok 189201 lines
Test #7:
score: 3
Accepted
time: 41ms
memory: 9700kb
input:
75 IIJOJIJIOOIOJOIIIJIOIIJIOIIJJJJOIJIJIOOJOOJJIIJOIJOOIIIJOIOJJJOIIIIIOJOIIIJ IIJOJIJIOOIOJOIIIJIOIIJIOIIJJJJOIJIJIOOJOOJJIIJOIJOOIIIJOIOJJJOIIIIIOJOIIIJ IIJOJIJIOOIOJOIIIJIOIIJIOIIJJJJOIJIJIOOJOOJJIIJOIJOOIIIJOIOJJJOIIIIIOJOIIIJ 197529 JJIOIJIJOOJOIOJJJIJOJJIJOJJIIIIOJIJIJOOIOOIIJJIOJIOOJJJIOJOIII...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
ok 197530 lines
Test #8:
score: 3
Accepted
time: 43ms
memory: 9768kb
input:
100 OOIOJJIIOJJOOOOIIIIJIJIOIIIOJIOJJIOOJIIIJIJOOOJJJOIIJIIOOOOJIIJOIIJIOJJIJIOOOJIOJJJOIOOOJOJJJOOIJOJO OOIOJJIIOJJOOOOIIIIJIJIOIIIOJIOJJIOOJIIIJIJOOOJJJOIIJIIOOOOJIIJOIIJIOJJIJIOOOJIOJJJOIOOOJOJJJOOIJOJO OOIOJJIIOJJOOOOIIIIJIJIOIIIOJIOJJIOOJIIIJIJOOOJJJOIIJIIOOOOJIIJOIIJIOJJIJIOOOJIOJJJOIOOOJOJJJO...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No...
result:
ok 200001 lines
Test #9:
score: 3
Accepted
time: 44ms
memory: 9996kb
input:
100 IJIIIOOIOIIIOOOIOJJJJOIOJIOIOOJOIJJOJJOIJJOJIIIJOJJIJIIJIIJJOOOOIJOJIOOJOOOJOOOJOIJIOOOIIOIIJOOJJJJO IJIIIOOIOIIIOOOIOJJJJOIOJIOIOOJOIJJOJJOIJJOJIIIJOJJIJIIJIIJJOOOOIJOJIOOJOOOJOOOJOIJIOOOIIOIIJOOJJJJO IJIIIOOIOIIIOOOIOJJJJOIOJIOIOOJOIJJOJJOIJJOJIIIJOJJIJIIJIIJJOOOOIJOJIOOJOOOJOOOJOIJIOOOIIOIIJO...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No...
result:
ok 200001 lines
Test #10:
score: 0
Wrong Answer
time: 40ms
memory: 9920kb
input:
100 IIJOIIOIIIIOOOIOOJIIIOIIOOIJOJIJJOOJJJOOIOOOIOJIIJIIOIJIJOOJIOJOOJJIIOIIOJOOJIIIJJJOOOOIOIOJJIIIOOIO IIJOIIOIIIIOOOIOOJIIIOIIOOIJOJIJJOOJJJOOIOOOIOJIIJIIOIJIJOOJIOJOOJJIIOIIOJOOJIIIJJJOOOOIOIOJJIIIOOIO IIJOIIOIIIIOOOIOOJIIIOIIOOIJOJIJJOOJJJOOIOOOIOJIIJIIOIJIJOOJIOJOOJJIIOIIOJOOJIIIJJJOOOOIOIOJJI...
output:
No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No Yes Yes No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No N...
result:
wrong answer 54th lines differ - expected: 'No', found: 'Yes'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%