oj.uz

Submission #770925

# Submission time Handle Problem Language Result Execution time Memory
770925 2023-07-02T07:01:55 Z rxlfd314 Data Transfer (IOI19_transfer) C++17
60 / 100
 3000 ms 2488 KB 
#include "transfer.h"
#include <bits/stdc++.h>
using namespace std;

void yeet(int n, vector<int> &v, vector<int> &source) {
	for (int j = 0; (1 << j) <= n; j++) {
		v.push_back(0);
		for (int i = 1; i <= n; i++) {
			if (i & 1 << j) {
				v[j] ^= source[i-1];
			}
		}
	}
}

vector<int> get_attachment(vector<int> source) {
	int N = source.size();
	vector<int> ret;
	yeet(N, ret, source);
	ret.push_back(0);
	for (int i = 0; i < N; i++) {
		ret.back() ^= source[i];
	}
	return ret;
}

vector<int> retrieve(vector<int> data) {
	int N = data.size() < 255 ? 63 : 255;
	int M = data.size();
	vector<int> test;
	yeet(N, test, data);
	if (test == vector<int>(data.begin()+N, data.begin()+M-1)) {
		return vector<int>(data.begin(), data.begin()+N);
	}
	bool p = 0;
	for (int i = 0; i < N; i++) {
		p ^= data[i];
	}
	if (p ^ data[M-1]) {
		for (int i = 0; i < N; i++) {
			test.clear();
			data[i] ^= 1;
			yeet(N, test, data);
			if (test == vector<int>(data.begin()+N, data.begin()+M-1)) {
				return vector<int>(data.begin(), data.begin()+N);
			}
			data[i] ^= 1;
		}
	}
	return vector<int>(data.begin(), data.begin()+N);
}

Subtask #1
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 652 KB Output is correct
2 Correct 66 ms 656 KB Output is correct
3 Correct 64 ms 648 KB Output is correct
4 Correct 66 ms 644 KB Output is correct
5 Correct 64 ms 644 KB Output is correct
6 Correct 65 ms 740 KB Output is correct
7 Correct 65 ms 644 KB Output is correct
8 Correct 66 ms 652 KB Output is correct
9 Correct 64 ms 740 KB Output is correct
10 Correct 77 ms 736 KB Output is correct
11 Correct 74 ms 688 KB Output is correct
12 Correct 65 ms 644 KB Output is correct
13 Correct 67 ms 652 KB Output is correct
14 Correct 66 ms 644 KB Output is correct
15 Correct 65 ms 652 KB Output is correct
16 Correct 69 ms 736 KB Output is correct
17 Correct 68 ms 652 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 2488 KB Time limit exceeded
2 Halted 0 ms 0 KB -