QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#308298#5018. nthHarry27182100 ✓29ms27044kbC++142.8kb2024-01-19 20:49:292024-01-19 20:49:30

Judging History

你现在查看的是最新测评结果

  • [2024-01-19 20:49:30]
  • 评测
  • 测评结果:100
  • 用时:29ms
  • 内存:27044kb
  • [2024-01-19 20:49:29]
  • 提交

answer

#include"nth.h"
#include<bits/stdc++.h>
using namespace std; 
namespace Alice
{
	int n=0,a[(1<<21)+5],l,r,dep,tmp[(1<<21)+5],c;
	void send()
	{
		int mid=(l+r)>>1;
		sendA((a[mid]>>dep)&1);
	}
	void initA(bitset<M> A,unsigned S,unsigned c)
	{
		for(int i=0;i<(1<<21);i++)if(A[i])a[++n]=i;
		int m=S-n;
		if(m>=c&&n>=c)n=c,c=0;
		else if(max(n,m)>=c)
		{
			if(n>=c)
			{
				for(int i=1;i<=n;i++)tmp[i]=a[i];
				int tot=0;
				for(int i=c-m;i<=c;i++)a[++tot]=tmp[i];
				n=tot;
			}
			else 
			{
				int tot=0;
				for(int i=1;i<=n;i++)tmp[i]=a[i];
				a[++tot]=0;
				for(int i=1;i<=n;i++)a[++tot]=tmp[i];
				n=tot;
			}
			c=1;
		}
		else
		{
			int tot=0;
			for(int i=1;i<=n;i++)tmp[i]=a[i];
			for(int i=c-m;i<=n;i++)a[++tot]=tmp[i];
			n=tot;c=1;
		}
		l=1;r=n;dep=20;Alice::c=c;send();
	}
	void receiveA(bool x)
	{
		if(l==r-1)
		{
			for(int i=dep;i>=0;i--)sendA((a[l]>>i)&1);
			for(int i=dep;i>=0;i--)sendA((a[r]>>i)&1);
			return;
		}
		int mid=(l+r)>>1;
		int now=(a[mid]>>dep)&1;
		if(now<x)l=mid;
		else if(now>x)r=mid;
		else 
		{
			int val=(a[mid]>>dep)<<dep;
			for(int i=1;i<=n;i++)a[i]=max(a[i],val),a[i]=min(a[i],val+(1<<dep)-1);
			dep--;
		}
		if(l==r&&((now>x&&c==1)||(now<x&&c==0)))report(a[l]);
		if(dep==-1)report(a[l]);
		send();
	}
}
namespace Bob
{	
	int n=0,b[(1<<21)+5],l,r,dep,tmp[(1<<21)+5],val[105],p,c,res[4];
	void send()
	{
		int mid=(l+r+1)>>1;
		sendB((b[mid]>>dep)&1);
	}
	void initB(std::bitset<M> B,unsigned S,unsigned c)
	{
		for(int i=0;i<(1<<21);i++)if(B[i])b[++n]=i;
		int m=S-n;
		if(m>=c&&n>=c)n=c,c=0;
		else if(max(n,m)>=c)
		{
			if(n>=c)
			{
				for(int i=1;i<=n;i++)tmp[i]=b[i];
				int tot=0;
				for(int i=c-m;i<=c;i++)b[++tot]=tmp[i];
				n=tot;
			}
			else 
			{
				int tot=0;
				for(int i=1;i<=n;i++)tmp[i]=b[i];
				b[++tot]=0;
				for(int i=1;i<=n;i++)b[++tot]=tmp[i];
				n=tot;
			}
			c=1;
		}
		else
		{
			int tot=0;
			for(int i=1;i<=n;i++)tmp[i]=b[i];
			for(int i=c-m;i<=n;i++)b[++tot]=tmp[i];
			n=tot;c=1;
		}
		l=1;r=n;dep=20;Bob::c=c;send();
	}
	void receiveB(bool x)
	{
		if(l==r-1)
		{
			val[p++]=x;
			if(p==2*dep+3)
			{
				res[0]=b[l];res[1]=b[r];int num=(b[l]>>(dep+1))<<(dep+1);
				for(int i=1;i<=dep+1;i++)res[2]=(res[2]<<1)|val[i];
				for(int i=dep+2;i<=2*dep+2;i++)res[3]=(res[3]<<1)|val[i];
				res[2]+=num;res[3]+=num;
				sort(res,res+4);
				if(c==0)report(res[1]);
				else report(res[2]);
			}
			return;
		}
		int mid=(l+r+1)>>1;
		int now=(b[mid]>>dep)&1;
		if(now<x)l=mid;
		else if(now>x)r=mid;
		else 
		{
			int val=(b[mid]>>dep)<<dep;
			for(int i=1;i<=n;i++)b[i]=max(b[i],val),b[i]=min(b[i],val+(1<<dep)-1);
			dep--;
		}
		if(l==r&&((now>x&&c==1)||(now<x&&c==0)))report(b[l]);
		if(dep==-1)report(b[l]);
		send();
	}
}

详细

Subtask #1:

score: 100
Accepted

Test #1:

score: 100
Accepted
time: 26ms
memory: 25324kb

input:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3196614622 1083345 2

result:

points 1.0 OK L = 2

Test #2:

score: 100
Accepted
time: 28ms
memory: 26608kb

input:

111111100101001001100100000000111110101000101001001100101010011110000110101011010000000001000111000001011011110101010111001101010000101001101011101001110011001001101111110100001111001001010000110000011011000101010010000000011010010111110000111011011100110000100101111000111111110001100110110111101001...

output:

4153393124 307591 7

result:

points 1.0 OK L = 7

Test #3:

score: 100
Accepted
time: 28ms
memory: 26100kb

input:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

1444424234 522975 44

result:

points 1.0 OK L = 44

Test #4:

score: 100
Accepted
time: 29ms
memory: 27044kb

input:

001101001011011011110001100111001010010100110110111111100011101010001111110101110101110011111001110110111010001100100011010101011000000000001010010001011111110101111100000101000010101110100000110101010100100100010010110010010000001010010100110110100101111110010011011111011111110010100010001110110011...

output:

3619264599 491607 44

result:

points 1.0 OK L = 44

Test #5:

score: 100
Accepted
time: 16ms
memory: 17588kb

input:

111111100110100111101001011010001100010101010010010110010010101011100111110111101101011110111100011001100010111011001000101000111000000000001010110001111010001110110100111110101011000001110000010100111010001110110111000001010101010001110110100111110011111001001101000011101010111010111001100010010000...

output:

2453620143 222311 70

result:

points 1.0 OK L = 70

Test #6:

score: 100
Accepted
time: 12ms
memory: 18144kb

input:

010000110010100010000100101100000101110100111110011000000010000000110000001010010010110100011101010001101010010110000011000000010000000110010010001011010101111111100001110101010101000011100111100011100001001011001011011000100000101101010101111011111011010110011101010011000101000011110100010101110100...

output:

3106575258 96616 78

result:

points 1.0 OK L = 78

Test #7:

score: 100
Accepted
time: 20ms
memory: 18812kb

input:

000010111100100011010101110011011100111000111011001101010101110001011011111000111000111011111101011010111100100011111101110001110000011011100010001000001100000101110011001100101110010000111110100101100010100000111010001000001010011000110111100101011011111101000011010000110100000100011110101001110000...

output:

231451419 44869 74

result:

points 1.0 OK L = 74

Test #8:

score: 100
Accepted
time: 21ms
memory: 25304kb

input:

110011000011011100100010011110111101101010001101101000011011010110111100010011001001101010100110010110011001001110110000111000011101100011101111101111011001111000011000001110101001101001100000000001111100000011010110100000000110011010100100100011001001000000111001100001011010110000101111000000000100...

output:

2146141025 203865 76

result:

points 1.0 OK L = 76

Test #9:

score: 100
Accepted
time: 14ms
memory: 17620kb

input:

010111110100110001011110101111110010110010010000101010001011101000100000101010101000010100111110111101101010111111110101010101110010101000101100100001100001001110011111011010100110001001010000100010101001110010110000001010010011100111000001011110101100101011010100111111101100000000000100011111100111...

output:

1530939132 71635 76

result:

points 1.0 OK L = 76

Test #10:

score: 100
Accepted
time: 20ms
memory: 18576kb

input:

100000000010111111001011011000101110100100110110100000000100010011001111110000000110001110000111010110001010011110010110101111000000101010001001001111100110001101000111010100100111000000011000100111000011101110100111111001111001101111100011101011010010111101101101010011001001101100110001011010101110...

output:

3917079713 66212 72

result:

points 1.0 OK L = 72

Test #11:

score: 100
Accepted
time: 16ms
memory: 21308kb

input:

110011101110110111110100111011101011110000110011010100010100111110001111111001011111110111000010111001110011110011011100100100000001010001000111000010100110011111101010000000100000100100110101001110100001101011110010011001001110110110000001111000111100000110000110101111001001001001101100001100100010...

output:

1969203498 32471 62

result:

points 1.0 OK L = 62

Test #12:

score: 100
Accepted
time: 22ms
memory: 17368kb

input:

000111001100010010000011011000010111000010000110111110011011001001011011000001001110001011101001101000110010111010111000111000011001001000111100100001000000111101101000111000001111011100011111000010000110011101111001110000100100000010101001101000110010011011110110011100101101110000101111010100110000...

output:

314678533 150418 66

result:

points 1.0 OK L = 66

Test #13:

score: 100
Accepted
time: 15ms
memory: 17996kb

input:

001110001000001101001010011100101100011110101100100110000110110000111011111110111010001101011011110010010000010010001001100011000101010110000111110111100111101100011001100001011000100111011100100100011000011001100000100111010001011110011100110011110111011010100011010011101100110010101001011101000000...

output:

3420667525 43478 74

result:

points 1.0 OK L = 74

Test #14:

score: 100
Accepted
time: 20ms
memory: 18632kb

input:

000010101110000110100010111001000010010110110111100101001010010011000000101000011010101100011101010101010100100100000100110011110011100110001111011111111001101100000010010111101101000101110100100111000000011010101001100001010000001100001110111111000111001101111101011011001110011011100100101001100100...

output:

313408403 219687 76

result:

points 1.0 OK L = 76

Test #15:

score: 100
Accepted
time: 14ms
memory: 18180kb

input:

110000101111011000011000101011000001101100100101011110011110110111100101100000011110011001000001000101100000101100100011111010111011000111001111001010011011111001111111001000001010101000110011010001111011100100100011110010001000101100001001010000100011100001101001001101111010101111111100001110010100...

output:

2777622505 129823 78

result:

points 1.0 OK L = 78

Test #16:

score: 100
Accepted
time: 22ms
memory: 25240kb

input:

101110101011011001010011010100101111011100110000011011101001111001111000001111011000101110011001010110100111100001001010010000001011001111101001011000111000110100000100000011101010011111101000101010000010001011001101000110000010101011000000101000110011010111010110011110101101110010001010000011000000...

output:

1604023773 173204 78

result:

points 1.0 OK L = 78

Test #17:

score: 100
Accepted
time: 17ms
memory: 18196kb

input:

101100010100110001101001101000011011001101100100010111010100111001000000100010111101011100001100000011010011000101010000111101001011110000000110010100100111011111010011111011110011111110001010110011100000111110001011011010111000100001001001111110110000000110111010101100111000100011111101000010001100...

output:

1162653421 98067 68

result:

points 1.0 OK L = 68

Test #18:

score: 100
Accepted
time: 16ms
memory: 18312kb

input:

100111111011101111011011000101000011011001100000111001000101100110101001011001111110011100101001100001101111101101010110110111100100110011100111110101101111101110101101010011100010001000010011010111001011100001001011000101101110000001001111010011110010110011001100101101101100110010010110011011010011...

output:

2853070317 247143 72

result:

points 1.0 OK L = 72

Test #19:

score: 100
Accepted
time: 17ms
memory: 18484kb

input:

110111100111100111001111101001110111000000101001011001101111010110000010000100000011111000000111011110010010100111000000001110001001100001000111101010010100101111011011100100001000100111001011110001010010111101001110111101000010010010010010011111001111110111100001001100110100111100000100100101001100...

output:

1170245885 93479 70

result:

points 1.0 OK L = 70

Test #20:

score: 100
Accepted
time: 23ms
memory: 25484kb

input:

010100100000001101011100100011100011001010011011011001011100000110000111100001110100011101011000000110111010101101000100010110100010010110001110101111110111000000001100100010100100111000000110100000001111001100111011111011110010000100100000110101111111010111011110100111011101001110100100111100111110...

output:

1138672942 140644 70

result:

points 1.0 OK L = 70