Submission #434610

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
434610	2021-06-21T13:03:23 Z	egekabas	Data Transfer (IOI19_transfer)	C++14	100 / 100	521 ms	2532 KB

transfer

#include <bits/stdc++.h>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
	
std::vector<int> get_attachment(std::vector<int> source) {
	int n = source.size(), k;
	if(n == 63)
		k = 7;
	else
		k = 9;
	
	vector<int> ret(k);
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < (k-1); ++j)
			if((1<<j)&(i+1))
				ret[j] ^= source[i];
		ret[k-1] ^= source[i];
	}
	return ret;
}
	
std::vector<int> retrieve(std::vector<int> data) {
	int n, k;
	if(data.size() == 70){
		n = 63, k = 7;
	}
	else{
		n = 255, k = 9;
	}
	vector<int> ori(data.begin(), data.begin()+n);
	int tot = data.back();
	
	vector<vector<int>> vals(2, vector<int>(k-1));
	vals[1] = vector<int>(data.begin()+n, data.end()-1);
	for(int i = 0; i < k-1; ++i)
		vals[0][i] = vals[1][i]^tot;
	
	vector<vector<int>> cur(2, vector<int>(k-1));
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < (k-1); ++j)
			cur[((1<<j)&(i+1)) > 0][j] ^= ori[i];
	
	
	int cnt = 0;
	for(int i = 0; i < (k-1); ++i){
		if(cur[0][i] != vals[0][i] && cur[1][i] != vals[1][i]){
			return ori;
		}
		if(cur[0][i] != vals[0][i] || cur[1][i] != vals[1][i])
			++cnt;
	}
	if(cnt == 0)
		return ori;
	if(cnt != k-1)
		return ori;
	
	int falidx = -1;
	for(int i = 0; i < (k-1); ++i)
		if(cur[1][i] != vals[1][i])
			falidx += (1<<i);
	if(falidx >= 0)
		ori[falidx] ^= 1;
	return ori;
}

Subtask #1

60.0 / 60.0

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

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	521 ms	2456 KB	Output is correct
2	Correct	497 ms	2472 KB	Output is correct
3	Correct	484 ms	2456 KB	Output is correct
4	Correct	500 ms	2440 KB	Output is correct
5	Correct	503 ms	2476 KB	Output is correct
6	Correct	506 ms	2460 KB	Output is correct
7	Correct	499 ms	2464 KB	Output is correct
8	Correct	514 ms	2464 KB	Output is correct
9	Correct	511 ms	2460 KB	Output is correct
10	Correct	499 ms	2460 KB	Output is correct
11	Correct	490 ms	2460 KB	Output is correct
12	Correct	504 ms	2460 KB	Output is correct
13	Correct	505 ms	2460 KB	Output is correct
14	Correct	489 ms	2472 KB	Output is correct
15	Correct	508 ms	2460 KB	Output is correct
16	Correct	498 ms	2532 KB	Output is correct
17	Correct	501 ms	2460 KB	Output is correct
18	Correct	509 ms	2464 KB	Output is correct
19	Correct	505 ms	2460 KB	Output is correct