QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#811848 | #9783. Duloc Network | I_Love_Sonechka# | WA | 42ms | 4736kb | C++20 | 3.0kb | 2024-12-13 03:31:00 | 2024-12-13 03:31:00 |
Judging History
answer
#include <complex.h>
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pi pair<int, int>
#define pb push_back
using namespace std;
using ll = long long;
template<typename T_container, typename T = typename enable_if
<!is_same<T_container, string>::value, typename
T_container::value_type>::type>
ostream& operator<<(ostream &os, const T_container &v) {
os << '{';
string sep;
for(const T &x : v) {
os << sep << x;
sep = ", ";
}
return os << '}';
}
void dbg_out(){cerr<<endl;}
template <typename Head, typename... Tail>void dbg_out(Head H
, Tail... T){cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) dbg_out(__VA_ARGS__)
// #define TEST_CASES
#define vt vector
const int amax = 12;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void get() {
int n = 200;
double res = 0;
for(int i = 1; i < n; ++i) {
double P = 1;
for(int j = 1; j <= i; ++j) {
P /= i;
res += P * j;
P *= (i-1);
}
}
cout << 2 * res << '\n';
}
const int MAX_QUERIES = 3500;
void solve() {
int n; cin >> n;
map<string, int> queries;
auto Ask = [&](string s) -> int {
if(queries.count(s)) {
return queries[s];
}
if(queries.size() == MAX_QUERIES) {
cout << "! " << rng() % 2 << endl;
exit(0);
}
assert(queries.size() < MAX_QUERIES);
cout << "? " << s << endl;
fflush(stdout);
int ret; cin >> ret;
return queries[s] = ret;
};
string S;
for(int i = 0; i < n; ++i) {
S.push_back('0');
}
string T = S;
S[rng()%n] = '1';
for(int i = 1; i < n; ++i) {
vt<int> other;
for(int j = 0; j < n; ++j) if(S[j] == '0') {
other.push_back(j);
}
int value = Ask(S);
if(value == n - i) {
break;
}
if(value == 0) {
cout << "! 0" << endl;
fflush(stdout);
return ;
}
stable_sort(other.begin(), other.end(), [&](int x, int y) -> bool {
T[x] = '1';
auto ask_x = Ask(T);
T[x] = '0';
T[y] = '1';
auto ask_y = Ask(T);
T[y] = '0';
return ask_x > ask_y;
});
for(auto u: other) {
T[u] = '1';
int u_value = Ask(T);
T[u] = '0';
S[u] = '1';
int u_and_s = Ask(S);
S[u] = '0';
int s_value = Ask(S);
int inter = s_value + u_value - u_and_s;
if(inter != 0) {
S[u] = '1';
break;
}
}
}
cout << "! 1" << endl;
fflush(stdout);
}
int main() {
// cin.tie(0)->sync_with_stdio(0);
int tt = 1;
#ifdef TEST_CASES
cin >> tt;
#endif
while(tt--)
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3688kb
input:
4 1 2 3 2 2
output:
? 1000 ? 0010 ? 0100 ? 0001 ? 1100 ! 1
result:
ok Correct answer with 5 queries.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
2 0
output:
? 10 ! 0
result:
ok Correct answer with 1 queries.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
4 3
output:
? 0100 ! 1
result:
ok Correct answer with 1 queries.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
2 0
output:
? 01 ! 0
result:
ok Correct answer with 1 queries.
Test #5:
score: 0
Accepted
time: 2ms
memory: 3704kb
input:
50 3 1 3 1 1 1 4 3 1 1 2 3 3 2 1 4 2 3 1 1 1 2 1 4 3 1 3 4 2 2 2 4 2 1 2 1 2 1 2 4 1 1 3 3 3 6 2 2 1 3 6 7 11 11 11 11 10 12 15 16 20 18 20 23 21 24 21 24 20 23 19 22 22 19 22 22 19 22 22 19 22 22 20 22 25 21 24 20 23 20 23 19 22 18 21 17 20 16 19 15 18 15 18 14 17 14 17 14 17 13 16 12 15 11 14 10 1...
output:
? 00000000000000000000000000000000000000000000000100 ? 01000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 000010000000000000000000000000000...
result:
ok Correct answer with 161 queries.
Test #6:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
50 10 13 10 8 6 13 8 10 8 8 8 9 13 15 11 10 9 14 6 16 10 15 7 10 8 10 10 10 13 10 15 9 11 16 5 10 14 11 10 9 15 9 11 10 7 11 12 9 10 10 25 32 34 40 42 41 41 41
output:
? 00000000000000000000000000000001000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 000010000000000000000000000000000...
result:
ok Correct answer with 58 queries.
Test #7:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
50 1 1 3 4 3 1 1 1 3 1 1 1 1 1 3 1 5 1 1 1 3 2 1 5 2 1 1 4 2 3 4 3 3 3 2 1 1 1 1 3 2 2 1 3 4 2 4 3 2 2 5 10 9 9 7 10 12 13 17 13 17 12 16 15 12 16 15 13 17 15 19 18 15 18 21 18 21 19 22 19 22 19 22 19 22 19 22 18 21 17 20 19 17 20 19 16 19 18 15 18 17 14 17 16 13 16 15 12 15 14 11 14 13 10 13 12 9 1...
output:
? 10000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 179 queries.
Test #8:
score: 0
Accepted
time: 2ms
memory: 3572kb
input:
50 9 14 2 8 8 7 12 12 8 8 9 9 10 8 8 8 4 9 9 9 11 13 8 11 7 9 7 12 5 6 4 7 8 5 10 5 10 8 4 10 7 11 10 8 6 8 10 5 7 9 20 27 30 34 34 36 35 35 34 34 33 33 33 33 32 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 7
output:
? 00000000000000000000000000000000000000010000000000 ? 01000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 000010000000000000000000000000000...
result:
ok Correct answer with 92 queries.
Test #9:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
50 2 1 3 1 1 2 1 1 1 1 5 1 2 1 1 1 1 3 1 1 2 1 1 1 2 2 1 1 1 1 3 1 1 2 1 3 1 2 3 2 3 1 1 2 3 1 2 1 2 1 7 5 5 5 5 5 5 3 8 6 6 6 6 6 6 5 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 2 7 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 1 6 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0
output:
? 00000000000000000000000000000001000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 000010000000000000000000000000000...
result:
ok Correct answer with 148 queries.
Test #10:
score: 0
Accepted
time: 7ms
memory: 3988kb
input:
100 1 2 1 1 1 1 1 1 3 1 3 1 1 2 3 1 4 2 2 2 1 2 1 2 2 2 1 1 3 1 2 2 2 1 4 1 1 1 3 2 4 1 3 3 2 3 3 1 1 1 1 1 2 2 2 4 3 1 1 2 1 1 1 3 3 2 3 1 1 2 1 2 3 2 2 1 5 3 5 1 1 1 1 1 1 1 3 1 4 1 2 1 2 1 1 2 1 3 2 1 6 6 5 4 9 9 8 8 7 12 10 15 12 17 15 20 19 17 22 21 19 23 27 26 24 28 27 25 29 28 25 29 28 27 29 ...
output:
? 0000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 770 queries.
Test #11:
score: 0
Accepted
time: 2ms
memory: 3640kb
input:
100 10 13 11 9 11 8 7 15 8 12 8 7 6 9 12 9 11 10 9 11 16 10 9 8 8 10 6 8 9 10 13 9 7 5 11 14 11 6 16 7 7 8 8 8 11 13 15 11 12 11 11 9 11 10 12 10 6 11 13 5 9 9 6 6 6 7 12 12 10 10 9 11 11 7 5 6 9 6 5 5 9 16 11 13 13 10 5 5 8 8 12 11 5 8 8 10 8 10 8 10 25 35 48 55 62 63 68 71 72 76 77 79 79 79 78 79 ...
output:
? 0000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 132 queries.
Test #12:
score: 0
Accepted
time: 7ms
memory: 3604kb
input:
100 3 3 5 3 4 2 2 2 4 8 5 4 4 2 2 4 3 6 5 1 4 3 2 3 5 5 2 2 4 4 3 4 4 4 1 3 3 5 4 4 3 3 4 3 1 3 2 5 5 5 1 4 3 3 4 2 2 4 1 2 3 3 7 3 5 6 5 6 1 2 3 3 2 3 1 6 3 5 5 4 3 4 2 2 1 5 3 7 3 1 6 2 2 2 5 5 3 3 6 4 11 10 9 15 21 26 30 34 37 39 42 43 46 46 47 49 51 51 51 51 53 53 54 57 57 58 57 57 57 56 57 57 5...
output:
? 0000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 184 queries.
Test #13:
score: 0
Accepted
time: 9ms
memory: 3716kb
input:
100 1 1 1 1 3 1 1 3 4 1 1 2 3 4 1 2 1 4 1 3 2 1 2 3 4 1 3 1 1 1 2 1 1 3 1 1 1 4 1 1 1 4 1 1 2 3 3 1 1 3 4 2 2 3 3 1 1 1 4 1 1 1 1 1 1 2 2 2 2 1 2 2 2 2 2 1 1 2 5 2 1 2 1 1 2 2 4 2 1 1 1 5 4 3 1 1 1 1 2 1 6 6 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 3 8 8 7 7 7 7 7 7 7 7 7 7 6 6 6 6 6 6 6 6 6 6 5 10 9...
output:
? 0000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 1200 queries.
Test #14:
score: 0
Accepted
time: 4ms
memory: 3780kb
input:
100 1 1 1 2 3 1 3 2 1 1 1 1 1 1 4 1 1 1 2 1 1 2 1 3 1 1 2 1 2 2 2 1 2 1 1 1 3 4 1 1 1 1 2 3 2 2 1 1 1 1 1 1 1 1 5 3 1 1 1 2 1 2 1 2 2 2 1 3 1 1 1 1 3 1 1 1 1 1 1 1 3 1 1 2 2 1 3 3 2 1 4 3 1 3 2 1 1 2 1 2 6 5 3 8 7 6 10 14 13 13 13 13 13 13 13 10 14 13 13 13 13 13 13 13 13 13 12 16 15 15 15 15 14 18 ...
output:
? 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 877 queries.
Test #15:
score: 0
Accepted
time: 16ms
memory: 3764kb
input:
150 1 2 4 3 2 2 3 2 3 4 3 4 2 2 4 1 6 3 2 3 5 3 4 4 3 6 3 1 2 5 4 5 3 2 3 3 3 2 1 2 4 2 4 1 4 2 3 2 3 1 4 1 4 3 2 2 1 3 3 1 2 1 6 1 2 3 4 1 4 2 4 4 3 1 3 4 4 2 2 5 3 4 2 6 6 2 2 2 3 2 4 4 4 2 2 1 2 3 1 2 3 7 2 1 2 3 5 4 1 2 3 3 2 2 3 5 3 4 2 5 3 1 3 1 2 1 3 3 1 2 3 3 3 2 7 1 2 1 4 2 2 2 3 4 4 3 3 6 ...
output:
? 000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 349 queries.
Test #16:
score: 0
Accepted
time: 19ms
memory: 3716kb
input:
150 3 2 4 2 1 2 1 1 1 8 2 1 3 4 2 4 1 3 2 1 4 3 1 1 4 5 2 3 3 4 2 1 3 4 4 5 2 4 6 4 2 2 2 3 2 6 2 3 3 4 3 3 2 3 2 4 2 1 1 1 1 2 2 4 3 2 3 3 7 1 4 3 3 3 4 2 1 2 2 2 2 1 2 2 4 1 2 2 4 2 4 2 2 6 2 4 4 1 2 2 4 2 5 1 3 4 3 1 2 4 4 2 2 3 4 1 4 2 3 2 3 3 2 3 2 3 6 3 2 3 1 1 5 3 2 3 2 2 2 1 3 3 3 4 3 3 3 2 ...
output:
? 000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 282 queries.
Test #17:
score: 0
Accepted
time: 17ms
memory: 3808kb
input:
150 1 1 3 4 1 4 2 3 1 1 3 1 4 5 7 2 1 1 2 3 4 2 5 3 1 5 1 2 2 3 5 6 2 2 1 3 1 5 3 2 2 3 1 1 2 3 2 2 1 3 2 2 2 5 1 2 2 5 5 2 3 4 1 3 2 1 1 2 2 1 1 3 5 1 3 1 3 2 1 2 2 2 1 1 4 2 2 5 3 2 4 1 2 2 5 1 3 1 3 4 3 2 4 1 3 5 4 2 2 3 1 4 2 3 3 2 1 2 1 3 1 2 1 3 4 1 3 2 4 4 3 1 4 7 1 1 1 1 4 2 3 3 2 2 1 3 1 3 ...
output:
? 000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 480 queries.
Test #18:
score: 0
Accepted
time: 19ms
memory: 3688kb
input:
150 2 4 4 5 4 2 2 5 1 3 4 2 2 3 1 2 1 2 3 3 3 8 1 2 3 2 2 3 1 3 1 2 3 2 3 3 1 7 2 1 5 4 1 4 4 3 2 3 2 5 3 7 2 1 2 1 3 3 5 3 6 3 3 5 5 3 5 1 4 2 5 3 2 2 2 1 2 3 2 2 1 3 2 2 1 5 4 3 6 3 3 2 1 2 3 3 1 2 4 2 2 3 4 3 5 1 2 1 5 2 4 3 6 3 2 3 3 2 1 3 5 1 3 2 3 2 8 5 1 4 5 4 1 1 3 1 1 1 5 1 3 3 4 2 3 2 4 2 ...
output:
? 000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 498 queries.
Test #19:
score: 0
Accepted
time: 20ms
memory: 4008kb
input:
150 1 1 2 1 3 2 2 2 1 1 1 1 1 2 2 1 2 1 3 3 2 2 2 1 1 2 5 4 2 2 1 2 2 2 1 2 2 1 1 2 3 3 2 2 3 1 1 2 2 3 2 1 1 1 3 3 2 2 4 1 1 2 5 2 2 2 2 1 1 3 2 3 1 1 5 3 3 1 1 4 1 2 1 1 3 1 1 3 1 1 1 2 5 3 1 1 1 1 2 2 1 2 1 2 3 2 1 2 1 2 2 2 2 2 3 1 5 2 2 1 3 2 1 2 4 1 1 2 3 3 3 1 1 2 3 2 2 1 1 2 2 3 1 1 1 1 1 4 ...
output:
? 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 1843 queries.
Test #20:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
200 1 3 1 1 3 3 1 1 1 1 1 2 1 3 2 1 2 1 3 1 2 1 1 1 1 2 2 1 1 2 1 1 4 1 1 1 2 1 1 1 2 3 1 1 1 4 1 1 1 1 1 3 1 1 1 2 1 1 1 1 2 1 2 1 1 2 1 1 1 1 4 1 1 1 1 1 1 1 1 1 2 1 1 2 1 2 2 2 4 1 2 1 5 1 2 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 3 1 2 1 1 3 1 1 1 2 5 1 1 1 1 1 4 4 1 1 1 3 1 3 3 1 1 1 4 1 2 3 1 1 2 2 ...
output:
? 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000 ? 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 358 queries.
Test #21:
score: -100
Wrong Answer
time: 42ms
memory: 4736kb
input:
200 1 2 3 2 2 2 2 1 1 1 4 2 1 2 2 2 2 1 1 2 1 1 1 3 1 2 2 2 3 2 1 1 1 2 1 2 2 2 3 3 3 2 2 1 1 4 1 1 2 2 2 2 1 2 2 1 3 3 2 2 1 1 1 1 2 1 2 1 1 2 1 4 1 2 1 1 1 1 3 2 2 1 2 3 4 1 1 2 5 5 2 1 2 3 3 1 3 1 2 2 1 1 1 3 2 2 3 3 1 4 1 2 1 3 2 1 1 1 1 1 4 2 1 1 1 1 2 2 2 2 3 2 2 1 1 1 3 2 3 2 2 2 3 4 1 1 3 2 ...
output:
? 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000 ? 01000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer Wrong answer.