Submission #1225545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225545		Dan4Life	Message (IOI24_message)	C++20	100 / 100	430 ms	848 KiB

message

#include "message.h"
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)

using ll = long long;
using ar2 = array<int,2>;
using ar3 = array<int,3>;
using vi = vector<int>;
using vll = vector<ll>;
using vb = vector<bool>;

const int mxN = (int)1e5+10;
const int INF = (int)1e9+10;
const ll LINF = (ll)1e18+10;

void send_message(vb M, vb c) {
	reverse(all(M)); M.pb(1); 
	while(sz(M)<1025) M.pb(0);
	int num = 0, cnt[31]{0};
	for(int i = 0; i < 31; i++){
		if(c[i]) continue;
		int j = i;
		while(1){
			j++; j%=31; cnt[i]++;
			if(!c[j]) break;
		}
		num = max(num, cnt[i]);
	}
	int cur = 0;
	for(int i = 0; i < 66; i++){
		vb packet(31,0);
		for(int j = 0; j < 31; j++){
			if(c[j]) continue; cnt[j]--;
			if(cnt[j]>=0) packet[j] = (cnt[j]==0);
			else packet[j] = M[cur++];
		}
		send_packet(packet);
	}
}

vb receive_message(vector<vb> R) {
	vb ans; ans.clear(); vi v;
	int found[31]{0}, nx[31]{0}, good[31]{0}, vis[31]{0};
	for(int i = 0; i < 31; i++) nx[i]=i;
	for(int i = 0; i < sz(R); i++){
		for(int j = 0; j < 31; j++){
			if(R[i][j]) found[j]++;
			if(found[j]==1) nx[j] = (j+i+1)%31, found[j]++;
		}
	}
	for(int i = 0; i < 31; i++){
		fill(vis,vis+31,0);
		int x = i; v.clear();
		while(!vis[x]) v.pb(x), vis[x] = 1, x = nx[x];
		if(sz(v)==16) break;
	}
	fill(found,found+31,0);
	for(auto u : v) good[u] = 1;
	for(int i = 0; i < sz(R); i++){
		for(int j = 0; j < 31; j++){
			if(!good[j]) continue;
			if(R[i][j] or found[j]) found[j]++;
			if(found[j]>1) ans.pb(R[i][j]);
		}
	}
	while(!ans.back()) ans.pop_back();
	ans.pop_back(); reverse(all(ans));
	return ans;
}

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