QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#798370#9783. Duloc Networkucup-team5071#WA 1ms3860kbC++206.2kb2024-12-04 12:55:472024-12-04 12:55:48

Judging History

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

  • [2024-12-04 12:55:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3860kb
  • [2024-12-04 12:55:47]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const bool TEST = false;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

struct interactor
{
    int n;
    int query_count;
    vector<vector<int>> G;
    int ans;
    void init()
    {
        query_count = 0;
        if (TEST)
        {
            n = 200;
            G = vector<vector<int>>(n, vector<int>(n));
            for (int i = 0; i < n; ++i)
            {
                for (int j = i + 1; j < n; ++j)
                {
                    int x = rng() % 2;
                    G[i][j] = G[j][i] = x;
                }
            }
            int viscnt = 0;
            vector<int> vis(n);
            auto dfs = [&](auto &self, int now) -> void
            {
                vis[now] = 1;
                viscnt++;
                for (int i = 0; i < n; ++i)
                {
                    if (!vis[i] && G[now][i] == 1)
                    {
                        self(self, i);
                    }
                }
            };
            dfs(dfs, 0);
            if (viscnt == n)
            {
                ans = 1;
            }
            else
            {
                ans = 0;
            }
        }
    }
    int readn()
    {
        if (TEST)
        {
            return n;
        }
        else
        {
            cin >> n;
            return n;
        }
    }
    int query(const string &s)
    {
        query_count++;
        if (TEST == true)
        {
            assert((int)s.size() == n);
            int cnt = 0;
            vector<int> ok(n);
            for (int i = 0; i < n; ++i) // i是否能选
            {
                if (s[i] == '1')
                {
                    continue;
                }
                for (int j = 0; j < n; ++j)
                {
                    if (i == j)
                        continue;
                    if (s[j] == '0')
                        continue;
                    if (G[i][j] == 1)
                    {
                        // cout << i << " " << j << endl;
                        ok[i] = 1;
                        cnt++;
                        break;
                    }
                }
            }
            // cout << "Q: " << s << " " << cnt << endl;
            return cnt;
        }
        else
        {
            cout << "? " << s << endl;
            int res;
            cin >> res;
            return res;
        }
    }
    void answer(int x)
    {
        if (TEST)
        {
            if (x != ans)
            {
                cout << "WA" << endl;
                cout << "ANS : " << ans << " OUT: " << x << endl;
                for (int i = 0; i < n; ++i)
                {
                    for (int j = 0; j < n; ++j)
                    {
                        cout << G[i][j] << " ";
                    }
                    cout << endl;
                }
                exit(1);
            }
            else
            {
                // cout << "AC" << endl;
            }
        }
        else
        {
            cout << "! " << x << endl;
        }
    }
    void outputG()
    {
        cout << n << endl;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                cout << G[i][j] << " ";
            }
            cout << endl;
        }
    }
} inter;
struct SSS
{
    set<int> st;
    int whitecnt;
    int id;
};

void solve()
{

    inter.init();
    // inter.outputG();
    int n = inter.readn();
    vector<int> fa(n);
    iota(fa.begin(), fa.end(), 0);
    vector<SSS> a(n);

    auto get_fa = [&](auto &self, int x) -> int
    {
        if (fa[x] != x)
        {
            return fa[x] = self(self, fa[x]);
        }
        else
        {
            return x;
        }
    };

    auto mergeset = [](const set<int> &s1, const set<int> &s2) -> set<int>
    {
        set<int> res;
        for (auto x : s1)
        {
            res.insert(x);
        }
        for (auto x : s2)
        {
            res.insert(x);
        }
        return res;
    };

    auto set2s = [&](const set<int> &s) -> string
    {
        string res;
        res.assign(n, '0');
        for (auto x : s)
        {
            res[x] = '1';
        }
        return res;
    };
    vector<int> SSS;
    int tot = 0;
    for (int i = 0; i < n; ++i)
    {
        set<int> setx{i};
        int res = inter.query(set2s(setx));
        if (res == 0)
        {
            inter.answer(0);
            return;
        }
        a[i].st = setx;
        a[i].whitecnt = res;
        a[i].id = ++tot;
    }
    set<pair<int, int>> vised;
    while (inter.query_count <= 3450)
    {
        int x, y;
        x = rng() % n;
        y = rng() % n;
        while (x == y)
        {
            x = rng() % n;
            y = rng() % n;
        }
        if (x > y)
        {
            swap(x, y);
        }
        int fx = get_fa(get_fa, x);
        int fy = get_fa(get_fa, y);
        if (fx == fy)
            continue;
        int xid = a[fx].id;
        int yid = a[fy].id;

        auto p = make_pair(xid, yid);
        if (vised.count(p))
            continue;
        // cout << x << " " << y << " " << fx << " " << fy << endl;
        set<int> newst = mergeset(a[fx].st, a[fy].st);
        int qres = inter.query(set2s(newst));
        if (qres == 0)
        {
            if ((int)newst.size() == n)
            {
                inter.answer(1);
                return;
            }
            else
            {
                inter.answer(0);
                return;
            }
        }
        if (qres == a[fx].whitecnt + a[fy].whitecnt)
        {
            vised.insert(p);
            continue;
        }

        fa[fx] = fy;
        for (auto x : a[fx].st)
        {
            a[fy].st.insert(x);
        }
        a[fy].id = ++tot;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // int T = 1000;
    int T = 1;
    // cin >> T;
    while (T--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

input:

4
1
3
2
2
2
1
0

output:

? 1000
? 0100
? 0010
? 0001
? 0110
? 1110
? 1111
! 1

result:

ok Correct answer with 7 queries.

Test #2:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

2
0

output:

? 10
! 0

result:

ok Correct answer with 1 queries.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

4
1
3
2
2
1
1
0

output:

? 1000
? 0100
? 0010
? 0001
? 0011
? 0111
? 1111
! 1

result:

ok Correct answer with 7 queries.

Test #4:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

2
0

output:

? 10
! 0

result:

ok Correct answer with 1 queries.

Test #5:

score: -100
Wrong Answer
time: 1ms
memory: 3860kb

input:

50
3
1
1
1
1
4
3
1
1
2
3
3
2
1
2
4
3
1
1
1
2
4
1
3
1
4
3
2
2
2
4
2
2
1
1
2
1
2
4
1
1
3
3
3
6
2
1
3
2
3
2
4
3
9
7
8
2
5
4
5
2
3
7
7
4
3
6
8
9
9
4
8
9
3
13
13
15
15
17
3
18
18
20
19
18
17
17
16
15
15
3
14
13
12
4
13
13
13
13
14
13
12
12
11
10
9
8
7
6
5
4
4
3
2
1
0

output:

? 10000000000000000000000000000000000000000000000000
? 01000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000
? 00010000000000000000000000000000000000000000000000
? 00001000000000000000000000000000000000000000000000
? 000001000000000000000000000000000...

result:

wrong answer Wrong answer.