QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#801533 | #9783. Duloc Network | MrPavlito | WA | 6ms | 3872kb | C++17 | 2.0kb | 2024-12-07 01:14:31 | 2024-12-07 01:14:33 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
//#define endl "\n"
#define pii pair<int,int>
using namespace std;
const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
int n;
int query(string s)
{
cout << "? " << s << endl;
cout.flush();
int x;
cin >> x;
return x;
}
string craft(set<int>& niz)
{
string s;
for(int i=0; i<n; i++)s+='0';
for(auto x: niz)s[x] = '1';
return s;
}
void guess(bool t)
{
if(t)cout << "! 1" << endl;
else cout << "! 0" << endl;
}
map<string,int> mapa;
signed main()
{
ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
int tt=1;
//cin >> tt;
while(tt--)
{
cin >> n;
vector<int> cnt(n+1);
string s;
for(int i=0; i<n; i++)s+='0';
set<int> org;
org.insert(0);
bool resenje = 1;
for(int i = 1; i<n; i++)
{
int trenutno = query(craft(org));
int l = 1;
int r = n-1;
int rez = n;
while(l<=r)
{
int mid = l+r >> 1;
set<int> niz = org;
for(int j= i; j<=mid; j++)niz.insert(j);
set<int> setic;
for(auto x:niz)if(!org.count(x))setic.insert(x);
int trcnt = 0;
int tre1 = query(craft(niz));
int tre2 = query(craft(setic));
if(trenutno + tre2 == tre1)l = mid+1;
else
{
r = mid-1;
rez = mid;
}
}
if(rez == n)
{
resenje = false;
break;
}
org.insert(rez);
//for(auto x: org)cout << x << " ";cout << endl;
}
guess(resenje);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3580kb
input:
4 1 1 2 2 3 2 1 2 2 0 1 1 0 0 2
output:
? 1000 ? 1110 ? 0110 ? 1100 ? 0100 ? 1100 ? 1110 ? 0010 ? 1100 ? 0000 ? 1110 ? 1110 ? 0000 ? 1111 ? 0001 ! 1
result:
ok Correct answer with 15 queries.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
2 0 0 0
output:
? 10 ? 11 ? 01 ! 0
result:
ok Correct answer with 3 queries.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
4 1 1 2 2 3 2 1 2 2 0 1 1 0 0 2
output:
? 1000 ? 1110 ? 0110 ? 1100 ? 0100 ? 1100 ? 1110 ? 0010 ? 1100 ? 0000 ? 1110 ? 1110 ? 0000 ? 1111 ? 0001 ! 1
result:
ok Correct answer with 15 queries.
Test #4:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
2 0 0 0
output:
? 10 ? 11 ? 01 ! 0
result:
ok Correct answer with 3 queries.
Test #5:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
50 3 14 13 15 14 11 8 14 11 14 11 16 13 3 15 13 16 14 11 9 5 2 6 3 8 6 6 15 13 15 12 10 5 6 1 6 0 6 0 6 15 13 15 11 10 4 13 8 11 5 12 6 7 16 15 14 10 10 3 12 5 12 8 7 16 16 14 7 18 15 18 11 17 14 6 15 13 10 4 17 11 15 9 16 13 16 10 6 16 11 10 4 17 11 16 10 17 11 17 11 9 16 11 11 3 9 0 9 0 9 0 11 3 1...
output:
? 10000000000000000000000000000000000000000000000000 ? 11111111111111111111111111000000000000000000000000 ? 01111111111111111111111111000000000000000000000000 ? 11111111111110000000000000000000000000000000000000 ? 01111111111110000000000000000000000000000000000000 ? 111111100000000000000000000000000...
result:
ok Correct answer with 465 queries.
Test #6:
score: 0
Accepted
time: 3ms
memory: 3616kb
input:
50 10 24 25 36 36 33 32 22 20 19 13 19 24 26 36 37 33 29 22 12 19 0 21 8 21 24 27 36 38 33 26 22 6 21 0 21 0 22 24 28 36 38 33 23 22 0 30 13 30 24 29 36 38 33 16 30 0 30 0 32 8 32 24 30 36 37 33 10 32 0 32 0 32 0 33 24 31 36 36 33 0 35 18 34 8 34 24 32 36 34 34 0 35 13 34 0 35 8 35 24 33 36 34 35 0 ...
output:
? 10000000000000000000000000000000000000000000000000 ? 11111111111111111111111111000000000000000000000000 ? 01111111111111111111111111000000000000000000000000 ? 11111111111110000000000000000000000000000000000000 ? 01111111111110000000000000000000000000000000000000 ? 111111100000000000000000000000000...
result:
ok Correct answer with 609 queries.
Test #7:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
50 1 16 16 17 16 15 15 16 16 16 15 16 15 5 17 16 17 14 15 10 15 11 14 9 13 8 7 17 16 16 10 16 9 14 7 14 8 7 17 17 12 5 12 8 12 8 13 6 12 8 7 18 16 12 5 13 6 14 7 18 13 17 12 10 17 10 14 4 15 5 16 6 17 7 18 9 11 17 8 14 3 15 4 17 6 18 7 18 7 10 17 7 16 17 16 15 17 9 18 10 12 17 6 14 2 14 3 14 3 14 3 ...
output:
? 10000000000000000000000000000000000000000000000000 ? 11111111111111111111111111000000000000000000000000 ? 01111111111111111111111111000000000000000000000000 ? 11111111111110000000000000000000000000000000000000 ? 01111111111110000000000000000000000000000000000000 ? 111111111111111111100000000000000...
result:
ok Correct answer with 387 queries.
Test #8:
score: 0
Accepted
time: 4ms
memory: 3588kb
input:
50 2 24 23 31 30 33 32 24 23 15 14 15 24 24 31 30 33 29 24 14 15 0 21 8 21 24 25 31 30 33 27 24 8 21 0 21 0 24 24 26 31 31 33 24 24 0 27 7 27 24 27 31 32 33 22 27 0 27 0 30 12 30 24 28 31 31 33 12 30 0 30 0 30 0 33 24 29 31 28 33 0 33 20 33 8 33 24 29 31 28 33 0 33 15 33 0 33 8 33 24 30 31 27 33 0 3...
output:
? 10000000000000000000000000000000000000000000000000 ? 11111111111111111111111111000000000000000000000000 ? 01111111111111111111111111000000000000000000000000 ? 11111111111110000000000000000000000000000000000000 ? 01111111111110000000000000000000000000000000000000 ? 111111100000000000000000000000000...
result:
ok Correct answer with 609 queries.
Test #9:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
50 3 15 16 13 13 6 6 4 3 4 1 5 2 2 15 16 13 13 5 5 3 1 3 3 2 15 15 12 10 13 13 14 12 13 11 14 12 1 15 14 9 10 12 13 15 16 14 15 0 14 14 9 9 6 6 5 5 3 3 2 2
output:
? 10000000000000000000000000000000000000000000000000 ? 11111111111111111111111111000000000000000000000000 ? 01111111111111111111111111000000000000000000000000 ? 11111111111110000000000000000000000000000000000000 ? 01111111111110000000000000000000000000000000000000 ? 111111100000000000000000000000000...
result:
ok Correct answer with 61 queries.
Test #10:
score: 0
Accepted
time: 1ms
memory: 3664kb
input:
100 1 29 28 21 22 27 28 28 27 27 26 26 27 0 28 28 21 21 11 11 7 7 4 4 2 2 1 1
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 1111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000...
result:
ok Correct answer with 28 queries.
Test #11:
score: 0
Accepted
time: 6ms
memory: 3536kb
input:
100 11 48 49 64 65 61 60 48 46 33 27 23 13 23 48 50 64 65 61 58 48 40 33 18 23 0 27 9 27 48 51 64 66 61 59 48 37 33 11 27 0 27 0 33 48 52 64 67 61 52 48 26 33 0 40 8 40 48 53 64 67 61 51 48 20 40 0 40 0 43 7 43 48 54 64 68 61 48 48 15 43 0 43 0 43 0 48 48 55 64 66 61 39 48 0 55 26 50 12 50 48 56 64 ...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 1111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000...
result:
ok Correct answer with 1429 queries.
Test #12:
score: -100
Wrong Answer
time: 6ms
memory: 3592kb
input:
100 5 36 36 46 46 32 29 19 16 14 10 8 3 11 6 8 37 38 46 44 31 25 16 9 11 3 13 5 15 7 9 38 38 46 42 30 22 13 4 25 17 18 10 16 38 38 46 40 30 17 18 4 16 0 16 2 16 38 38 46 39 30 16 18 2 25 9 26 12 18 39 40 47 39 30 13 18 0 26 9 18 0 21 4 21 39 41 47 38 30 9 40 24 36 17 31 11 22 39 42 47 36 31 9 40 22 ...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 1111111111111111111111111111111111111111111111111110000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000...
result:
wrong answer Wrong answer.