QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#85807#5689. 喵了个喵 IIwhateverWA 2667ms691640kbC++173.0kb2023-03-08 15:56:222023-03-08 15:56:51

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-08 15:56:51]
  • 评测
  • 测评结果:WA
  • 用时:2667ms
  • 内存:691640kb
  • [2023-03-08 15:56:22]
  • 提交

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 * 44;
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;
        }
    }
    in_stk[u] = false;
}

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 << 19 | 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: 1556ms
memory: 593620kb

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: 1877ms
memory: 601448kb

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: 1594ms
memory: 597808kb

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: 2667ms
memory: 691640kb

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: 2619ms
memory: 676276kb

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: 2563ms
memory: 681372kb

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