QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#85817 | #5689. 喵了个喵 II | LJC00118 | WA | 2940ms | 899380kb | C++14 | 2.9kb | 2023-03-08 16:15:23 | 2023-03-08 16:15:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = a, I = b; i <= I; ++i)
#define per(i, a, b) for (int i = a, I = b; i >= I; --i)
template<typename T> void down(T &x, T y) { if (x > y) x = y; }
const int M = 200000 * 88;
int cnt, dfn, id[M], low[M], bel[M], stk[M], top, tot;
vector<int> e[M];
bool in_stk[M];
void tarjan(int u) {
id[u] = low[u] = ++dfn;
stk[++top] = u;
in_stk[u] = true;
for (auto v : e[u]) {
if (!id[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (in_stk[v]) {
low[u] = min(low[u], id[v]);
}
}
if (id[u] == low[u]) {
++tot;
for (; ; --top) {
int x = stk[top];
bel[x] = tot;
in_stk[x] = false;
if (x == u) break;
}
}
}
int ID(int x, int y) {
return x * 2 + y;
}
void add(int x, int y) {
e[x].push_back(y);
e[y ^ 1].push_back(x ^ 1);
}
const int S = 1 << 20 | 5;
int t[S];
void cover(int p, int l, int r, int ll, int rr, int x) {
if (l >= ll && r <= rr) {
if (t[p]) add(x, t[p]);
return;
}
int mid = (l + r) >> 1;
if (mid >= ll) cover(p << 1, l, mid, ll, rr, x);
if (mid < rr) cover(p << 1 | 1, mid + 1, r, ll, rr, x);
}
void add(int p, int l, int r, int pos, int x) {
int prv = t[p];
t[p] = ++cnt * 2;
if (prv) add(t[p], prv);
add(t[p], x);
if (l == r) return;
int mid = (l + r) >> 1;
if (mid >= pos) add(p << 1, l, mid, pos, x);
else add(p << 1 | 1, mid + 1, r, pos, x);
}
int n, a[200005], rk[200005];
bool ans[200005];
vector<int> pos[50005];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
rep(i, 1, 4 * n) {
cin >> a[i];
rk[i] = pos[a[i]].size();
pos[a[i]].push_back(i);
}
cnt = n;
per(i, 4 * n, 1) {
int x = a[i];
if (rk[i] == 2) {
cover(1, 1, 4 * n, i, pos[x][3], ID(x, 0));
add(1, 1, 4 * n, pos[x][3], ID(x, 1));
} else if (rk[i] == 1) {
cover(1, 1, 4 * n, i, pos[x][3], ID(x, 1));
add(1, 1, 4 * n, pos[x][3], ID(x, 0));
} else if (rk[i] == 0) {
cover(1, 1, 4 * n, i, pos[x][1], ID(x, 0));
cover(1, 1, 4 * n, i, pos[x][2], ID(x, 1));
add(1, 1, 4 * n, pos[x][1], ID(x, 1));
add(1, 1, 4 * n, pos[x][2], ID(x, 0));
}
}
rep(i, 2, cnt * 2 + 1) if (!id[i]) tarjan(i);
rep(i, 1, n) {
int x = ID(i, 0), y = ID(i, 1);
assert(bel[x] && bel[y]);
if (bel[x] == bel[y]) {
cout << "No\n";
return 0;
}
ans[pos[i][0]] = 1;
ans[pos[i][bel[x] < bel[y] ? 2 : 1]] = 1;
}
cout << "Yes\n";
rep(i, 1, 4 * n) cout << ans[i];
cout << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1706ms
memory: 800464kb
input:
50000 12725 41478 2443 1096 36968 36898 3393 45898 43154 26629 22985 37972 13935 25628 40196 40293 39791 29109 455 45812 12634 21086 8928 13600 25416 30244 15917 22568 35849 40189 27442 28785 46334 25651 7172 30994 39724 27853 47091 21306 42087 31612 22081 23002 17127 15269 11569 8254 41080 30112 31...
output:
Yes 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok correct
Test #2:
score: 0
Accepted
time: 1923ms
memory: 806976kb
input:
50000 39298 39298 14319 14319 11620 11620 20424 20424 14345 14345 28478 28478 11587 11587 25545 25545 24607 24607 18203 18203 30593 30593 144 144 2117 2117 14201 14201 27012 27012 20683 20683 39367 39367 7902 7902 12365 12365 17601 17601 29145 29145 15133 15133 47765 47765 22205 22205 13706 13706 20...
output:
Yes 10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010...
result:
ok correct
Test #3:
score: 0
Accepted
time: 1697ms
memory: 802884kb
input:
50000 21684 21684 49246 49246 20339 20339 12374 12374 25130 25130 30869 30869 21854 21854 19251 19251 24016 24016 4812 4812 13915 13915 14386 14386 33943 33943 43449 43449 16175 16175 29984 29984 4712 4712 48795 48795 952 952 3589 3589 34274 34274 12915 12915 6840 6840 23436 23436 15670 15670 3873 3...
output:
Yes 10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010...
result:
ok correct
Test #4:
score: 0
Accepted
time: 2940ms
memory: 899380kb
input:
50000 236 236 32031 707 41062 32031 37516 21446 707 41062 37516 21446 26170 44004 47187 26170 9742 44004 47187 9742 14845 835 14845 43803 4270 835 43803 4270 44275 22853 44275 45825 5286 8810 10767 49050 26809 22853 36108 45825 46063 5286 6289 5206 8810 24938 33324 48973 10767 49050 49412 19286 4152...
output:
Yes 10111011000011101000110110001101111110101011011100111110000001100011111110001100011110001001111111111010100010101010001010011000010111110011100001111100001100001101011110001110011110000111100110001001100011001100111111000111111001010101111010100000101011000100010000010111001111110011001011010011...
result:
ok correct
Test #5:
score: 0
Accepted
time: 2728ms
memory: 885400kb
input:
50000 31692 10868 8109 34968 86 31692 10868 8109 445 38569 31022 34968 86 445 38569 37143 31022 34848 37143 34848 16972 16972 49187 4897 3916 2354 45320 49187 4897 3916 2354 12356 45320 30732 12356 30732 43451 43451 32288 32288 46985 46985 12183 12183 48726 48726 32168 32168 16071 16071 33304 33304 ...
output:
Yes 11111000111000010100101111100001010010101010101010101010110101011001001010111111010010011101110000011010010011000011011011101101010000010011011101100110000110111100000010101101001110001011001011111110010111001110011100010011100100111011100000101111000001100110110110111001110100101000111110111111...
result:
ok correct
Test #6:
score: -100
Wrong Answer
time: 2646ms
memory: 888884kb
input:
50000 47495 24797 47495 24797 15994 5403 31166 15335 15994 5403 31166 14675 15335 37320 14675 13007 37320 1837 13007 1837 39037 9932 39037 20263 9932 22331 28895 28737 30264 20263 22331 28590 38050 29802 10883 28895 27990 21537 28737 30264 39689 24549 29304 10917 45017 31830 28590 38050 29802 10883 ...
output:
No
result:
wrong answer Incorrect