oj.uz

Submission #434595

# Submission time Handle Problem Language Result Execution time Memory
434595 2021-06-21T12:37:35 Z egekabas Data Transfer (IOI19_transfer) C++14
80 / 100
 538 ms 2480 KB 
#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)
				ret[j] ^= source[i];
		ret[k-1] ^= source[i];
	}
	int val = 0;
	for(auto u : ret)
		val ^= u;
	ret.pb(val);
	return ret;
}

std::vector<int> retrieve(std::vector<int> data) {
	int n, k;
	if(data.size() <= 255){
		n = 63, k = 7;
	}
	else{
		n = 255, k = 9;
	}
	int safety = data.back();
	data.pop_back();

	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) > 0][j] ^= ori[i];

	safety ^= tot;
	for(auto u : vals[1])
		safety ^= u;
	if(safety)
		return ori;

	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 = 0;
	for(int i = 0; i < (k-1); ++i)
		if(cur[1][i] != vals[1][i])
			falidx += (1<<i);
	
	ori[falidx] ^= 1;
	return ori;
}

Subtask #1
48.0 / 60.0

# Verdict Execution time Memory Grader output
1 Partially correct 9 ms 628 KB Partially correct
2 Partially correct 11 ms 704 KB Partially correct
3 Partially correct 9 ms 788 KB Partially correct
4 Partially correct 9 ms 624 KB Partially correct
5 Partially correct 9 ms 628 KB Partially correct
6 Partially correct 11 ms 620 KB Partially correct
7 Partially correct 9 ms 700 KB Partially correct
8 Partially correct 9 ms 620 KB Partially correct
9 Partially correct 9 ms 712 KB Partially correct
10 Partially correct 9 ms 620 KB Partially correct
11 Partially correct 11 ms 632 KB Partially correct
12 Partially correct 11 ms 620 KB Partially correct
13 Partially correct 9 ms 704 KB Partially correct
14 Partially correct 9 ms 620 KB Partially correct
15 Partially correct 9 ms 620 KB Partially correct
16 Partially correct 9 ms 704 KB Partially correct
17 Partially correct 9 ms 620 KB Partially correct

Subtask #2
32.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 502 ms 2472 KB Partially correct
2 Partially correct 538 ms 2468 KB Partially correct
3 Partially correct 504 ms 2464 KB Partially correct
4 Partially correct 503 ms 2476 KB Partially correct
5 Partially correct 515 ms 2464 KB Partially correct
6 Partially correct 449 ms 2464 KB Partially correct
7 Partially correct 497 ms 2428 KB Partially correct
8 Partially correct 477 ms 2476 KB Partially correct
9 Partially correct 465 ms 2448 KB Partially correct
10 Partially correct 466 ms 2464 KB Partially correct
11 Partially correct 468 ms 2464 KB Partially correct
12 Partially correct 474 ms 2464 KB Partially correct
13 Partially correct 417 ms 2452 KB Partially correct
14 Partially correct 496 ms 2464 KB Partially correct
15 Partially correct 502 ms 2460 KB Partially correct
16 Partially correct 525 ms 2464 KB Partially correct
17 Partially correct 490 ms 2464 KB Partially correct
18 Partially correct 491 ms 2464 KB Partially correct
19 Partially correct 512 ms 2480 KB Partially correct