QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#814541 | #9783. Duloc Network | ucup-team4967# | WA | 1ms | 3780kb | C++20 | 2.3kb | 2024-12-14 18:08:58 | 2024-12-14 18:08:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 2305843009213693951
#define REP(i,n) for(ll i=0;i<(n);i++)
ll N;
ll remQ = 3500;
void input(void){
cin >> N;
}
void output(int c){
cout << "! " << c << endl;
exit(0);
}
map<vector<ll>,ll> memo;
ll query(vector<ll> C){
if((ll)C.size() == N){
return 0;
}
if(memo.find(C)!=memo.end()){
return memo[C];
}
assert(remQ > 0);
string S(N,'0');
for(ll c:C){
S[c] = '1';
}
cout << "? " << S << endl;
remQ--;
ll c;
cin >> c;
memo[C] = c;
return c;
}
int main(void){
input();
vector<pair<vector<ll>,ll>> C(N);
REP(i,N){
C[i] = {{i},query({i})};
}
// C の [l,r) に連結なところはあるか
function<ll(ll,ll)> ask = [&](ll l, ll r){
assert(0<=l && l<r && r<=(ll)C.size());
vector<ll> E;
ll sum = 0;
for(ll x=l;x<r;x++){
for(ll e:C[x].first){
E.push_back(e);
}
sum += C[x].second;
}
ll q = query(E);
if(q < sum){ // 連結あり
return 1;
}
// 孤立
return 0;
};
while(1){
// cerr << "$$$ " << endl;
// REP(i,(ll)C.size()){
// REP(j,(ll)C[i].first.size()){
// cerr << C[i].first[j] << " ";
// }
// cerr << " " << C[i].second << endl;
// }cerr << endl;
if(C.size()==1){
output(1);
}
ll l = 0, r = C.size();
if(ask(l,r)==0){
output(0);
}
while(abs(r-l)>2){
ll m = (l+r)/2;
if(ask(l,m)==1){
r = m;
}else{
l = m;
}
}
// l と l+1 が連結
pair<vector<ll>,ll> s;
s.first = C[l].first;
for(ll e:C[l+1].first){
s.first.push_back(e);
}
s.second = ask(l,l+1);
for(ll x=l;x+2<(ll)C.size();x++){
C[x] = C[x+2];
}
C.pop_back();
C.pop_back();
C.push_back(s);
}
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 3 2 2 2
output:
? 1000 ? 0100 ? 0010 ? 0001 ? 1100 ! 1
result:
ok Correct answer with 5 queries.
Test #2:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
2 0 0
output:
? 10 ? 01 ! 0
result:
ok Correct answer with 2 queries.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3748kb
input:
4 1 3 2 2 2
output:
? 1000 ? 0100 ? 0010 ? 0001 ? 1100 ! 1
result:
ok Correct answer with 5 queries.
Test #4:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
2 0 0
output:
? 10 ? 01 ! 0
result:
ok Correct answer with 2 queries.
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3780kb
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 15 16 10 5 16 13 8 15 18 9 8 15 13 7 6 17 12 5 17 12 20 15 17 9 4 18 13 16 10 16 12 17 11 6 3 17 12 15 9 19 10 17 11 15 12 17 10 19 11 22 12 2 25 20 8 7 6 24 18 9 8 4 9 6 4 23 14 10 2 4 13 12 4 2 2...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
wrong answer Wrong answer.