QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#801506 | #9783. Duloc Network | MrPavlito | WA | 5ms | 3872kb | C++17 | 2.1kb | 2024-12-07 00:52:49 | 2024-12-07 00:52:50 |
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;
}
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;
for(int i=0; i<n; i++)
{
s[i] = '1';
cnt[i] = query(s);
s[i] = '0';
}
org.insert(0);
bool resenje = 1;
for(int i = 1; i<n; i++)
{
int trenutno = query(craft(org));
int l = i;
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: 3840kb
input:
4 1 3 2 2 1 1 2 2 3 2 1 2 1 0 2
output:
? 1000 ? 0100 ? 0010 ? 0001 ? 1000 ? 1110 ? 0110 ? 1100 ? 0100 ? 1100 ? 1110 ? 0010 ? 1110 ? 1111 ? 0001 ! 1
result:
ok Correct answer with 15 queries.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
2 0 0 0 0 0
output:
? 10 ? 01 ? 10 ? 11 ? 01 ! 0
result:
ok Correct answer with 5 queries.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
4 1 3 2 2 1 1 2 2 3 2 1 2 1 0 2
output:
? 1000 ? 0100 ? 0010 ? 0001 ? 1000 ? 1110 ? 0110 ? 1100 ? 0100 ? 1100 ? 1110 ? 0010 ? 1110 ? 1111 ? 0001 ! 1
result:
ok Correct answer with 15 queries.
Test #4:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
2 0 0 0 0 0
output:
? 10 ? 01 ? 10 ? 11 ? 01 ! 0
result:
ok Correct answer with 5 queries.
Test #5:
score: 0
Accepted
time: 3ms
memory: 3652kb
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 3 14 13 15 14 11 8 14 11 14 11 16 13 3 15 13 15 13 12 10 6 3 8 6 6 14 12 16 13 12 7 7 2 6 1 6 14 12 16 12 12 6 15 11 13 8 7 14 15 18 14 12 5 14 10 12 8 7 14 16 17 14 12 5 13 6 15 8 18 11 6 14 15 17...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 455 queries.
Test #6:
score: 0
Accepted
time: 3ms
memory: 3644kb
input:
50 10 13 8 6 13 8 10 8 8 8 9 13 15 11 9 10 14 6 16 10 15 10 7 8 10 10 10 13 10 15 9 10 11 5 16 10 14 11 10 9 9 15 11 10 7 11 12 10 9 10 10 24 25 36 36 33 32 22 20 19 13 19 24 26 35 37 34 31 30 23 21 8 21 23 26 34 37 35 32 32 22 22 6 22 23 27 34 37 35 29 32 18 30 13 30 22 27 33 37 35 26 33 16 32 8 32...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 485 queries.
Test #7:
score: 0
Accepted
time: 3ms
memory: 3612kb
input:
50 1 3 1 4 3 1 1 1 1 3 1 1 1 1 3 5 1 1 1 1 3 2 5 1 2 1 4 1 2 3 4 3 3 2 3 1 1 1 1 3 2 2 1 3 4 2 4 2 3 2 1 16 16 17 16 15 15 16 16 16 15 16 15 5 17 16 16 13 14 9 15 12 13 8 15 11 7 18 17 14 9 14 7 15 9 14 7 14 8 7 18 18 12 8 10 3 11 4 12 5 13 6 7 18 16 13 6 14 7 19 15 17 12 10 17 12 15 5 16 6 18 9 16 ...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 407 queries.
Test #8:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
50 2 14 8 8 7 12 12 8 8 9 9 10 8 8 4 8 9 9 9 11 13 11 8 7 9 12 7 5 6 4 7 8 10 5 5 10 8 4 10 9 11 7 10 8 6 8 10 7 5 9 2 24 23 31 30 33 32 24 23 15 14 15 24 24 30 29 33 30 27 21 21 8 21 23 25 31 31 33 29 30 23 24 8 24 23 26 31 32 33 28 30 18 27 7 27 22 27 31 34 33 29 33 22 30 12 30 22 28 31 35 32 28 3...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 485 queries.
Test #9:
score: 0
Accepted
time: 1ms
memory: 3616kb
input:
50 3 1 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 2 1 1 2 3 1 2 3 2 1 3 1 2 3 1 2 2 1 1 3 15 16 13 13 6 6 4 3 4 1 5 2 2 15 16 13 13 6 6 3 3 3 1 3 1 2 14 16 13 11 13 13 14 12 13 13 1 14 15 12 11 13 12 14 13 15 14 15 14 0 14 14 9 9 5 5 4 4 3 3 2 2
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 113 queries.
Test #10:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
100 1 2 1 1 1 1 1 1 3 3 1 1 2 3 4 1 2 2 2 1 2 2 1 2 2 1 1 1 3 2 1 2 2 1 4 1 1 1 3 2 4 1 3 2 3 3 3 1 1 1 1 2 1 2 2 4 3 1 2 1 1 1 1 3 3 3 2 1 1 2 1 2 2 3 2 1 5 3 5 1 1 1 1 1 1 1 1 3 4 1 2 1 2 1 1 2 1 3 2 1 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 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 128 queries.
Test #11:
score: 0
Accepted
time: 5ms
memory: 3872kb
input:
100 11 13 9 11 8 7 15 12 8 8 7 6 9 12 11 9 10 9 11 16 10 8 9 8 10 6 8 9 13 10 9 7 5 11 14 6 11 16 7 7 8 8 11 8 13 15 11 12 11 11 11 9 10 12 10 6 11 10 5 13 9 9 6 6 6 12 7 12 10 10 9 11 7 11 5 6 9 6 5 9 5 16 11 13 13 10 5 5 8 8 12 11 5 8 8 10 8 10 8 10 11 48 49 64 65 61 60 48 46 33 27 23 13 23 48 50 ...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 1159 queries.
Test #12:
score: -100
Wrong Answer
time: 0ms
memory: 3644kb
input:
100 5 3 3 4 2 2 2 8 4 5 4 4 2 2 3 4 6 5 1 4 3 3 2 5 5 2 2 4 3 4 4 4 4 1 3 5 3 4 4 3 3 4 1 3 3 2 5 5 5 1 3 4 3 4 2 2 4 2 1 3 3 7 3 5 5 6 6 1 3 2 3 3 3 2 1 6 3 5 5 3 4 4 2 2 1 5 7 3 3 1 6 2 2 5 2 5 3 3 6 4 5 36 36 46 46 32 29 19 16 14 10 8 3 11 6 8 37 38 46 44 32 27 21 15 13 5 15 7 16 9 9 39 39 46 42 ...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer Wrong answer.