Submission #432951

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
432951	2021-06-18T15:33:17 Z	jeroenodb	Data Transfer (IOI19_transfer)	C++14	100 / 100	223 ms	2508 KB

transfer

#ifndef GRADER
#include "transfer.h"
#endif
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
vi get_attachment(vi source) {
	auto n = source.size();
	vi output;
	int last=0;
	for(int i=0;(1<<i)<n;++i) {
		output.push_back(0);
		for(int j=0;j<n;++j) {
			if((j&(1<<i))==0)
				output.back()^=source[j];
		}
		last^=output.back();
	}
	output.push_back(last);
	return output;
}

std::vector<int> retrieve(vi data) {
	int k=__lg(data.size());
	int n = (1<<k) -1;
	vi extra(data.begin()+n,data.end());
	data.erase(data.begin()+n,data.end());
	int check=0;
	for(int i: extra) check^=i;
	if(check) return data;
	extra.pop_back();
	int wrong = 0;
	for(int i=0;(1<<i) < n;++i) {
		check=extra[i];
		for(int j=0;j<n;++j) {
			if((j&(1<<i))==0)
				check^=data[j];
		}
		if(!check) wrong+=(1<<i);
	}
	if(wrong<data.size()) {
		data[wrong]^=1;
	}
	return data;

}

Compilation message

transfer.cpp: In function 'vi get_attachment(vi)':
transfer.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   18 |  for(int i=0;(1<<i)<n;++i) {
      |              ~~~~~~^~
transfer.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   20 |   for(int j=0;j<n;++j) {
      |               ~^~
transfer.cpp: In function 'std::vector<int> retrieve(vi)':
transfer.cpp:48:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  if(wrong<data.size()) {
      |     ~~~~~^~~~~~~~~~~~

Subtask #1

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	620 KB	Output is correct
2	Correct	6 ms	652 KB	Output is correct
3	Correct	5 ms	628 KB	Output is correct
4	Correct	7 ms	620 KB	Output is correct
5	Correct	6 ms	616 KB	Output is correct
6	Correct	8 ms	620 KB	Output is correct
7	Correct	5 ms	700 KB	Output is correct
8	Correct	6 ms	784 KB	Output is correct
9	Correct	5 ms	632 KB	Output is correct
10	Correct	6 ms	712 KB	Output is correct
11	Correct	5 ms	600 KB	Output is correct
12	Correct	6 ms	624 KB	Output is correct
13	Correct	6 ms	620 KB	Output is correct
14	Correct	5 ms	712 KB	Output is correct
15	Correct	5 ms	620 KB	Output is correct
16	Correct	5 ms	620 KB	Output is correct
17	Correct	5 ms	620 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	223 ms	2416 KB	Output is correct
2	Correct	214 ms	2464 KB	Output is correct
3	Correct	214 ms	2464 KB	Output is correct
4	Correct	215 ms	2396 KB	Output is correct
5	Correct	221 ms	2476 KB	Output is correct
6	Correct	212 ms	2464 KB	Output is correct
7	Correct	216 ms	2460 KB	Output is correct
8	Correct	211 ms	2464 KB	Output is correct
9	Correct	217 ms	2464 KB	Output is correct
10	Correct	217 ms	2464 KB	Output is correct
11	Correct	214 ms	2464 KB	Output is correct
12	Correct	210 ms	2468 KB	Output is correct
13	Correct	217 ms	2472 KB	Output is correct
14	Correct	211 ms	2464 KB	Output is correct
15	Correct	209 ms	2452 KB	Output is correct
16	Correct	210 ms	2508 KB	Output is correct
17	Correct	213 ms	2480 KB	Output is correct
18	Correct	213 ms	2464 KB	Output is correct
19	Correct	211 ms	2464 KB	Output is correct