Submission #601915

#	Time	Username	Problem	Language	Result	Execution time	Memory
601915		CSQ31	Flight to the Ford (BOI22_communication)	C++17	0 / 100	292 ms	212 KiB

communication

#include "communication.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
typedef pair<int,int> pii;
//we want a solution that returns a mask where either flipped or unflipped is correct
void get(vector<int>v){
	if(v.size() <= 1)return;
	vector<int>res,nxt;
	int n = v.size();
	for(int x:v){
		res.pb(send(x));
		res.pb(send(x));
	}
	for(int i=0;i<n;i++){
		if(res[2*i] == res[2*i+1])continue;
		int j = i;
		while(j+1<n && res[2*j+2] != res[2*j+3])j++;
		nxt.pb(res[2*i] != v[i]);
		i=j;
	} 
	//equal segment take the bit value of the left guy
	get(nxt);
}
//cw = 1
//wc = 0
vector<int>solve(int n){
	if(n<=1)return {0};
	vector<int>res,nxt,ans(n,0);
	for(int i=0;i<2*n;i++)res.pb(receive());
	for(int i=0;i<n;i++){
		if(res[2*i] == res[2*i+1])continue;
		int j = i;
		while(j+1<n && res[2*j+2] != res[2*j+3])j++;
		nxt.pb(i/2);
		i=j;
	} 
	if(nxt.empty()){ //all equal
		for(int i=0;i<2*n;i++)ans[i/2] = res[i];
		return ans;
	}
	vector<int>sol = solve(nxt.size());
	int ptr = 0;
	for(int i=0;i<n;i++){
		if(res[2*i] == res[2*i+1]){
			if(ptr == (int)(sol.size()))ptr--;
			ans[i] = res[2*i] ^ sol[ptr];
			continue;
		}
		int j = i;
		while(j+1<n && res[2*j+2] != res[2*j+3])j++;
		for(int k=i;k<=j;k++)ans[k] = res[2*k] ^ sol[ptr];
		ptr++;
		i=j;
	} 
	return ans;

}
void encode(int n, int x) {
	vector<int>v;
	int lim = 0;
	for(int i=30;i>=0;i--){
		if(n&(1<<i)){
			lim = i;
			break;
		}
	}
	for(int i=0;i<=lim;i++)v.pb((x&(1<<i))>0);
	get(v);
}
pair<int, int> decode(int n) {
	pair<int,int>ans = {1,1};
	int lim = 0;
	for(int i=30;i>=0;i--){
		if(n&(1<<i)){
			lim = i;
			break;
		}
	}
	int a = 0;
	int b = 0;
	vector<int>v = solve(lim+1);
	for(int i=0;i<=lim;i++){
		if(v[i])a+=(1<<i);
		else b+=(1<<i);
	}
	if(a>0 && a<=n)ans.fi = a;
	if(b>0 && b<=n)ans.se = b;
	return ans;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85