QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#811849 | #9783. Duloc Network | I_Love_Sonechka# | WA | 32ms | 4616kb | C++20 | 3.0kb | 2024-12-13 03:31:32 | 2024-12-13 03:31:33 |
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: 3724kb
input:
4 3
output:
? 0100 ! 1
result:
ok Correct answer with 1 queries.
Test #2:
score: 0
Accepted
time: 1ms
memory: 3816kb
input:
2 0
output:
? 01 ! 0
result:
ok Correct answer with 1 queries.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
4 1 2 3 2 2
output:
? 1000 ? 0010 ? 0100 ? 0001 ? 1010 ! 1
result:
ok Correct answer with 5 queries.
Test #4:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
2 0
output:
? 01 ! 0
result:
ok Correct answer with 1 queries.
Test #5:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
50 1 1 3 1 1 4 3 1 2 1 3 3 2 1 2 3 4 1 1 1 2 4 3 1 1 4 2 3 2 2 4 2 2 1 1 2 1 2 4 1 3 1 3 3 6 2 1 2 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 4 5 5 5 5 5 5...
output:
? 00100000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 567 queries.
Test #6:
score: 0
Accepted
time: 2ms
memory: 3756kb
input:
50 11 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 10 5 11 16 10 14 11 10 9 9 15 11 10 7 12 9 10 10 14 17 22 26 28 31 34 35 35 34 35 35 35 34 33 32 31 31
output:
? 00000000000000000000000000000000000000000000010000 ? 01000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 000010000000000000000000000000000...
result:
ok Correct answer with 68 queries.
Test #7:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
50 5 3 1 1 4 3 1 1 1 1 3 1 1 1 1 1 3 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 6 6 6 6 6 5 6 6 6 6 6 6 6 6 6 6 6 6 6 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 4 5 5 5 4 5 5 5 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 5...
output:
? 00000000000000010000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 000010000000000000000000000000000...
result:
ok Correct answer with 513 queries.
Test #8:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
50 7 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 5 12 6 4 7 8 10 5 5 10 8 4 10 9 7 11 10 8 6 8 10 5 7 9 8 11 15 13 16 18 21 23 24 27 27 28 28 29 30 30 33
output:
? 00000000000000000000000000100000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 000010000000000000000000000000000...
result:
ok Correct answer with 67 queries.
Test #9:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
50 1 1 3 1 1 2 1 1 1 1 5 1 2 1 1 3 1 1 1 2 1 1 2 1 2 1 1 1 1 3 1 2 1 2 1 3 1 2 3 2 3 1 1 2 3 1 2 1 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 0
output:
? 00000000000000010000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 000010000000000000000000000000000...
result:
ok Correct answer with 64 queries.
Test #10:
score: 0
Accepted
time: 8ms
memory: 4292kb
input:
100 2 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 1 2 3 1 2 2 1 4 1 1 1 3 2 4 1 2 3 3 3 3 1 1 1 2 1 1 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 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
output:
? 0000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 2555 queries.
Test #11:
score: 0
Accepted
time: 6ms
memory: 3688kb
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 12 10 6 11 10 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 11 16 15 20 20 19 23 28 25 30 29 34 34 33 38 37 ...
output:
? 0000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 150 queries.
Test #12:
score: 0
Accepted
time: 10ms
memory: 3688kb
input:
100 5 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 3 2 3 3 3 2 1 6 3 5 4 3 4 2 2 1 5 3 7 3 1 6 2 2 2 5 5 3 3 6 4 6 6 6 6 5 6 6 6 6 6 6 6 6 7 7 5 6 6 6 6 5 6 6 6 6 6 6 6 7 7 7 7 7 6 7 7 7 7 7 7 7 8 8 8 8 8 8 8 ...
output:
? 0000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 615 queries.
Test #13:
score: 0
Accepted
time: 11ms
memory: 3948kb
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 1 2 3 3 1 1 1 1 4 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 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
output:
? 0000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 1767 queries.
Test #14:
score: 0
Accepted
time: 6ms
memory: 3672kb
input:
100 3 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 1 1 2 1 1 2 1 2 2 1 3 2 1 1 1 1 1 1 3 1 1 1 1 3 1 1 1 2 2 1 3 2 3 1 4 3 1 2 1 3 1 2 1 2 1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
output:
? 0000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 689 queries.
Test #15:
score: 0
Accepted
time: 28ms
memory: 4228kb
input:
150 2 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 1 3 4 4 1 3 2 4 4 2 5 3 4 6 2 6 2 2 2 3 4 2 4 4 2 2 1 1 2 3 2 3 7 2 3 1 2 5 4 1 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:
? 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 2347 queries.
Test #16:
score: 0
Accepted
time: 20ms
memory: 4208kb
input:
150 2 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 3 2 3 2 3 4 1 3 4 4 4 5 2 6 4 2 2 2 2 3 6 2 3 3 3 4 3 2 3 2 4 1 2 1 1 1 2 2 2 4 3 3 3 7 1 3 4 3 3 4 2 2 1 2 2 2 1 4 2 2 1 2 2 4 2 2 4 2 6 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:
? 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 2745 queries.
Test #17:
score: 0
Accepted
time: 32ms
memory: 4512kb
input:
150 2 1 3 4 1 4 2 3 1 1 3 1 1 4 5 1 7 2 1 2 3 4 3 2 5 1 5 1 2 5 2 3 6 2 2 1 5 3 1 3 2 2 3 2 1 1 3 2 2 1 2 3 2 2 5 1 2 5 2 5 2 3 4 1 1 3 2 1 2 2 1 5 1 3 1 3 2 1 3 1 2 2 2 4 1 1 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:
? 000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 3500 queries.
Test #18:
score: 0
Accepted
time: 25ms
memory: 4380kb
input:
150 4 4 4 5 2 2 5 3 4 1 2 2 3 1 1 2 2 3 3 3 8 2 3 1 2 2 3 1 1 2 3 3 2 3 3 7 2 1 1 5 4 1 4 3 4 2 3 2 5 7 2 3 1 2 1 3 5 3 3 6 3 3 5 3 5 5 1 4 2 5 2 2 3 2 1 3 2 2 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:
? 000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 3242 queries.
Test #19:
score: -100
Wrong Answer
time: 28ms
memory: 4616kb
input:
150 3 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 1 1 3 1 1 2 5 1 3 1 1 1 2 2 1 1 2 1 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:
? 000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer Wrong answer.