QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#865712 | #9783. Duloc Network | ucup-team004 | WA | 7ms | 3712kb | C++23 | 1.9kb | 2025-01-21 21:20:34 | 2025-01-21 21:20:35 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
int query(std::string s) {
std::cout << "? " << s << std::endl;
int ans;
std::cin >> ans;
return ans;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<bool> vis(n);
std::queue<int> q;
q.push(0);
vis[0] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
int qx;
{
std::string s(n, '0');
s[x] = '1';
qx = query(s);
}
std::vector<int> a;
for (int i = 0; i < n; i++) {
if (!vis[i]) {
a.push_back(i);
}
}
if (!a.empty()) {
auto work = [&](this auto &&self, int l, int r) -> void {
std::string s(n, '0');
for (int i = l; i < r; i++) {
s[a[i]] = '1';
}
int qs = query(s);
s[x] = '1';
if (query(s) == qs + qx) {
return;
}
if (r - l == 1) {
int y = a[l];
vis[y] = true;
q.push(y);
return;
}
int m = (l + r) / 2;
self(l, m);
self(m, r);
};
work(0, a.size());
}
}
if (std::find(vis.begin(), vis.end(), false) != vis.end()) {
std::cout << "! 0" << std::endl;
} else {
std::cout << "! 1" << std::endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
4 1 1 0 3 2 1 1 2 2 2 2 3 2 2
output:
? 1000 ? 0111 ? 1111 ? 0100 ? 1100 ? 0011 ? 1011 ? 0010 ? 1010 ? 0001 ? 1001 ? 0100 ? 0010 ? 0001 ! 1
result:
ok Correct answer with 14 queries.
Test #2:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
2 0 0 0
output:
? 10 ? 01 ? 11 ! 0
result:
ok Correct answer with 3 queries.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
4 1 1 0 3 2 1 1 2 2 2 2 3 2 2
output:
? 1000 ? 0111 ? 1111 ? 0100 ? 1100 ? 0011 ? 1011 ? 0010 ? 1010 ? 0001 ? 1001 ? 0100 ? 0010 ? 0001 ! 1
result:
ok Correct answer with 14 queries.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
2 0 0 0
output:
? 10 ? 01 ? 11 ! 0
result:
ok Correct answer with 3 queries.
Test #5:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
50 3 1 0 14 15 14 15 8 11 9 10 4 7 8 9 3 6 5 6 3 6 2 3 16 19 19 18 18 18 15 15 9 11 4 7 5 7 3 6 2 4 6 7 2 4 6 7 2 5 4 5 6 9 19 19 10 11 6 9 5 6 1 4 4 5 3 4 3 5 16 17 11 12 3 6 8 9 6 8 2 4 9 11 4 7 5 7 2 5 3 5 2 5 6 13 14 11 12 7 8 2 4 5 6 1 3 5 6 1 3 4 5 8 10 13 15 17 19 2 5 6 13 14 10 12 13 14 12 1...
output:
? 10000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111 ? 11111111111111111111111111111111111111111111111111 ? 01111111111111111111111110000000000000000000000000 ? 11111111111111111111111110000000000000000000000000 ? 011111111111100000000000000000000...
result:
ok Correct answer with 712 queries.
Test #6:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
50 10 1 0 26 25 36 36 32 33 20 22 13 19 12 16 8 14 6 13 23 29 13 22 16 22 8 17 10 17 36 37 18 26 8 17 13 22 8 18 8 17 29 31 9 17 23 26 13 18 15 22 38 37 36 36 24 28 11 18 17 23 9 18 10 16 27 30 14 20 19 26 6 15 16 23 35 35 27 29 10 18 19 21 15 18 10 17 18 24 7 16 15 21 8 17 10 17 25 24 37 37 36 39 2...
output:
? 10000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111 ? 11111111111111111111111111111111111111111111111111 ? 01111111111111111111111110000000000000000000000000 ? 11111111111111111111111110000000000000000000000000 ? 011111111111100000000000000000000...
result:
ok Correct answer with 254 queries.
Test #7:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
50 1 1 0 17 17 16 17 19 19 9 9 7 7 1 2 6 6 3 4 5 5 3 4 12 13 16 15 18 19 20 19 10 9 5 6 5 4 2 1 3 4 15 16 5 1 1 16 17 15 17 12 16 4 8 3 7 1 6 8 13 7 10 2 7 5 8 3 7 2 6 1 5 1 6 15 18 5 8 5 8 1 6 4 7 1 6 3 6 3 8 12 17 15 15 18 19 13 14 6 9 1 4 5 10 8 10 2 7 6 8 3 6 4 7 11 16 18 20 9 13 5 10 6 10 2 6 4...
output:
? 10000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111 ? 11111111111111111111111111111111111111111111111111 ? 01111111111111111111111110000000000000000000000000 ? 11111111111111111111111110000000000000000000000000 ? 011111111111100000000000000000000...
result:
ok Correct answer with 641 queries.
Test #8:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
50 2 1 0 24 25 30 31 32 33 23 24 14 15 14 16 24 26 28 29 20 21 8 10 15 16 8 10 9 10 21 23 32 34 25 24 33 33 27 27 19 19 12 14 10 10 7 8 5 5 17 18 6 7 11 13 26 28 31 30 27 27 18 18 4 4 15 17 22 23 11 13 17 18 7 9 10 11 28 29 18 19 8 9 12 14 21 22 13 14 10 11 7 9 12 14 14 7 7 27 27 30 31 29 32 14 23 8...
output:
? 10000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111 ? 11111111111111111111111111111111111111111111111111 ? 01111111111111111111111110000000000000000000000000 ? 11111111111111111111111110000000000000000000000000 ? 011111111111100000000000000000000...
result:
ok Correct answer with 326 queries.
Test #9:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
50 3 1 0 16 15 13 13 6 6 3 4 1 4 2 3 1 4 1 2 4 5 2 3 2 5 8 11 10 11 6 7 3 6 5 6 3 6 2 3 1 4 1 2 7 10 16 18 11 13 7 9 3 5 1 4 2 4 1 3 1 4 4 7 8 11 15 18 1 0 1 2 0 2 1 0 1 1 0 1
output:
? 10000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111 ? 11111111111111111111111111111111111111111111111111 ? 01111111111111111111111110000000000000000000000000 ? 11111111111111111111111110000000000000000000000000 ? 011111111111100000000000000000000...
result:
ok Correct answer with 79 queries.
Test #10:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
100 1 1 0 29 30 31 30 26 25 14 13 10 11 7 6 4 5 3 2 1 2 2 1 1 0 1 2 19 20 35 36 1 0 1
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 ? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct answer with 34 queries.
Test #11:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
100 11 1 0 50 49 65 65 60 61 46 48 27 33 13 23 18 24 9 17 11 19 26 32 8 18 20 27 7 18 15 22 39 45 26 32 12 20 16 24 8 17 8 18 22 32 7 17 15 26 61 63 42 48 28 36 12 22 20 29 11 22 9 18 27 34 10 18 18 28 9 19 11 22 47 50 29 36 16 24 18 27 10 20 8 18 24 30 9 18 15 23 8 16 10 20 68 67 57 58 41 47 22 29 ...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 ? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct answer with 638 queries.
Test #12:
score: 0
Accepted
time: 3ms
memory: 3584kb
input:
100 5 1 0 36 36 47 47 29 32 16 19 10 14 3 8 7 11 3 8 4 8 6 10 2 7 4 8 2 7 2 6 22 27 34 36 19 21 9 14 11 13 6 11 6 8 5 7 1 6 17 22 42 44 31 33 16 20 8 13 10 14 3 8 7 11 4 9 4 8 19 22 9 13 4 8 5 10 11 15 3 7 8 13 29 34 43 42 38 39 29 34 29 30 24 27 11 16 13 16 6 9 7 12 15 18 7 10 3 8 5 8 2 5 3 8 9 14 ...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 ? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct answer with 1462 queries.
Test #13:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
100 1 1 0 34 33 37 38 29 28 14 14 7 8 10 10 5 5 1 2 4 4 3 3 1 2 5 6 20 19 9 8 3 4 7 6 4 3 3 4 12 13 31 31 29 29 16 17 19 19 7 7 3 4 6 6 2 2 4 5 13 14 32 32 12 12 6 6 3 4 7 7 5 5 3 4 9 10 22 23 3 3 3 33 33 38 38 19 19 7 10 12 12 6 6 3 4 5 6 1 4 4 5 6 9 24 27 25 28 31 31 28 28 16 19 17 17 7 10 11 11 5...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 ? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct answer with 944 queries.
Test #14:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
100 1 1 0 30 31 30 29 26 25 14 13 9 8 3 4 9 8 5 6 4 3 3 4 1 0 6 7 15 16 25 26 1 0 1
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 ? 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct answer with 34 queries.
Test #15:
score: 0
Accepted
time: 1ms
memory: 3712kb
input:
150 4 1 0 58 59 57 58 39 41 22 26 24 26 12 15 6 10 6 9 2 5 4 8 14 17 7 11 8 11 3 7 5 8 2 6 3 6 43 45 20 23 11 15 13 16 9 12 3 7 6 9 6 10 31 34 19 22 9 13 10 13 5 8 5 9 12 16 55 58 28 32 36 39 21 25 25 28 10 14 15 18 7 10 4 7 3 7 8 12 62 61 62 62 39 39 23 23 11 14 6 9 4 7 2 6 5 9 14 14 6 7 5 6 3 6 10...
output:
? 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct answer with 2872 queries.
Test #16:
score: 0
Accepted
time: 3ms
memory: 3712kb
input:
150 4 1 0 53 53 51 52 31 34 20 23 7 11 13 16 2 6 11 14 8 11 3 7 17 21 34 36 23 25 9 12 7 11 2 5 1 4 1 5 17 20 9 12 4 8 5 8 8 12 24 28 58 59 39 42 25 29 20 23 11 15 13 16 5 9 8 11 3 7 5 8 2 6 4 7 43 45 15 19 33 35 17 21 16 18 7 9 4 6 3 7 9 13 57 56 62 62 34 35 16 17 7 10 4 7 2 5 2 6 3 7 11 13 4 8 7 9...
output:
? 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct answer with 2688 queries.
Test #17:
score: 0
Accepted
time: 5ms
memory: 3584kb
input:
150 3 1 0 63 62 54 56 33 36 38 40 20 22 10 12 6 8 3 5 4 6 4 7 13 15 6 9 7 9 5 7 3 6 25 28 56 55 35 35 19 22 18 18 6 7 3 4 2 3 1 4 3 6 12 14 4 7 8 10 5 7 3 6 38 40 22 24 12 14 7 9 2 5 5 7 7 10 12 15 19 22 56 55 54 54 33 34 18 19 7 8 3 4 1 4 2 3 4 7 11 14 21 24 40 41 24 27 24 25 17 18 5 8 12 13 5 6 7 ...
output:
? 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct answer with 2742 queries.
Test #18:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
150 4 1 0 65 65 61 64 40 43 25 29 18 21 8 11 4 8 4 7 3 6 1 5 11 15 40 44 67 67 39 40 22 23 11 13 6 8 1 5 5 7 5 9 14 16 8 10 4 6 4 8 8 11 3 7 5 8 2 6 3 6 24 28 46 48 32 34 16 20 19 21 6 9 3 7 3 6 13 16 5 9 8 11 3 7 5 8 27 31 60 59 57 57 38 39 18 22 25 26 13 14 7 9 2 6 5 7 7 10 4 7 3 7 13 17 41 42 19 ...
output:
? 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct answer with 2720 queries.
Test #19:
score: 0
Accepted
time: 3ms
memory: 3712kb
input:
150 2 1 0 51 50 42 43 22 23 12 14 15 16 6 8 9 10 3 5 6 7 1 2 5 7 32 33 21 23 14 15 7 8 3 5 6 7 2 4 4 5 2 4 2 3 7 9 53 52 31 31 17 17 8 10 9 9 5 7 4 4 1 3 3 3 1 3 2 2 15 17 35 35 19 19 6 8 13 13 7 7 2 4 5 5 6 8 20 22 50 50 36 38 47 47 37 38 19 20 8 9 4 6 4 5 3 4 1 3 13 15 22 23 10 11 3 5 7 8 2 4 5 6 ...
output:
? 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct answer with 2997 queries.
Test #20:
score: 0
Accepted
time: 3ms
memory: 3584kb
input:
200 1 1 0 63 63 50 50 31 32 31 31 16 17 20 20 9 10 12 12 6 6 1 2 5 5 4 4 1 2 6 7 58 58 30 30 15 15 7 8 8 8 3 4 5 5 2 3 3 3 1 2 2 2 17 18 39 40 65 64 56 57 57 56 31 32 29 28 15 16 15 14 8 9 8 7 5 4 3 2 2 3 5 6 4 2 2 62 62 48 49 31 33 18 22 16 18 10 13 5 9 5 8 1 5 4 7 3 6 1 5 8 10 4 8 4 6 1 5 3 5 1 5 ...
output:
? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct answer with 1329 queries.
Test #21:
score: 0
Accepted
time: 7ms
memory: 3584kb
input:
200 3 1 0 67 67 60 60 38 41 39 39 19 19 11 13 7 10 4 6 1 4 3 5 2 5 1 3 9 10 4 5 1 4 3 4 2 3 1 4 6 9 23 26 60 63 67 66 58 60 35 37 21 24 16 18 9 12 9 11 7 9 1 4 6 8 4 6 2 5 4 7 40 43 64 64 46 46 28 28 15 16 8 10 1 3 7 10 7 9 1 3 6 9 16 17 9 10 5 8 4 5 3 4 1 4 7 10 24 27 40 40 21 21 13 14 7 8 3 4 4 7 ...
output:
? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct answer with 3163 queries.
Test #22:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
200 1 1 0 71 72 67 66 63 62 44 43 23 24 26 25 10 9 5 6 5 4 2 3 3 2 1 0 2 3 16 17 37 38 64 65 1 0 1
output:
? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok Correct answer with 38 queries.
Test #23:
score: -100
Wrong Answer
time: 5ms
memory: 3584kb
input:
200 1 1 0 69 68 64 63 36 35 20 21 21 20 11 10 7 6 2 3 5 4 3 2 2 3 4 5 11 12 49 50 61 62 75 75 63 63 39 39 19 20 22 22 12 13 10 10 5 5 2 3 3 3 2 3 1 1 7 8 46 46 22 23 30 30 15 15 9 9 3 4 6 6 4 4 2 3 6 7 15 16 65 66 3 1 3 67 69 62 64 36 38 20 22 9 12 11 13 4 6 2 4 2 5 7 10 21 24 47 50 62 65 74 76 64 6...
output:
? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
wrong answer Too many queries.