QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#785542 | #9783. Duloc Network | ucup-team4975# | WA | 3ms | 3812kb | C++23 | 2.5kb | 2024-11-26 18:11:47 | 2024-11-26 18:11:49 |
Judging History
answer
#define LOCAL
#include <bits/stdc++.h>
#define fir first
#define sec second
#define el endl
#ifdef LOCAL
#define FINISH cerr << "FINISH" << endl;
#else
#define FINISH ;
#endif
#ifdef LOCAL
#define debug(x) cerr << setw(4) << #x << " == " << x << endl
#else
#define debug(x)
#endif
#ifdef LOCAL
#define debugv(x) \
cerr << setw(4) << #x << ":: "; \
for (auto i : x) \
cerr << i << " "; \
cerr << endl
#else
#define debugv(x)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
ostream& operator<<(ostream& out, PII& x)
{
out << x.fir << " " << x.sec << endl;
return out;
}
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int N = 200020;
int con[205]={};
int n;
string qstr(int x){
string res(n,'0');
for(int i=x;i<con[x];i++){
res[i]='1';
}
return res;
}
string qstr(int x,int y){
string res(n,'0');
for(int i=x;i<con[x];i++){
res[i]='1';
}
for(int i=y;i<con[y];i++){
res[i]='1';
}
return res;
}
int totq = 0;
bool query(int a1,int a2){
int c1,c2,c12;
totq++;
assert(totq <= 3500);
cout<< "? " <<qstr(a1)<<el;
cin>>c1;
totq++;
assert(totq <= 3500);
cout<< "? " <<qstr(a2)<<el;
totq++;
assert(totq <= 3500);
cin>>c2;
cout<< "? " <<qstr(a1,a2)<<el;
cin>>c12;
if(c1+c2-c12==0){
return false;
}
else return true;
}
// int a[330];
void solve()
{
cin>>n;
// for (int i = 1; i <= n; i++) {
// a[i] = i;
// }
for(int i=0;i<n;i++)con[i]=i+1;
while(1){
if(con[0]==n){
break;
}
vector<int> tmp;
tmp.push_back(0);
for(int i=0;con[i]<n;i=con[i]){
tmp.push_back(con[i]);
if(query(i,con[i]))tmp.pop_back();
}
tmp.push_back(n);
bool flag=0;
for(int i=0;i<tmp.size()-1;i++){
if(con[tmp[i]]!=tmp[i+1]){
flag=1;
con[tmp[i]]=tmp[i+1];
}
}
if(!flag){
cout<<"! 0"<<el;
return ;
}
}
cout<<"! 1"<<el;
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
//cin >> T;
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3812kb
input:
4 1 3 2 3 2 2 2 2 1
output:
? 1000 ? 0100 ? 1100 ? 0100 ? 0010 ? 0110 ? 0010 ? 0001 ? 0011 ! 1
result:
ok Correct answer with 9 queries.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3608kb
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: 3552kb
input:
4 1 3 2 3 2 2 2 2 1
output:
? 1000 ? 0100 ? 1100 ? 0100 ? 0010 ? 0110 ? 0010 ? 0001 ? 0011 ! 1
result:
ok Correct answer with 9 queries.
Test #4:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
2 0 0 0
output:
? 10 ? 01 ? 11 ! 0
result:
ok Correct answer with 3 queries.
Test #5:
score: 0
Accepted
time: 3ms
memory: 3788kb
input:
50 3 1 4 1 1 2 1 1 2 1 1 2 1 4 5 4 3 7 3 1 4 1 1 2 1 2 3 2 3 3 3 3 6 3 2 5 2 1 3 1 2 3 2 4 6 4 3 7 3 1 4 1 1 2 1 1 2 1 2 3 2 4 5 4 1 5 1 3 4 3 1 4 1 4 5 4 3 7 3 2 5 2 2 4 2 2 4 2 4 6 4 2 6 2 2 4 2 1 3 1 1 0 1 2 3 2 1 2 1 2 3 2 4 6 4 1 4 1 1 2 1 3 4 3 3 4 3 3 6 3 6 9 6 2 8 2 1 3 1 3 4 3 2 5 2 3 5 3 1...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 11000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 011000000000000000000000000000000...
result:
ok Correct answer with 402 queries.
Test #6:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
50 10 13 19 13 8 19 8 6 12 6 13 18 13 8 18 8 10 16 10 8 15 8 8 16 8 8 13 8 9 17 9 13 21 13 15 23 15 11 22 11 9 20 9 10 17 10 14 23 14 6 18 6 16 19 16 10 23 10 15 24 15 10 19 10 7 13 7 8 12 8 10 15 10 10 17 10 10 19 10 13 21 13 10 19 10 15 22 15 9 21 9 10 16 10 11 15 11 5 14 5 16 19 16 10 21 10 14 21...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 11000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 011000000000000000000000000000000...
result:
ok Correct answer with 156 queries.
Test #7:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
50 1 3 4 3 1 4 1 4 5 4 3 7 3 1 4 1 1 2 1 1 2 1 1 1 1 3 4 3 1 4 1 1 2 1 1 2 1 1 2 1 3 4 3 5 6 5 1 6 1 1 2 1 1 2 1 1 2 1 3 2 3 2 5 2 5 7 5 1 6 1 2 3 2 1 3 1 4 5 4 1 5 1 2 3 2 3 5 3 4 6 4 3 7 3 3 4 3 2 5 2 3 5 3 1 4 1 1 2 1 1 2 1 1 2 1 3 4 3 2 5 2 2 4 2 1 3 1 3 4 3 4 6 4 2 4 2 4 6 4 2 6 2 3 5 3 2 5 1 3...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 11000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 011000000000000000000000000000000...
result:
ok Correct answer with 516 queries.
Test #8:
score: 0
Accepted
time: 1ms
memory: 3808kb
input:
50 2 14 15 14 8 20 8 8 14 8 7 15 7 12 18 12 12 22 12 8 17 8 8 14 8 9 15 9 9 17 9 10 17 10 8 17 8 8 15 8 4 11 4 8 12 8 9 17 9 9 15 9 9 16 9 11 17 11 13 21 13 11 18 11 8 18 8 7 11 7 9 15 9 12 18 12 7 16 7 5 10 5 6 9 6 4 10 4 7 11 7 8 14 8 10 17 10 5 15 5 5 10 5 10 14 10 8 13 8 4 12 4 10 14 10 9 15 9 1...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 11000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 011000000000000000000000000000000...
result:
ok Correct answer with 180 queries.
Test #9:
score: 0
Accepted
time: 2ms
memory: 3544kb
input:
50 3 1 4 1 1 2 1 1 2 1 2 2 2 1 3 1 1 2 1 1 2 1 1 2 1 5 5 5 1 6 1 2 3 2 1 3 1 1 2 1 1 2 1 1 2 1 3 4 3 1 4 1 1 2 1 2 3 2 1 3 1 1 2 1 1 2 1 2 3 2 2 4 2 1 3 1 1 2 1 1 2 1 1 2 1 3 4 3 1 3 1 2 3 2 1 3 1 1 2 1 2 3 2 3 5 3 1 4 1 2 3 2 3 5 3 2 5 2 1 3 1 3 2 3 1 4 1 2 3 2 3 5 3 1 4 1 2 3 2 2 4 2 1 3 1 1 2 3 1...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 11000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 011000000000000000000000000000000...
result:
ok Correct answer with 414 queries.
Test #10:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
100 1 2 3 2 1 3 1 1 2 1 1 2 1 1 2 1 1 0 1 1 2 1 3 4 3 3 6 3 1 4 1 1 2 1 2 3 2 3 3 3 4 7 4 1 5 1 2 3 2 2 4 2 2 4 2 1 3 1 2 3 2 2 4 2 1 3 1 2 3 2 2 4 2 1 3 1 1 2 1 1 2 1 3 3 3 2 5 2 1 3 1 2 3 2 2 4 2 1 3 1 4 5 4 1 5 1 1 2 1 1 2 1 3 4 3 2 5 2 4 6 4 1 5 1 3 4 3 2 5 2 3 5 3 3 6 3 3 6 3 1 4 1 1 2 1 1 2 1 ...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 11000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 573 queries.
Test #11:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
100 11 13 23 13 9 19 9 11 18 11 8 19 8 7 14 7 15 20 15 12 25 12 8 20 8 8 16 8 7 15 7 6 13 6 9 15 9 12 18 12 11 22 11 9 20 9 10 17 10 9 19 9 11 18 11 16 23 16 10 22 10 8 18 8 9 15 9 8 17 8 10 15 10 6 15 6 8 14 8 9 17 9 13 20 13 10 21 10 9 19 9 7 16 7 5 12 5 11 15 11 14 24 14 6 19 6 11 16 11 16 25 16 ...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 11000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 426 queries.
Test #12:
score: -100
Wrong Answer
time: 0ms
memory: 3808kb
input:
100 5 3 8 3 3 6 3 4 7 4 2 6 2 2 4 2 2 4 2 8 10 8 4 12 4 5 9 5 4 9 4 4 8 4 2 6 2 2 4 2 3 5 3 4 7 4 6 9 6 5 10 5 1 6 1 4 5 4 3 7 3 3 4 3 2 5 2 5 7 5 5 10 5 2 7 2 2 4 2 4 6 4 3 7 3 4 7 4 4 7 4 4 8 4 4 8 4 1 5 1 3 4 3 5 8 5 3 8 3 4 7 4 4 8 4 3 7 3 3 6 3 4 7 4 1 5 1 3 4 3 3 6 3 2 5 2 5 7 5 5 10 5 5 10 5 ...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 11000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer Wrong answer.