oj.uz

Submission #1099788

# Submission time Handle Problem Language Result Execution time Memory
1099788 2024-10-12T05:17:59 Z model_code Message (IOI24_message) C++17
100 / 100
 959 ms 1076 KB 
// model_solution/mruxim-extra32.cpp

#include "message.h"
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0, i##__n = (int)(n); i < i##__n; ++i)
#define fer(i, a, b) for(int i = (int)(a), i##__b = (int)(b); i < i##__b; ++i)
#define rof(i, b, a) for(int i = (int)(b), i##__a = (int)(a); i-- > i##__a; )
#define sz(x) (int((x).size()))
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define X first
#define Y second
//#define endl '\n'

template<class P, class Q> inline void smin(P &a, Q b) { if (b < a) a = b; }
template<class P, class Q> inline void smax(P &a, Q b) { if (a < b) a = b; }

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;

///////////////////////////////////////////////////////////////////////////

const int plen = 31;
const int maxe = 16;

void send_message(vector<bool> M, vector<bool> C) {
	vector<vector<bool>> A(max(maxe, (sz(M) + 15) / 16 + 2), vector<bool>(plen, false));

	vector<int> nxt(plen, 1);
	rep(b, plen) if(!C[b])
		while(C[(b + nxt[b]) % plen]) nxt[b]++;
	rep(b, plen) if(!C[b]) A[nxt[b] - 1][b] = true;
	
	int pos = 0;
	rep(i, sz(A)) rep(b, plen) if(!C[b] && nxt[b] <= i)
		A[i][b] = (pos < sz(M) ? M[pos] : (pos == sz(M) ? true : false)), pos++;

	rep(i, sz(A)) send_packet(A[i]);
}

vector<bool> receive_message(vector<vector<bool>> A) {
	vector<int> nxt(plen, 0);
	rep(b, plen) rep(i, maxe) if(A[i][b]) { nxt[b] = i + 1; break; }
	vector<bool> C(plen, true);
	rep(b, plen) {
		int cnt = 0;
		vector<bool> mark(plen, false);
		for(int v = (b + nxt[b]) % plen; !mark[v]; v = (v + nxt[v]) % plen) mark[v] = true, cnt++;
		if(cnt == 16) rep(v, plen) C[v] = !mark[v];
	}

	vector<bool> M;
	rep(i, sz(A)) rep(b, plen) if(!C[b] && nxt[b] <= i)
		M.pb(A[i][b]);

	while(!M.back()) M.pop_back();
	M.pop_back();

	return M;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 664 KB Used 16 days

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 808 KB Used 16 days
2 Correct 232 ms 804 KB Used 16 days
3 Correct 254 ms 812 KB Used 16 days
4 Correct 252 ms 808 KB Used 16 days
5 Correct 164 ms 804 KB Used 16 days
6 Correct 122 ms 796 KB Used 16 days
7 Correct 157 ms 804 KB Used 16 days

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 664 KB Used 16 days
2 Correct 239 ms 808 KB Used 16 days
3 Correct 232 ms 804 KB Used 16 days
4 Correct 254 ms 812 KB Used 16 days
5 Correct 252 ms 808 KB Used 16 days
6 Correct 164 ms 804 KB Used 16 days
7 Correct 122 ms 796 KB Used 16 days
8 Correct 157 ms 804 KB Used 16 days
9 Correct 862 ms 820 KB Used 66 days
10 Correct 466 ms 812 KB Used 66 days
11 Correct 942 ms 820 KB Used 66 days
12 Correct 922 ms 824 KB Used 66 days
13 Correct 959 ms 1060 KB Used 65 days
14 Correct 670 ms 824 KB Used 66 days
15 Correct 448 ms 996 KB Used 66 days
16 Correct 670 ms 828 KB Used 66 days
17 Correct 639 ms 820 KB Used 66 days
18 Correct 269 ms 984 KB Used 16 days
19 Correct 247 ms 812 KB Used 16 days
20 Correct 294 ms 824 KB Used 21 days
21 Correct 361 ms 824 KB Used 27 days
22 Correct 473 ms 816 KB Used 34 days
23 Correct 497 ms 824 KB Used 40 days
24 Correct 658 ms 800 KB Used 46 days
25 Correct 619 ms 824 KB Used 52 days
26 Correct 776 ms 812 KB Used 59 days
27 Correct 889 ms 804 KB Used 65 days
28 Correct 852 ms 1076 KB Used 66 days