제출 #1199207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199207		Nelt	Message (IOI24_message)	C++20	100 / 100	400 ms	860 KiB

message

#include"message.h"
#include<bits/stdc++.h>
using namespace std;
void send_message(vector<bool> M,vector<bool> C){
	for (int i=0;i<31;++i) C[i]=!C[i];
//	for (int i=0;i<31;++i) cout<<C[i];cout<<endl;
	M.emplace_back(1);
	while(M.size()<66*16) M.emplace_back(0);
	int pos_M=0,cnt=0,bad=0;
	vector<bool> A(31);
	vector<int> vis(31),fa(31,-1),stk;
	for (int i=0;i<30;++i){
		if (stk.empty()){stk.push_back(i);continue;}
		else{
			A[stk.back()]=C[i];
			bad+=C[stk.back()];
			fa[i]=stk.back();
			for (int j=0;j<31;++j) if (C[j]&&(j!=stk.back())) A[j]=M[pos_M++];
			auto vec=send_packet(A);
			++cnt;
			if (vec[stk.back()]==0){
				stk.pop_back();
			}
			else stk.emplace_back(i);
		}
	}
	int lst=30;
	if (stk.size()) lst=stk.back();
	vis[lst]=vis[30]=1;
//	for (auto x:stk) cout<<x<<' ';cout<<endl;
	for (++cnt;cnt<=66;++cnt){
		int p=-1;
		for (int i=0;i<30;++i) if (!vis[i]){p=i;break;}
//		cout<<"try "<<p<<endl;
		if (p!=-1) A[lst]=C[p],++bad;
		for (int i=0;i<31;++i) if (C[i]&&(i!=lst||p==-1)) A[i]=M[pos_M++];
		send_packet(A);
		if (p==-1) continue;
		vis[p]=1;
		for (int i=p+1;i<31;++i) if (fa[i]!=-1&&C[fa[i]]&&vis[fa[i]]) vis[i]=1;
	}
	assert(pos_M>=1026);
}
vector<bool> receive_message(vector<vector<bool> > R){
	vector<bool> ans;
	vector<int> ok[66],vis(31),qry(31),C(31),stk,fa(31,-1);
	for (int i=0;i<66;++i) ok[i].resize(31);
	int L=0,bad=0;
	for (int i=0;i<30;++i){
		if (stk.empty()){stk.push_back(i);continue;}
		else{
			int x=stk.back();fa[i]=x;
			int k=qry[i]=R[L][x];ok[L++][x]=1;++bad;
			if (k) stk.emplace_back(i);
			else{
				stk.pop_back();
			}
		}
	}
	int lst=30;
	if (stk.size()) lst=stk.back();
	C[lst]=vis[lst]=1;
//	for (auto x:stk) cout<<x<<' ';cout<<endl;
//	for (int i=0;i<30;++i) cout<<fa[i]<<' ';cout<<endl;
	for (;L<66;++L){
		int p=-1;
		for (int i=0;i<30;++i) if (!vis[i]){p=i;break;}
		if (p==-1) break;
//		cout<<"try "<<p<<endl;
		int k=R[L][lst];ok[L][lst]=1;++bad;
		C[p]=k;vis[p]=1;
		for (int i=p+1;i<31;++i) if (vis[i]==0&&fa[i]!=-1&&C[fa[i]]){
			vis[i]=1;C[i]=qry[i];
		}
	}
	if (vis[30]==0){
		C[30]=16;
		for (int i=0;i<30;++i) C[30]-=C[i];
	}
	for (int i=0;i<66;++i) for (int j=0;j<31;++j) if (ok[i][j]==0&&C[j]) ans.emplace_back(R[i][j]);
//	for (int i=0;i<31;++i) cout<<C[i];cout<<endl;
	assert(ans.size()>=1026);
	while(ans.back()==0) ans.pop_back();ans.pop_back();
	return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 90 / 90