QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #586124 | #1131. Crossing | makrav | 0 | 55ms | 26028kb | C++20 | 9.8kb | 2024-09-24 05:05:10 | 2024-09-24 05:05:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
struct node {
int cnt[3];
int sm, push;
node() = default;
node(int el) {
for (int j = 0; j < 3; j++) cnt[j]=0;
cnt[el]++;
sm = 0;
push = -1;
}
};
node operator+(node x, node y) {
node nw;
nw.push = -1; nw.sm = 0;
for (int i = 0; i < 3; i++) nw.cnt[i] = x.cnt[i] + y.cnt[i];
return nw;
}
struct segtree {
int n;
vector<node> t;
vector<int> a;
segtree() = default;
segtree(int n_, vector<int> a_) {
n = n_;
a = a_;
t.resize(4 * n);
build(1, 0, n);
}
void build(int v, int tl, int tr) {
if (tl + 1 == tr) {
t[v] = node(a[tl]);
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm, tr);
t[v] = t[v * 2] + t[v * 2 + 1];
}
void push(int v, int tl, int tr) {
if (t[v].push != -1) {
t[v].sm = t[v].cnt[t[v].push];
//cout << v << ' ' << tl << ' ' << tr << ' ' << t[v].push << ' ' << t[v].sm << " pushh\n";
if (tl + 1 < tr) {
t[v * 2].push = t[v].push;
t[v * 2 + 1].push = t[v].push;
}
t[v].push = -1;
return;
}
if (tl + 1 == tr) return;
int sml = (t[v * 2].push == -1 ? t[v * 2].sm : t[v * 2].cnt[t[v * 2].push]),
smr = (t[v * 2 + 1].push == -1 ? t[v * 2 + 1].sm : t[v * 2 + 1].cnt[t[v * 2 + 1].push]);
t[v].sm = sml + smr;
}
void upd(int v, int tl, int tr, int l, int r, int val) {
push(v, tl, tr);
if (l <= tl && tr <= r) {
t[v].push = val;
return;
}
if (tr <= l || tl >= r) return;
int tm = (tl + tr) / 2;
upd(v * 2, tl, tm, l, r, val);
upd(v * 2 + 1, tm, tr, l, r, val);
push(v, tl, tr);
}
int get(int v, int tl, int tr, int l, int r) {
push(v, tl, tr);
if (l <= tl && tr <= r) return t[v].sm;
if (tr <= l || tl >= r) return 0;
int tm = (tl + tr) / 2;
return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm, tr, l, r);
}
};
string xorr(string x, string y) {
string res;
for (int i = 0; i < sz(x); i++) {
if (x[i]==y[i])res += x[i];
else {
res +=char('J'+'O'+'I'-x[i]-y[i]);
}
}
return res;
}
void solve() {
int n;
string s1, s2, s3;
cin >> n >> s1 >> s2 >> s3;
vector<string> LOL = {s1,s2,s3};
unordered_set<string> st;
st.insert(s1); st.insert(s2); st.insert(s3);
while (true) {
bool good = false;
vector<string> adddd;
for (auto ST : st) {
for (auto ST2 : st) {
string cur = xorr(ST, ST2);
if (st.find(cur)==st.end()){good=true; adddd.pb(cur);}
}
}
if(!good) break;
for(auto&u:adddd)st.insert(u);
}
vector<int> PS;
string S;
vector<vector<int>> pos(4);
for (int i = 0; i < n; i++) {
if (s1[i] == s2[i] && s2[i] == s3[i]) {
PS.pb(i);
S += s1[i];
}
else {
int coef = 0;
if (s1[i] == s2[i]) coef = 1;
if (s1[i] == s3[i]) coef = 2;
if (s2[i] == s3[i]) coef = 3;
pos[coef].pb(i);
}
}
vector<char> xd = {'J', 'O', 'I'};
vector<vector<char>> ahaha(4, vector<char>(4, 'l'));
vector<vector<bool>> diff(4, vector<bool>(4, false));
vector<string> HH;
//for(auto&u:pos)cout<<u[0]<<'\n';
for (string H : st) {
HH.pb(H);
cout<<H<<'\n';
for (int i = 0; i < 4; i++) {
if (!pos[i].empty()) {
for (int j = i + 1; j < 4; j++) {
if (!pos[j].empty()) {
if (H[pos[i][0]] == 'J') {
//cout<<"yes\n";
if (ahaha[i][j] == 'l') ahaha[i][j] = H[pos[j][0]];
else if (ahaha[i][j] != H[pos[j][0]]) diff[i][j] = true;
}
}
}
}
}
}
vector<int> US(4);
for (int i = 0; i < 4; i++) {
if (US[i] || pos[i].empty())continue;
for (int j = i + 1; j < 4; j++) {
if (!diff[i][j] && !pos[j].empty()) {
//cout << "fuckxd\n";
//assert(false);
for (int ind = 0; ind < 3; ind++) {
for (int ps : pos[j]) {
pos[i].pb(ps);
for (int I = 0; I < sz(HH); I++) {
if (HH[I][pos[i][0]] == LOL[ind][pos[i][0]]) {
LOL[ind][ps] = HH[I][ps];
break;
}
}
}
}
pos[j].clear();
US[j] = 1;
}
}
}
int q; cin >> q;
string ss; cin >> ss;
vector<vector<int>> qrs(q);
for (int i = 0; i < q; i++) {
int l, r; char c; cin >> l >> r >> c;
l--; r--;
int ps = 0;
for (int j = 0; j < 3; j++) {
if (xd[j] == c) ps = j;
}
qrs[i] = {l, r, ps};
}
auto check = [&](vector<int> pos, vector<vector<int>> newQ, string res) -> vector<int> {
if (pos.empty()) return vector<int>(q + 1, 1);
// for (auto &u : pos) cout << u << ' ';
// cout << '\n';
// cout << res << '\n';
vector<int> lol(sz(pos));
for (int i = 0; i < sz(pos); i++) {
for (int j = 0; j < 3; j++) {
if (xd[j] == res[i]) lol[i] = j;
}
}
// for (auto &u : lol) cout << u << ' ';
// cout << '\n';
segtree sg(sz(pos), lol);
for (int i = 0; i < sz(pos); i++) {
int IND = 0;
for (int j = 0; j < 3; j++) {
if (xd[j] == ss[pos[i]]) IND = j;
}
//cout << IND << ' ';
sg.upd(1, 0, sz(pos), i, i + 1, IND);
}
//cout << '\n';
vector<int> asws;
auto rs = sg.get(1, 0, sz(pos), 0, sz(pos));
asws.pb(rs == sz(pos));
for (int i = 0; i < q; i++) {
//cout << newQ[i][0] << ' ' << newQ[i][1] << ' ' << newQ[i][2] << '\n';
if (newQ[i][0] != -1) {
sg.upd(1, 0, sz(pos), newQ[i][0], newQ[i][1] + 1, newQ[i][2]);
}
rs = sg.get(1, 0, sz(pos), 0, sz(pos));
asws.pb(rs == sz(pos));
}
// cout << "answer: ";
// for (auto &u : asws) cout << u << ' ';
// cout << '\n';
return asws;
};
if(HH.size() <= 27) {
vector<vector<int>> result(HH.size(), vector<int>(q + 1));
vector<int> AP(n);
iota(all(AP), 0);
for (int i = 0; i < HH.size(); i++) {
result[i] = check(AP, qrs, HH[i]);
}
for (int i = 0; i < q + 1; i++) {
bool good = true;
for (int j = 0; j < HH.size(); j++) good &= result[j][i];
cout << (good ? "Yes\n" : "No\n");
}
return;
}
auto genQ = [&](vector<int> pos) {
vector<vector<int>> newQ(q);
for (int i = 0; i < q; i++) {
int L = -1, R = sz(pos);
while (R - L > 1) {
int M = (L + R) / 2;
if (pos[M] >= qrs[i][0]) R = M;
else L = M;
}
int left = R;
L = -1; R = sz(pos);
while (R - L > 1) {
int M = (L + R) / 2;
if (pos[M] <= qrs[i][1]) L = M;
else R = M;
}
int right = L;
if (right >= left) newQ[i] = {left, right, qrs[i][2]};
else newQ[i] = {-1, -1, -1};
}
return newQ;
};
auto rs1 = check(PS, genQ(PS), S);
vector<vector<int>> rs(4, vector<int>(q + 1));
for (int i = 0; i < 4; i++) {
// todo: remake queries
if (pos[i].size() <= 1) {
rs[i].assign(q + 1, 1);
continue;
}
auto newQ = genQ(pos[i]);
vector<int> pss = pos[i];
vector<string> ss(3);
for (int ch = 0; ch < 3; ch++) {
int ind = -1;
for (int j = 0; j < 3; j++) if (LOL[j][pos[i][0]] == xd[ch]) ind = j;
for (int j = 0; j < sz(pos[i]); j++) {
if (ind > -1) ss[ch] += LOL[ind][pos[i][j]];
else {
set<char> st;
for (int jj = 0; jj <3; jj++) st.insert(LOL[jj][pos[i][j]]);
for (int jj = 0; jj < 3; jj++) {
if (st.find(xd[jj]) == st.end()) ss[ch] += xd[jj];
}
}
}
}
for (int j = 0; j < 3; j++) {
auto rss = check(pss, newQ, ss[j]);
for (int ii = 0; ii < q + 1; ii++) rs[i][ii] |= rss[ii];
}
}
for (int i = 0; i < q + 1; i++) {
bool good = rs1[i];
for (int j = 0; j < 4; j++) good &= rs[j][i];
cout << (good ? "Yes\n" : "No\n");
}
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 55ms
memory: 26028kb
input:
80 JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJIJIIIJIJOOIIIJIOIIOJJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJIJIIIJIJOOIIIJIOIIOJJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJIJIIIJIJOOIIIJIOIIOJJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ 185606 IIJJOJIOJOIJIJJJJIOOJIIIIIIJIOIIOJOIJOIJOIJOJOI...
output:
JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJIJIIIJIJOOIIIJIOIIOJJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No 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:
wrong answer 1st lines differ - expected: 'No', found: 'JJIJOJOJOJIJJIJJIJJIJIIIJIIJIJ...JJOOJOJJOJJOOIIOOOOOJIIOIJOJIIJ'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%