QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#798370 | #9783. Duloc Network | ucup-team5071# | WA | 1ms | 3860kb | C++20 | 6.2kb | 2024-12-04 12:55:47 | 2024-12-04 12:55:48 |
Judging History
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;
}
详细
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.