QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#819196#9237. Messagesyxsyx0 1ms4916kbC++207.2kb2024-12-18 13:56:592024-12-18 13:57:01

Judging History

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

  • [2024-12-18 13:57:01]
  • 评测
  • 测评结果：0
  • 用时：1ms
  • 内存：4916kb
查看
  • [2024-12-18 13:56:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
vector <bool> send_packet(vector <bool> A);
namespace sol1
{
const int N=2005,M=65536;
const int LUCK=19260817;
int chan(vector <bool> a)
{
	int res=0;
	for(int i=0;i<31;i++) res+=(int)a[i]<<i;
	return res;
}
int send(int x)
{
	vector <bool> A;
	A.resize(31);
	for(int i=0;i<31;i++) A[i]=(x>>i)&1;
	return chan(send_packet(A));
}
int lowbit(int x){return x&-x;}
int popcount(int x)
{
	int cnt=0;
	while(x) x-=lowbit(x),cnt++;
	return cnt;
}
bool getbit(int x)
{
	return popcount(x)>15;
}
int sent[N];
//op=0:0-14
//op=1:16-30
int rev[N];
int tmp[N];
int noww[M];
long long hsh[M];
void upd(int len,int op)
{
	if(op==0) tmp[len]=sent[len]&32767;
	if(op==1) tmp[len]=(sent[len]&2147450880)>>16;
//	for(int j=0;j<15;j++) printf("%d",(bool)(tmp[len]&(1<<j)));printf("\n");
	for(int i=0;i<(1<<15);i++)
	{
		if(noww[i]>15&&hsh[i]!=i) continue;
		if(popcount(i)>7) continue;
		for(int j=0;j<15;j++)
		{
			if(i&(1<<j)) continue;
			bool v=tmp[len]&(1<<j);
//			if(i==1) printf("%d %d %d %d\n",j,noww[i],v,v^rev[noww[i]]);
			hsh[i]+=(v^rev[noww[i]])<<noww[i];
			noww[i]++;
		}
	}
}
int check(int len,int op)
{
	int res=-2;
	for(int i=0;i<(1<<15)-1;i++)
	{
		if(popcount(i)>7) continue;
		bool chk=hsh[i]==i;
		if(noww[i]<15) chk=1;
//		if(chk) printf("%d ok %lld %d\n",i,hsh[i],noww[i]);
		if(chk&&res!=-2) return -1;
		if(chk) res=i;
	}
	return res;
}
bool chk[N],tchk[N];
int len,S[N],now;
void send_message(vector <bool> M,vector <bool> C)
{
	len=M.size();now=0;
	memset(noww,0,sizeof(noww));
	memset(hsh,0,sizeof(hsh));
	for(int i=1;i<=10;i++) S[i]=(bool)((len-1)&(1<<(i-1)));
	for(int i=1;i<=len;i++) S[i+10]=M[i-1];
	len+=10;
	for(int i=1;i<=len;i++) printf("%d ",S[i]);printf("\n");
	for(int i=0;i<31;i++) chk[i]=C[i];
	mt19937 Rnd(LUCK);
	for(int i=0;i<=1000;i++) rev[i]=Rnd()&1;
//	for(int i=0;i<=100;i++) printf("%d",rev[i]);printf("\n");
//	for(int i=0;i<=100;i++) printf("%d",chk[i]);printf("\n");
	int op=0;
	int cnt=0;
	for(int i=0;i<15;i++) if(!chk[i]) cnt++;
	if(cnt>=8){op=0,send(0);for(int i=0;i<15;i++) tchk[i]=chk[i];}
	else{op=1,send(2147483647);for(int i=0;i<15;i++) tchk[i]=chk[16+i];}
	
//	printf("%d:\n",op);
	
	cnt=0;
	int w=0;
	while(check(cnt,op)==-1)
	{
		int val=0;
		if(op==0)
		{
			for(int i=0;i<15;i++)
			{
				if(chk[i]) continue;
				val+=(tchk[w]^rev[w])<<i;
				w++;
			}
			for(int i=16;i<31;i++) if(!chk[i]) val+=S[++now]<<i;
		}
		if(op==1)
		{
			for(int i=16;i<31;i++)
			{
				if(chk[i]) continue;
				val+=(tchk[w]^rev[w])<<i;
				w++;
			}
			for(int i=0;i<15;i++) if(!chk[i]) val+=S[++now]<<i;
		}
		sent[++cnt]=send(val);
		upd(cnt,op);
	}
	int val=0;
	if(op==0)
	{
		int tmp=16;
		for(int i=0;i<15;i++)
		{
			if(chk[i]) continue;
			val+=chk[tmp++]<<i;
		}
		for(int i=16;i<31;i++) if(!chk[i]) val+=S[++now]<<i;
		sent[++cnt]=send(val);
		val=0;
		for(int i=0;i<15;i++)
		{
			if(chk[i]) continue;
			val+=chk[tmp++]<<i;
		}
		for(int i=16;i<31;i++) if(!chk[i]) val+=S[++now]<<i;
		sent[++cnt]=send(val);
	}
	if(op==1)
	{
		int tmp=0;
		for(int i=16;i<31;i++)
		{
			if(chk[i]) continue;
			val+=chk[tmp++]<<i;
		}
		for(int i=0;i<15;i++) if(!chk[i]) val+=S[++now]<<i;
		sent[++cnt]=send(val);
		val=0;
		for(int i=16;i<31;i++)
		{
			if(chk[i]) continue;
			val+=chk[tmp++]<<i;
		}
		for(int i=0;i<15;i++) if(!chk[i]) val+=S[++now]<<i;
		sent[++cnt]=send(val);
	}
	while(now<len)
	{
		int val=0;
		for(int i=0;i<31;i++) if(!chk[i]) val+=S[++now]<<i;
		sent[++cnt]=send(val);
	}
//	for(int i=1;i<=cnt;i++){
//		for(int j=0;j<31;j++) printf((j==14||j==15)?"%d ":"%d",(bool)(sent[i]&(1<<j)));printf("\n");}
//	printf("%d\n",check(cnt,op));
}
}
void send_message(vector <bool> M,vector <bool> C)
{
	sol1::send_message(M,C);
}
namespace sol2
{
const int N=2005,M=65536;
const int LUCK=19260817;
int chan(vector <bool> a)
{
	int res=0;
	for(int i=0;i<31;i++) res+=(int)a[i]<<i;
	return res;
}
int send(int x)
{
	vector <bool> A;
	A.resize(31);
	for(int i=0;i<31;i++) A[i]=(x>>i)&1;
	return chan(send_packet(A));
}
int lowbit(int x){return x&-x;}
int popcount(int x)
{
	int cnt=0;
	while(x) x-=lowbit(x),cnt++;
	return cnt;
}
bool getbit(int x)
{
	return popcount(x)>15;
}
int sent[N];
//op=0:0-14
//op=1:16-30
int rev[N];
int tmp[N];
int noww[M];
long long hsh[M];
void upd(int len,int op)
{
	if(op==0) tmp[len]=sent[len]&32767;
	if(op==1) tmp[len]=(sent[len]&2147450880)>>16;
//	for(int j=0;j<15;j++) printf("%d",(bool)(tmp[len]&(1<<j)));printf("\n");
	for(int i=0;i<(1<<15);i++)
	{
		if(noww[i]>15&&hsh[i]!=i) continue;
		if(popcount(i)>7) continue;
		for(int j=0;j<15;j++)
		{
			if(i&(1<<j)) continue;
			bool v=tmp[len]&(1<<j);
//			if(i==1) printf("%d %d %d %d\n",j,noww[i],v,v^rev[noww[i]]);
			hsh[i]+=(v^rev[noww[i]])<<noww[i];
			noww[i]++;
		}
	}
}
int check(int len,int op)
{
	int res=-2;
	for(int i=0;i<(1<<15)-1;i++)
	{
		if(popcount(i)>7) continue;
		bool chk=hsh[i]==i;
		if(noww[i]<15) chk=1;
//		if(chk) printf("%d ok %lld %d\n",i,hsh[i],noww[i]);
		if(chk&&res!=-2) return -1;
		if(chk) res=i;
	}
	return res;
}
bool chk[N],tchk[N];
int len,S[N],now;
bool res[N];
vector <bool> receive_message(vector <vector <bool> > R)
{
	int tmp=0;
	int now=0;
	int cnt=R.size()-1;
	for(int i=0;i<=cnt;i++) sent[i]=chan(R[i]);
//	for(int i=1;i<=cnt;i++){
//		for(int j=0;j<31;j++) printf((j==14||j==15)?"%d ":"%d",(bool)(sent[i]&(1<<j)));printf("\n");}
	mt19937 Rnd(LUCK);
	for(int i=0;i<=1000;i++) rev[i]=Rnd()&1;
//	for(int i=0;i<=100;i++) printf("%d",rev[i]);printf("\n");
	int op=getbit(sent[0]);
//	printf("%d:\n",op);
	memset(chk,0,sizeof(chk));
	memset(noww,0,sizeof(noww));
	memset(hsh,0,sizeof(hsh));
	for(int i=1;i<=cnt;i++)
	{
		upd(i,op);
		if(check(i,op)==-1) continue;
		int now=check(i,op);
//		printf("%d:%d\n",i,now);
		if(op==0)
		{
			for(int j=0;j<15;j++) chk[j]=now&(1<<j);
			int tmp=16;
			for(int j=0;j<15;j++) if(!chk[j]&&tmp<31) chk[tmp++]=sent[i+1]&(1<<j);
			for(int j=0;j<15;j++) if(!chk[j]&&tmp<31) chk[tmp++]=sent[i+2]&(1<<j);
		}
		if(op==1)
		{
			for(int j=0;j<15;j++) chk[16+j]=now&(1<<j);
			int tmp=0;
//			printf("%d %d\n",sent[i+1],sent[i+2]);
			for(int j=16;j<31;j++) if(!chk[j]&&tmp<15) chk[tmp++]=sent[i+1]&(1<<j);
			for(int j=16;j<31;j++) if(!chk[j]&&tmp<15) chk[tmp++]=sent[i+2]&(1<<j);
		}
		tmp=i+3;
		break;
	}
	int cnt1=0;
	for(int i=0;i<31;i++) cnt1+=chk[i];
	chk[15]=cnt1<15;
//	for(int i=0;i<31;i++) printf("%d ",chk[i]);printf("\n");
	for(int i=1;i<tmp;i++)
	{
		if(op==0) for(int j=16;j<31;j++) if(!chk[j]) S[++now]=(bool)(sent[i]&(1<<j));
		if(op==1) for(int j=0;j<15;j++) if(!chk[j]) S[++now]=(bool)(sent[i]&(1<<j));
	}
	for(int i=tmp;i<=cnt;i++)
		for(int j=0;j<31;j++)
			if(!chk[j]) S[++now]=(bool)(sent[i]&(1<<j));
//	for(int i=1;i<=now;i++) printf("%d ",S[i]);printf("\n");
	int lens=1;
	for(int i=1;i<=10;i++) lens+=S[i]<<(i-1);
//	printf("%d\n",lens);
	vector <bool> ret;
	for(int i=11;i<=10+lens;i++) ret.push_back(S[i]);
	return ret;
}
}
vector <bool> receive_message(vector <vector <bool> > R)
{
	return sol2::receive_message(R);
}
/*
1
15
0 1 0 1 0 1 0 0 0 1 1 1 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0
*/
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4492kb

Manager to Aisha

Aisha to Manager

1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 1 0

Manager to Basma

Basma to Manager

Manager to Checker

0
ing with message 'Possible tampering with sol2mgr[0]'
Sending secret with code DIE to mgr2sol[0]
Sending secret with code DIE to mgr2sol[1]
Quitting with result code 11

result:

wrong output format Extra information in the output file

Subtask #2:

score: 0
Wrong Answer

Test #8:

score: 0
Wrong Answer
time: 1ms
memory: 4916kb

Manager to Aisha

Aisha to Manager

1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 1 0 0 0 1 1 0 1 1 1 1 0 0 1 0 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 0 0 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 0 1 1 1 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 1 0 1 1 1 1 0 ...

Manager to Basma

Basma to Manager

Manager to Checker

0
ing with message 'Possible tampering with sol2mgr[0]'
Sending secret with code DIE to mgr2sol[0]
Sending secret with code DIE to mgr2sol[1]
Quitting with result code 11

result:

wrong output format Extra information in the output file
English 繁體中文 简体中文

Server Time: 2025-02-01 16:41:00 | OpenSource Project