Submission #211907

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
211907	2020-03-21T16:33:55 Z	MarcoMeijer	Data Transfer (IOI19_transfer)	C++14	100 / 100	211 ms	2860 KB

transfer

#include "transfer.h"
#include <bits/stdc++.h>
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vi get_attachment(vi source) {
	vi ans;
	RE(bits,20) {
		int stepSize = (1<<bits);
		bool p=0;
		if(stepSize > source.size()) {
			RE(i,ans.size()) p ^= ans[i];
			ans.pb(p);
			return ans;
		}
		RE(j,source.size()) if((j+1)&stepSize) p^=source[j];
		ans.pb(p);
	}
}

vi retrieve(vi data) {
	int n=63;
	if(data.size() > 100) n=255;
	int expected=0;
	int reality=0;
	bool endCorrupt=0;
	RE(bits,20) {
		int stepSize = (1<<bits);
		bool p=0;
		if(stepSize > n) {
			REP(i,n,data.size()-1) p ^= data[i];
			if(p != data.back()) endCorrupt=1;
			break;
		}
		RE(j,n) if((j+1)&stepSize) p^=data[j];
		if(p) expected += stepSize;
		if(data[n+bits]) reality += stepSize;
	}
	if(!endCorrupt && reality!=expected) {
		int change=reality^expected;
		change--;
		data[change] ^= 1;
	}
	while(data.size() > n) data.pop_back();
	return data;
}

Compilation message

transfer.cpp: In function 'vi get_attachment(vi)':
transfer.cpp:29:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(stepSize > source.size()) {
      ~~~~~~~~~^~~~~~~~~~~~~~~
transfer.cpp: In function 'vi retrieve(vi)':
transfer.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(data.size() > n) data.pop_back();
        ~~~~~~~~~~~~^~~
transfer.cpp: In function 'vi get_attachment(vi)':
transfer.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	1136 KB	Output is correct
2	Correct	13 ms	992 KB	Output is correct
3	Correct	13 ms	1040 KB	Output is correct
4	Correct	13 ms	984 KB	Output is correct
5	Correct	13 ms	1040 KB	Output is correct
6	Correct	13 ms	1152 KB	Output is correct
7	Correct	13 ms	912 KB	Output is correct
8	Correct	13 ms	1120 KB	Output is correct
9	Correct	15 ms	1156 KB	Output is correct
10	Correct	13 ms	1112 KB	Output is correct
11	Correct	13 ms	1136 KB	Output is correct
12	Correct	13 ms	988 KB	Output is correct
13	Correct	13 ms	1124 KB	Output is correct
14	Correct	13 ms	1144 KB	Output is correct
15	Correct	13 ms	1040 KB	Output is correct
16	Correct	13 ms	1152 KB	Output is correct
17	Correct	13 ms	1144 KB	Output is correct

Subtask #2

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	194 ms	2664 KB	Output is correct
2	Correct	211 ms	2500 KB	Output is correct
3	Correct	198 ms	2676 KB	Output is correct
4	Correct	204 ms	2628 KB	Output is correct
5	Correct	194 ms	2668 KB	Output is correct
6	Correct	194 ms	2656 KB	Output is correct
7	Correct	211 ms	2664 KB	Output is correct
8	Correct	195 ms	2648 KB	Output is correct
9	Correct	196 ms	2668 KB	Output is correct
10	Correct	202 ms	2792 KB	Output is correct
11	Correct	197 ms	2676 KB	Output is correct
12	Correct	195 ms	2660 KB	Output is correct
13	Correct	195 ms	2860 KB	Output is correct
14	Correct	194 ms	2648 KB	Output is correct
15	Correct	195 ms	2664 KB	Output is correct
16	Correct	192 ms	2668 KB	Output is correct
17	Correct	197 ms	2676 KB	Output is correct
18	Correct	210 ms	2668 KB	Output is correct
19	Correct	192 ms	2668 KB	Output is correct