QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#777048 | #9783. Duloc Network | ucup-team3670# | WA | 1ms | 3832kb | C++20 | 2.1kb | 2024-11-23 22:28:04 | 2024-11-23 22:28:04 |
Judging History
answer
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
#define sz(a) (int)((a).size())
using namespace std;
typedef long long li;
//const int N = 205;
typedef string bs;
string operator |(const string &a, const string &b){
string c(a.size(), '0');
forn(i, a.size()) c[i] = max(a[i], b[i]);
return c;
}
int n;
map<bs, int> memo;
int ask(bs cur){
int cnt = count(cur.begin(), cur.end(), '1');
if (cnt == 0 || cnt == n)
return memo[cur] = 0;
if (cnt > n - cnt || (cnt == n - cnt && cur[0] == '1')){
forn(i, n) cur[i] ^= '0' ^ '1';
}
if (memo.count(cur))
return memo[cur];
cout << "? ";
forn(i, n) cout << cur[i];
cout << endl;
int x;
cin >> x;
memo[cur] = x;
return x;
}
int aske(bs a, bs b){
return (ask(a) + ask(b) - ask(a | b)) / 2;
}
vector<bs> comp;
vector<int> rk, p;
int getp(int a){
return a == p[a] ? a : p[a] = getp(p[a]);
}
void unite(int a, int b){
a = getp(a), b = getp(b);
if (a == b) return;
if (rk[a] < rk[b]) swap(a, b);
rk[a] += rk[b];
p[b] = a;
comp[a] = comp[a] | comp[b];
}
int main(){
//cin.tie(0);
//ios::sync_with_stdio(false);
cin >> n;
vector<bs> cur(n, string(n, '0'));
forn(i, n) cur[i][i] = '1';
while (sz(cur) > 1){
p.resize(sz(cur));
iota(p.begin(), p.end(), 0);
rk.assign(sz(cur), 1);
comp = cur;
forn(i, sz(cur)){
auto a = cur[i];
cur.erase(cur.begin() + i);
auto collect = [&](int l, int r){
bs tmp(n, '0');
fore(i, l, r) tmp = tmp | cur[i];
return tmp;
};
int l = 0, r = sz(cur);
auto tmp = collect(l, r);
int val = aske(a, tmp);
if (val == 0){
cout << "! " << 0 << endl;
return 0;
}
while (l < r - 1){
int m = (l + r) / 2;
auto nw = collect(l, m);
if (aske(a, nw) == 0)
l = m;
else
r = m;
}
unite(i, l < i ? l : (l + 1));
cur.insert(cur.begin() + i, a);
}
cur.clear();
forn(i, sz(comp)) if (getp(i) == i)
cur.push_back(comp[i]);
}
cout << "! " << 1 << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3572kb
input:
4 1 3 1 2 2 2 2
output:
? 1000 ? 0100 ? 0011 ? 0010 ? 0101 ? 0110 ? 0001 ! 1
result:
ok Correct answer with 7 queries.
Test #2:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
2 0
output:
? 01 ! 0
result:
ok Correct answer with 1 queries.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
4 1 3 1 2 2 2 2
output:
? 1000 ? 0100 ? 0011 ? 0010 ? 0101 ? 0110 ? 0001 ! 1
result:
ok Correct answer with 7 queries.
Test #4:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
2 0
output:
? 01 ! 0
result:
ok Correct answer with 1 queries.
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3632kb
input:
50 3 14 19 14 15 8 11 4 7 3 6 3 6 1 16 16 12 5 6 1 2 4 5 1 15 14 12 13 6 7 1 2 3 3 1 15 15 12 7 2 4 16 14 11 7 6 1 2 2 3 16 18 19 15 17 9 11 4 8 3 7 3 15 19 18 5 8 1 4 2 3 1 16 15 12 5 1 2 2 3 1 15 14 13 6 2 4 2 16 20 10 12 11 12 4 6 2 3 15 20 13 13 7 3 15 19 16 11 2 5 2 4 2 16 17 14 9 6 5 16 16 15 ...
output:
? 10000000000000000000000000000000000000000000000000 ? 01111111111111111111111110000000000000000000000000 ? 00000000000000000000000001111111111111111111111111 ? 01111111111110000000000000000000000000000000000000 ? 11111111111110000000000000000000000000000000000000 ? 011111100000000000000000000000000...
result:
wrong answer Wrong answer.