oj.uz

Submission #719704

# Submission time Handle Problem Language Result Execution time Memory
719704 2023-04-06T13:58:24 Z thimote75 Data Transfer (IOI19_transfer) C++14
100 / 100
 208 ms 2504 KB 
#include "transfer.h"

#include <bits/stdc++.h>

using namespace std;

#define idata vector<int>

pair<idata, int> make_xor_array (idata source) {
	idata res;
	int sxor = 0;

	for (int h = 0; (1 << h) <= source.size(); h ++) {
		int s   = 1 << h;
		int uxor = 0;
		for (int u = 0; u < source.size(); u ++)
			if ((u & s) == 0)
				uxor ^= source[u];
			
		res.push_back(uxor);
		sxor ^= uxor;
	}

	return { res, sxor };
}
idata get_attachment(idata source) {
	auto v = make_xor_array(source);
	idata res = v.first;
	res.push_back(v.second);

	return res;
}

idata retrieve(idata data) {
	idata source;
	idata xor_array;
	idata expected_xor_array;

	int sxor = data[data.size() - 1];
	int size = (1 << (int) floor(log2(data.size()))) - 1;

	source.resize(size);
	for (int i = 0; i < size; i ++)
		source[i] = data[i];
	int sexor = 0;
	for (int j = size; j + 1 < data.size(); j ++) {
		xor_array.push_back(data[j]);
		sexor ^= data[j];
	}

	if (sexor != sxor) return source;

	expected_xor_array = make_xor_array(source).first;

	int pos = 0;
	for (int h = 0; h < xor_array.size(); h ++)
		if (xor_array[h] == expected_xor_array[h])
			pos |= 1 << h;

	source[pos] = 1 - source[pos];
	return source;
}

Compilation message

transfer.cpp: In function 'std::pair<std::vector<int>, int> make_xor_array(std::vector<int>)':
transfer.cpp:13:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int h = 0; (1 << h) <= source.size(); h ++) {
      |                  ~~~~~~~~~^~~~~~~~~~~~~~~~
transfer.cpp:16:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for (int u = 0; u < source.size(); u ++)
      |                   ~~^~~~~~~~~~~~~~~
transfer.cpp: In function 'std::vector<int> retrieve(std::vector<int>)':
transfer.cpp:46:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int j = size; j + 1 < data.size(); j ++) {
      |                     ~~~~~~^~~~~~~~~~~~~
transfer.cpp:56:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for (int h = 0; h < xor_array.size(); h ++)
      |                  ~~^~~~~~~~~~~~~~~~~~

Subtask #1
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 644 KB Output is correct
2 Correct 6 ms 736 KB Output is correct
3 Correct 8 ms 656 KB Output is correct
4 Correct 6 ms 652 KB Output is correct
5 Correct 8 ms 824 KB Output is correct
6 Correct 6 ms 652 KB Output is correct
7 Correct 6 ms 728 KB Output is correct
8 Correct 7 ms 740 KB Output is correct
9 Correct 6 ms 740 KB Output is correct
10 Correct 6 ms 652 KB Output is correct
11 Correct 6 ms 644 KB Output is correct
12 Correct 6 ms 652 KB Output is correct
13 Correct 6 ms 732 KB Output is correct
14 Correct 5 ms 644 KB Output is correct
15 Correct 6 ms 732 KB Output is correct
16 Correct 6 ms 644 KB Output is correct
17 Correct 6 ms 652 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 2488 KB Output is correct
2 Correct 183 ms 2488 KB Output is correct
3 Correct 208 ms 2504 KB Output is correct
4 Correct 177 ms 2488 KB Output is correct
5 Correct 178 ms 2500 KB Output is correct
6 Correct 193 ms 2424 KB Output is correct
7 Correct 196 ms 2500 KB Output is correct
8 Correct 178 ms 2488 KB Output is correct
9 Correct 190 ms 2488 KB Output is correct
10 Correct 175 ms 2460 KB Output is correct
11 Correct 183 ms 2500 KB Output is correct
12 Correct 193 ms 2464 KB Output is correct
13 Correct 190 ms 2488 KB Output is correct
14 Correct 187 ms 2492 KB Output is correct
15 Correct 180 ms 2488 KB Output is correct
16 Correct 173 ms 2432 KB Output is correct
17 Correct 184 ms 2476 KB Output is correct
18 Correct 173 ms 2460 KB Output is correct
19 Correct 174 ms 2456 KB Output is correct