Submission #732006

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
732006	2023-04-28T08:31:25 Z	sentheta	Data Transfer (IOI19_transfer)	C++17	100 / 100	210 ms	2500 KB

transfer

#include "transfer.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;


V<int> get_attachment(V<int> a) {
	V<int> b;
	int n = a.size();
	
	a.push_back(0);
	rep(i,0,n){
		a[n] ^= a[i];
	}
	b.push_back(a[n]);

	for(int k=1; k<n; k<<=1){
		int x = 0;
		rep(i,0,n+1) if(i&k){
			x ^= a[i];
		}
		// cout << k _ x << nl;
		b.push_back(x);
	}
	return b;
}

V<int> retrieve(V<int> a) {
	int n;
	if((int)a.size() < 200) n = 63;
	else n = 255;

	{
		int x = 0;
		rep(i,0,n) x ^= a[i];
		if(x==a[n]){
			return V<int>(a.begin(),a.begin()+n);
		}
	}

	int idx = 0;
	for(int k=1,j=n+1; k<n; k<<=1,j++){
		int x = 0;
		rep(i,0,n+1) if(i&k){
			x ^= a[i];
		}
		// cout << k _ x << nl;
		if(x!=a[j]){
			idx ^= k;
		}
	}
	a[idx] ^= 1;

	return V<int>(a.begin(),a.begin()+n);
}

Subtask #1

60.0 / 60.0

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

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	183 ms	2488 KB	Output is correct
2	Correct	172 ms	2492 KB	Output is correct
3	Correct	181 ms	2488 KB	Output is correct
4	Correct	177 ms	2488 KB	Output is correct
5	Correct	168 ms	2488 KB	Output is correct
6	Correct	174 ms	2496 KB	Output is correct
7	Correct	176 ms	2432 KB	Output is correct
8	Correct	188 ms	2496 KB	Output is correct
9	Correct	176 ms	2500 KB	Output is correct
10	Correct	173 ms	2492 KB	Output is correct
11	Correct	210 ms	2488 KB	Output is correct
12	Correct	185 ms	2488 KB	Output is correct
13	Correct	191 ms	2500 KB	Output is correct
14	Correct	190 ms	2492 KB	Output is correct
15	Correct	175 ms	2488 KB	Output is correct
16	Correct	175 ms	2456 KB	Output is correct
17	Correct	177 ms	2492 KB	Output is correct
18	Correct	169 ms	2496 KB	Output is correct
19	Correct	168 ms	2488 KB	Output is correct