Submission #145461

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
145461	2019-08-19T23:35:59 Z	qkxwsm	Data Transfer (IOI19_transfer)	C++14	100 / 100	96 ms	2640 KB

transfer

#include "transfer.h"
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;


vi get_attachment(vi source)
{
	int n = SZ(source);
	int k = 33 - __builtin_clz(n);
	vi res(k);
	int stor = 0;
	FOR(i, 0, n)
	{
		if (source[i]) stor ^= (i + 1);
	}
	FOR(i, 0, k - 1)
	{
		res[i] = ((stor & (1 << i)) ? 1 : 0);
	}
	res[k - 1] = ((__builtin_popcount(stor)) & 1);
	// cerr << SZ(res) << endl;
	// FOR(i, 0, k)
	// {
	// 	cerr <<res[i];
	// }
	// cerr << endl;
	return res;
}

vi retrieve(vi data)
{
	int n = (1 << (31 - __builtin_clz(SZ(data)))) - 1, k = SZ(data) - n;
	// cerr << "N = " << n << " K = " << k << endl;
	// // cerr << "DATA HAS\n";
	// FOR(i, 0, n + k)
	// {
	// 	cerr << data[i];
	// }
	// cerr << endl;
	vi res(n);
	FOR(i, 0, n) res[i] = data[i];
	int stor = 0;
	FORD(i, n + k - 1, n)
	{
		stor *= 2; if (data[i]) stor++;
	}
	// cerr << "STOR = " << stor << endl;
	if ((__builtin_popcount(stor) & 1) ^ data[n + k - 1]) return res;
	// cerr << "OK\n";
	FOR(i, 0, n) if (data[i]) stor ^= (i + 1);
	if (stor == 0) return res;
	res[stor - 1] ^= 1;
	// cerr << "RESULT\n";
	// FOR(i, 0, n)
	// {
	// 	cerr << res[i];
	// }
	// cerr << endl;
	return res;
	//find the guys that don't match or smth
}

Subtask #1

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	896 KB	Output is correct
2	Correct	7 ms	900 KB	Output is correct
3	Correct	7 ms	984 KB	Output is correct
4	Correct	7 ms	972 KB	Output is correct
5	Correct	7 ms	1028 KB	Output is correct
6	Correct	7 ms	968 KB	Output is correct
7	Correct	7 ms	1028 KB	Output is correct
8	Correct	7 ms	900 KB	Output is correct
9	Correct	6 ms	900 KB	Output is correct
10	Correct	7 ms	968 KB	Output is correct
11	Correct	8 ms	952 KB	Output is correct
12	Correct	7 ms	1028 KB	Output is correct
13	Correct	7 ms	972 KB	Output is correct
14	Correct	7 ms	1100 KB	Output is correct
15	Correct	7 ms	900 KB	Output is correct
16	Correct	7 ms	1028 KB	Output is correct
17	Correct	7 ms	1020 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	2620 KB	Output is correct
2	Correct	81 ms	2616 KB	Output is correct
3	Correct	82 ms	2616 KB	Output is correct
4	Correct	89 ms	2620 KB	Output is correct
5	Correct	90 ms	2616 KB	Output is correct
6	Correct	96 ms	2632 KB	Output is correct
7	Correct	92 ms	2620 KB	Output is correct
8	Correct	86 ms	2480 KB	Output is correct
9	Correct	80 ms	2476 KB	Output is correct
10	Correct	78 ms	2620 KB	Output is correct
11	Correct	79 ms	2640 KB	Output is correct
12	Correct	88 ms	2488 KB	Output is correct
13	Correct	92 ms	2608 KB	Output is correct
14	Correct	89 ms	2620 KB	Output is correct
15	Correct	90 ms	2484 KB	Output is correct
16	Correct	88 ms	2624 KB	Output is correct
17	Correct	87 ms	2608 KB	Output is correct
18	Correct	83 ms	2484 KB	Output is correct
19	Correct	81 ms	2608 KB	Output is correct