QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #421418 | #5018. nth | 2745518585 | 100 ✓ | 34ms | 15052kb | C++20 | 4.2kb | 2024-05-25 18:20:02 | 2024-05-25 18:20:02 |
Judging History
answer
#include<cstdio>
#include<algorithm>
#include"nth.h"
namespace Alice
{
using namespace std;
int n,m,k,l,r,t=20,w,a[M];
void initA(bitset<M> _a,unsigned _m,unsigned _k)
{
m=_m,k=_k;
for(int i=0;i<=M-1;++i) if(_a[i]) a[++n]=i;
m-=n;
if(k<=min(n,m)) l=1,r=k,k=0;
else if(k<=max(n,m))
{
if(n<=m) l=0,r=n;
else l=k-m,r=k;
k=1;
}
else
{
l=k-m,r=n;
k=1;
}
sendA((a[(l+r)/2]&(1<<t))!=0);
}
void receiveA(bool x)
{
if(l==r)
{
int p=(a[l]&(1<<t))!=0;
// printf("A: %d %d %d %d: %d %d\n",l,r,t,w,p,x);for(int i=l;i<=r;++i) printf("%d ",a[i]);printf("\n");
if(p==x) w|=(p<<t),--t;
else if((p<x)^k) report(a[l]);
}
else if(r-l<=1)
{
int p=(a[l+k]&(1<<t))!=0;
// printf("A: %d %d %d %d: %d %d\n",l,r,t,w,p,x);for(int i=l;i<=r;++i) printf("%d ",a[i]);printf("\n");
if(p<x) l=r;
else if(p>x) r=l;
else
{
w|=(p<<t);
if(p==1&&(a[l]&(1<<t))==0) a[l]=w;
if(p==0&&(a[r]&(1<<t))!=0) a[r]=w|((1<<t)-1);
--t;
}
}
else
{
int p=(a[(l+r)/2]&(1<<t))!=0;
// printf("A: %d %d %d %d: %d %d\n",l,r,t,w,p,x);for(int i=l;i<=r;++i) printf("%d ",a[i]);printf("\n");
if(p^x)
{
if(p<x) l=(l+r)/2;
else r=(l+r)/2;
}
else
{
w|=(p<<t);
for(int i=l;i<=r;++i)
{
if(p==1&&(a[i]&(1<<t))==0) a[i]=w;
if(p==0&&(a[i]&(1<<t))!=0) a[i]=w|((1<<t)-1);
}
--t;
}
}
if(t==-1) report(w);
if(l==r) sendA((a[l]&(1<<t))!=0);
else if(r-l==1) sendA((a[l+k]&(1<<t))!=0);
else sendA((a[(l+r)/2]&(1<<t))!=0);
}
}
namespace Bob
{
using namespace std;
int n,m,k,l,r,t=20,w,a[M];
void initB(bitset<M> _a,unsigned _m,unsigned _k)
{
m=_m,k=_k;
for(int i=0;i<=M-1;++i) if(_a[i]) a[++n]=i;
m-=n;
if(k<=min(n,m)) l=1,r=k,k=0;
else if(k<=max(n,m))
{
if(n<=m) l=0,r=n;
else l=k-m,r=k;
k=1;
}
else
{
l=k-m,r=n;
k=1;
}
sendB((a[(l+r+1)/2]&(1<<t))!=0);
}
void receiveB(bool x)
{
if(l==r)
{
int p=(a[l]&(1<<t))!=0;
// printf("B: %d %d %d %d: %d %d\n",l,r,t,w,p,x);for(int i=l;i<=r;++i) printf("%d ",a[i]);printf("\n");
if(p==x) w|=(p<<t),--t;
else if((p<x)^k) report(a[l]);
}
else if(r-l<=1)
{
int p=(a[l+k]&(1<<t))!=0;
// printf("B: %d %d %d %d: %d %d\n",l,r,t,w,p,x);for(int i=l;i<=r;++i) printf("%d ",a[i]);printf("\n");
if(p<x) l=r;
else if(p>x) r=l;
else
{
w|=(p<<t);
if(p==1&&(a[l]&(1<<t))==0) a[l]=w;
if(p==0&&(a[r]&(1<<t))!=0) a[r]=w|((1<<t)-1);
--t;
}
}
else
{
int p=(a[(l+r+1)/2]&(1<<t))!=0;
// printf("B: %d %d %d %d: %d %d\n",l,r,t,w,p,x);for(int i=l;i<=r;++i) printf("%d ",a[i]);printf("\n");
if(p^x)
{
if(p<x) l=(l+r+1)/2;
else r=(l+r+1)/2;
}
else
{
w|=(p<<t);
for(int i=l;i<=r;++i)
{
if(p==1&&(a[i]&(1<<t))==0) a[i]=w;
if(p==0&&(a[i]&(1<<t))!=0) a[i]=w|((1<<t)-1);
}
--t;
}
}
if(t==-1) report(w);
if(l==r) sendB((a[l]&(1<<t))!=0);
else if(r-l==1) sendB((a[l+k]&(1<<t))!=0);
else sendB((a[(l+r+1)/2]&(1<<t))!=0);
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 100
Accepted
Test #1:
score: 100
Accepted
time: 34ms
memory: 14848kb
input:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
3196614622 1083345 2
result:
points 1.0 OK L = 2
Test #2:
score: 100
Accepted
time: 28ms
memory: 12796kb
input:
111111100101001001100100000000111110101000101001001100101010011110000110101011010000000001000111000001011011110101010111001101010000101001101011101001110011001001101111110100001111001001010000110000011011000101010010000000011010010111110000111011011100110000100101111000111111110001100110110111101001...
output:
4153393124 307591 7
result:
points 1.0 OK L = 7
Test #3:
score: 100
Accepted
time: 30ms
memory: 15052kb
input:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
1444424234 522975 8
result:
points 1.0 OK L = 8
Test #4:
score: 100
Accepted
time: 29ms
memory: 10928kb
input:
001101001011011011110001100111001010010100110110111111100011101010001111110101110101110011111001110110111010001100100011010101011000000000001010010001011111110101111100000101000010101110100000110101010100100100010010110010010000001010010100110110100101111110010011011111011111110010100010001110110011...
output:
3619264599 491607 9
result:
points 1.0 OK L = 9
Test #5:
score: 100
Accepted
time: 17ms
memory: 8696kb
input:
111111100110100111101001011010001100010101010010010110010010101011100111110111101101011110111100011001100010111011001000101000111000000000001010110001111010001110110100111110101011000001110000010100111010001110110111000001010101010001110110100111110011111001001101000011101010111010111001100010010000...
output:
2453620143 222311 70
result:
points 1.0 OK L = 70
Test #6:
score: 100
Accepted
time: 15ms
memory: 13064kb
input:
010000110010100010000100101100000101110100111110011000000010000000110000001010010010110100011101010001101010010110000011000000010000000110010010001011010101111111100001110101010101000011100111100011100001001011001011011000100000101101010101111011111011010110011101010011000101000011110100010101110100...
output:
3106575258 96616 76
result:
points 1.0 OK L = 76
Test #7:
score: 100
Accepted
time: 29ms
memory: 8292kb
input:
000010111100100011010101110011011100111000111011001101010101110001011011111000111000111011111101011010111100100011111101110001110000011011100010001000001100000101110011001100101110010000111110100101100010100000111010001000001010011000110111100101011011111101000011010000110100000100011110101001110000...
output:
231451419 44869 74
result:
points 1.0 OK L = 74
Test #8:
score: 100
Accepted
time: 21ms
memory: 8528kb
input:
110011000011011100100010011110111101101010001101101000011011010110111100010011001001101010100110010110011001001110110000111000011101100011101111101111011001111000011000001110101001101001100000000001111100000011010110100000000110011010100100100011001001000000111001100001011010110000101111000000000100...
output:
2146141025 203865 74
result:
points 1.0 OK L = 74
Test #9:
score: 100
Accepted
time: 22ms
memory: 7988kb
input:
010111110100110001011110101111110010110010010000101010001011101000100000101010101000010100111110111101101010111111110101010101110010101000101100100001100001001110011111011010100110001001010000100010101001110010110000001010010011100111000001011110101100101011010100111111101100000000000100011111100111...
output:
1530939132 71635 76
result:
points 1.0 OK L = 76
Test #10:
score: 100
Accepted
time: 26ms
memory: 7696kb
input:
100000000010111111001011011000101110100100110110100000000100010011001111110000000110001110000111010110001010011110010110101111000000101010001001001111100110001101000111010100100111000000011000100111000011101110100111111001111001101111100011101011010010111101101101010011001001101100110001011010101110...
output:
3917079713 66212 72
result:
points 1.0 OK L = 72
Test #11:
score: 100
Accepted
time: 18ms
memory: 7696kb
input:
110011101110110111110100111011101011110000110011010100010100111110001111111001011111110111000010111001110011110011011100100100000001010001000111000010100110011111101010000000100000100100110101001110100001101011110010011001001110110110000001111000111100000110000110101111001001001001101100001100100010...
output:
1969203498 32471 62
result:
points 1.0 OK L = 62
Test #12:
score: 100
Accepted
time: 19ms
memory: 7640kb
input:
000111001100010010000011011000010111000010000110111110011011001001011011000001001110001011101001101000110010111010111000111000011001001000111100100001000000111101101000111000001111011100011111000010000110011101111001110000100100000010101001101000110010011011110110011100101101110000101111010100110000...
output:
314678533 150418 66
result:
points 1.0 OK L = 66
Test #13:
score: 100
Accepted
time: 19ms
memory: 7692kb
input:
001110001000001101001010011100101100011110101100100110000110110000111011111110111010001101011011110010010000010010001001100011000101010110000111110111100111101100011001100001011000100111011100100100011000011001100000100111010001011110011100110011110111011010100011010011101100110010101001011101000000...
output:
3420667525 43478 72
result:
points 1.0 OK L = 72
Test #14:
score: 100
Accepted
time: 14ms
memory: 7640kb
input:
000010101110000110100010111001000010010110110111100101001010010011000000101000011010101100011101010101010100100100000100110011110011100110001111011111111001101100000010010111101101000101110100100111000000011010101001100001010000001100001110111111000111001101111101011011001110011011100100101001100100...
output:
313408403 219687 74
result:
points 1.0 OK L = 74
Test #15:
score: 100
Accepted
time: 26ms
memory: 7688kb
input:
110000101111011000011000101011000001101100100101011110011110110111100101100000011110011001000001000101100000101100100011111010111011000111001111001010011011111001111111001000001010101000110011010001111011100100100011110010001000101100001001010000100011100001101001001101111010101111111100001110010100...
output:
2777622505 129823 76
result:
points 1.0 OK L = 76
Test #16:
score: 100
Accepted
time: 17ms
memory: 7772kb
input:
101110101011011001010011010100101111011100110000011011101001111001111000001111011000101110011001010110100111100001001010010000001011001111101001011000111000110100000100000011101010011111101000101010000010001011001101000110000010101011000000101000110011010111010110011110101101110010001010000011000000...
output:
1604023773 173204 78
result:
points 1.0 OK L = 78
Test #17:
score: 100
Accepted
time: 20ms
memory: 7660kb
input:
101100010100110001101001101000011011001101100100010111010100111001000000100010111101011100001100000011010011000101010000111101001011110000000110010100100111011111010011111011110011111110001010110011100000111110001011011010111000100001001001111110110000000110111010101100111000100011111101000010001100...
output:
1162653421 98067 68
result:
points 1.0 OK L = 68
Test #18:
score: 100
Accepted
time: 21ms
memory: 7700kb
input:
100111111011101111011011000101000011011001100000111001000101100110101001011001111110011100101001100001101111101101010110110111100100110011100111110101101111101110101101010011100010001000010011010111001011100001001011000101101110000001001111010011110010110011001100101101101100110010010110011011010011...
output:
2853070317 247143 70
result:
points 1.0 OK L = 70
Test #19:
score: 100
Accepted
time: 21ms
memory: 7664kb
input:
110111100111100111001111101001110111000000101001011001101111010110000010000100000011111000000111011110010010100111000000001110001001100001000111101010010100101111011011100100001000100111001011110001010010111101001110111101000010010010010010011111001111110111100001001100110100111100000100100101001100...
output:
1170245885 93479 70
result:
points 1.0 OK L = 70
Test #20:
score: 100
Accepted
time: 18ms
memory: 7784kb
input:
010100100000001101011100100011100011001010011011011001011100000110000111100001110100011101011000000110111010101101000100010110100010010110001110101111110111000000001100100010100100111000000110100000001111001100111011111011110010000100100000110101111111010111011110100111011101001110100100111100111110...
output:
1138672942 140644 70
result:
points 1.0 OK L = 70