oj.uz

Submission #1099810

# Submission time Handle Problem Language Result Execution time Memory
1099810 2024-10-12T05:22:20 Z model_code Message (IOI24_message) C++17
91.225 / 100
 1072 ms 1056 KB 
// partially_correct/mruxim-4days.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 maxlen = 1024;

const int plen = 31;
const int bm = (1U << 31) - 1;
const int thr = 4*16 + (15 - (maxlen + 15) % 16);

int rnd(int x) { x ^= x << 13, x ^= x >> 17, x ^= x << 5; return x; }

vector<int> calcX(int k, int seed = 747) {
	vector<int> X(k);
	seed = rnd(seed);
	rep(i, k) X[i] = seed & bm, seed = rnd(seed);
	return X;
}

void toggle_encrypt(vector<bool> M, int seed = 777) {
	seed = rnd(seed);
	rep(i, sz(M)) M[i] = ((seed >> 17 & 1) ? !M[i] : M[i]), seed = rnd(seed);
}

vector<bool> pack(int x) {
	vector<bool> res(plen);
	rep(i, plen) res[i] = (bool)(x >> i & 1);
	return res;
}

int unpack(vector<bool> v) {
	int res = 0;
	rep(i, plen) res |= ((int)v[i]) << i;
	return res;
}

int poof(int x, int mask) {
	int res = 0;
	for(; mask; mask &= mask-1, x >>= 1)
		res |= (x & 1) << __builtin_ctz(mask);
	return res;
}

int unpoof(int x, int mask) {
	int res = 0;
	for(int i = 0; mask; mask &= mask-1, i++)
		res |= (x >> __builtin_ctz(mask) & 1) << i;
	return res;
}

void send_message(vector<bool> M, vector<bool> C) {
	rep(i, plen) C[i] = !C[i];
	int n = sz(M), k = max(66, ((n + thr) + 15) / 16);
	vector<int> X = calcX(k);
	toggle_encrypt(M);

	int cmask = unpack(C);
	int id = __builtin_ctz(cmask);

	vector<int> A(k, 0);
	rep(i, plen) A[i] |= (cmask >> i & 1) << id;
	fer(i, plen, thr-4) A[i] |= 1 << id;
	int rem = (k*16-thr) - n;
	rep(i, 4) A[thr-4+i] |= (min(rem, 15) >> i & 1) << id;

	int pos = 0;
	rep(i, k) rep(b, plen) if(pos < n && (cmask >> b & 1) && (i >= thr || b != id))
		A[i] |= ((int)M[pos++]) << b;
	if(rem > 15) A.back() = poof(rem << 5, cmask);

//	vector<int> tmp = calcX(k, 222);
//	rep(i, k) A[i] ^= tmp[i] & ~cmask;
	rep(i, k) send_packet(pack(A[i] ^ X[i]));
}

vector<bool> receive_message(vector<vector<bool>> R) {
	int k = sz(R);
	vector<int> X = calcX(k);
	vector<int> A(k);
	rep(i, k) A[i] = unpack(R[i]) ^ X[i];

	int id = -1, cmask = -1, rem = -1;
	rep(b, plen) {
		int tcmask = 0; rep(i, plen) tcmask |= (A[i] >> b & 1) << i;
		int t = 1; fer(i, plen, thr-4) t &= (A[i] >> b & 1);
		if(__builtin_popcount(tcmask) != 16 || (tcmask >> b & 1) == 0 || t == 0) continue;
		int trem = 0; rep(i, 4) trem |= ((A[thr-4+i] >> b & 1) << i);

		if(id != -1) assert(0); // unlucky!
		id = b, cmask = tcmask, rem = trem;
	}

	if(int tmp = unpoof(A.back(), cmask) >> 5; rem == 15 && tmp != 0) rem = tmp;
	rem = (k*16-thr) - rem;

	vector<bool> M;
	rep(i, k) rep(b, plen) if(rem > 0 && (cmask >> b & 1) && (i >= thr || b != id))
		M.push_back((bool)(A[i] >> b & 1)), rem--;

	toggle_encrypt(M);
	return M;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 916 KB Used 66 days

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 939 ms 828 KB Used 66 days
2 Correct 903 ms 992 KB Used 66 days
3 Correct 946 ms 812 KB Used 66 days
4 Correct 913 ms 800 KB Used 66 days
5 Correct 618 ms 804 KB Used 66 days
6 Correct 505 ms 820 KB Used 66 days
7 Correct 626 ms 932 KB Used 66 days

Subtask #2
81.225 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 916 KB Used 66 days
2 Correct 939 ms 828 KB Used 66 days
3 Correct 903 ms 992 KB Used 66 days
4 Correct 946 ms 812 KB Used 66 days
5 Correct 913 ms 800 KB Used 66 days
6 Correct 618 ms 804 KB Used 66 days
7 Correct 505 ms 820 KB Used 66 days
8 Correct 626 ms 932 KB Used 66 days
9 Partially correct 1072 ms 816 KB Used 68 days
10 Partially correct 985 ms 1004 KB Used 68 days
11 Partially correct 971 ms 816 KB Used 68 days
12 Partially correct 962 ms 820 KB Used 68 days
13 Partially correct 1030 ms 816 KB Used 67 days
14 Partially correct 727 ms 820 KB Used 68 days
15 Partially correct 523 ms 1052 KB Used 68 days
16 Partially correct 680 ms 996 KB Used 68 days
17 Partially correct 673 ms 828 KB Used 68 days
18 Correct 958 ms 1052 KB Used 66 days
19 Correct 900 ms 996 KB Used 66 days
20 Correct 883 ms 816 KB Used 66 days
21 Correct 981 ms 816 KB Used 66 days
22 Correct 899 ms 808 KB Used 66 days
23 Correct 965 ms 824 KB Used 66 days
24 Correct 943 ms 812 KB Used 66 days
25 Correct 918 ms 916 KB Used 66 days
26 Correct 984 ms 816 KB Used 66 days
27 Partially correct 999 ms 820 KB Used 67 days
28 Partially correct 1017 ms 1056 KB Used 68 days