Submission #1244739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244739		allin27x	Message (IOI24_message)	C++20	0 / 100	55 ms	840 KiB

message

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

const int SEED = 1502;

vector<bool> send_packet(vector<bool> A);

void send_message(vector<bool> M, vector<bool> C) {
	mt19937 rng(SEED);
	vector<int> prm(31,0); iota(prm.begin(), prm.end(), 0);
	shuffle(prm.begin(), prm.end(), rng);
	vector<pair<int,int>> ps;
	for (int i=0; i<31; i++) if (!C[i]) ps.push_back({prm[i], i});
	sort(ps.begin(), ps.end());ps.push_back(ps[0]);
	vector<int> A(31,0);
	for (int i=0; i+1<ps.size(); i++) {
		A[ps[i].second] = ps[i+1].first - ps[i].first - 1;
	}
	for (int i=0; i<31; i++){A[i]%=31; A[i] += 31; A[i]%=31;}
	for (int bt=0; bt<3; bt++) {
		vector<bool> pt(31,0);
		for (int i=0; i<31; i++) pt[i] = A[i]>>bt&1;
		send_packet(pt);
	}
	ps.pop_back();
	sort(ps.begin(), ps.end(), [](pair<int,int> a, pair<int,int> b) {return a.second < b.second;});
	int S = M.size();
	vector<bool> sz(31,0);
	for (int bt =0; bt<16; bt++) {
		if ((S>>bt)&1) sz[ps[bt].second] = 1;
	}
	send_packet(sz);
	vector<bool> pt(31,0);
	for (int i=0; i<31; i++) pt[i] = 0;
	for (int i=0; i<S; i+=16){
		for (int i=0; i<31; i++) pt[i] = 0;
		for (int j=i; j<i+16; j++) {
			pt[ps[j-i].second] = M[j];
		}
		send_packet(pt);
	}
}

vector<bool> receive_message(vector<vector<bool>> R) {
	mt19937 rng(SEED);
	vector<int> prm(31,0); iota(prm.begin(), prm.end(), 0);
	shuffle(prm.begin(), prm.end(), rng);

	vector<int> to(31,0); iota(to.begin(), to.end(), 1);
	for (int bt=0; bt<3; bt++) {
		for (int i=0; i<31; i++) {
			if (R[bt][i]) to[prm[i]] += 1<<bt; to[prm[i]] %= 31;
		}
	}
	vector<int> good(31, 0);
	for (int c=0; c<31; c++) {
		vector<int> vis(31, 0);
		vector<int> ds(31, 0);
		vis[c] = 1;
		for (int t_=0; t_<33; t_++) {
			for (int i=0; i<31; i++) {
				if (vis[i] && !vis[to[i]]) {
					vis[to[i]] = 1; ds[to[i]] = ds[i] + 1;
				}
			}
		}
		int g =0 ;
		for (int i=0; i<31; i++) if (to[i] == c && ds[i] == 15) g=1;
		good[c] = g;
	}
	vector<int> ng(31, 0); for (int i=0; i<31; i++) ng[i] = good[prm[i]];
	good = ng;
	vector<bool> M;
	int sz = 0; int bt = 0;
	for (int i=0; i<31; i++) {
		if (good[i]) sz += R[3][i] * (1<<bt), bt++;
	}

	for (int i=4; i<R.size(); i++) {
		for (int j=0; j<31; j++) {
			if (!good[j]) continue;
			M.push_back(R[i][j]);
			if (M.size() == sz) return M;
		}
	}
	return M;
}

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