oj.uz

Submission #739422

# Submission time Handle Problem Language Result Execution time Memory
739422 2023-05-10T12:36:52 Z onebit1024 Data Transfer (IOI19_transfer) C++17
100 / 100
 169 ms 2504 KB 
#include "transfer.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
 
\
string bin(int x){
	string res;
	for(int i = 30;i>=0;--i){
		if(x&(1ll<<i))res+='1';
		else res+='0';
	}
	while(!res.empty() && res[0]=='0')res.erase(res.begin());
	return res;
}
int power(int x){
	// is x a power of 2
	while((x%2)==0)x/=2;
	if(x==1)return 1;
	return 0;
}
 
 
std::vector<int> get_attachment(std::vector<int> source) {
	int v = 3;
	int x = 0;
	for(int i = 0;i<source.size();++i){
		while(power(v))v++;
		if(source[i])x^=v;
		v++;
	}
	string s= bin(x);
	vector<int>ret;
	for(auto w : s)ret.pb(w-'0');
	return ret;
}

std::vector<int> retrieve(std::vector<int> data) {
	int N = 63;
	if(data.size()>100)N = 255;
 
	int bits = data.size()-N;
	vector<int>ret;

	int v = 3, X = 0, Y = 0;
	for(int i = 0;i<N;++i){
		while(power(v))v++;
		if(data[i])X^=v;
		v++;
	}
	
	int pos = 0;
	for(int i = data.size()-1;i>=N;--i){
		if(data[i])Y+=(1ll<<pos);
		pos++;
	}
	if(X==Y){
		for(int i = 0;i<N;++i)ret.pb(data[i]);
		return ret;
	}
	v = 3;
	for(int i = 0;i<N;++i){
		while(power(v))v++;
		int nsum = X;
		data[i] = 1-data[i];
		nsum^=v;
		data[i] = 1-data[i];
		if(nsum==Y){
			for(int j = 0;j<i;++j)ret.pb(data[j]);
			ret.pb((data[i]?0:1));
			for(int j = i+1;j<N;++j)ret.pb(data[j]);
			return ret;
		}
		v++;
	}
	for(int i = 0;i<N;++i)ret.pb(data[i]);
	return ret;
}

Compilation message

transfer.cpp: In function 'std::vector<int> get_attachment(std::vector<int>)':
transfer.cpp:27:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i = 0;i<source.size();++i){
      |                ~^~~~~~~~~~~~~~
transfer.cpp: In function 'std::vector<int> retrieve(std::vector<int>)':
transfer.cpp:42:6: warning: unused variable 'bits' [-Wunused-variable]
   42 |  int bits = data.size()-N;
      |      ^~~~

Subtask #1
60.0 / 60.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 2428 KB Output is correct
2 Correct 157 ms 2488 KB Output is correct
3 Correct 163 ms 2496 KB Output is correct
4 Correct 155 ms 2500 KB Output is correct
5 Correct 163 ms 2460 KB Output is correct
6 Correct 149 ms 2480 KB Output is correct
7 Correct 145 ms 2488 KB Output is correct
8 Correct 144 ms 2484 KB Output is correct
9 Correct 143 ms 2488 KB Output is correct
10 Correct 135 ms 2488 KB Output is correct
11 Correct 138 ms 2444 KB Output is correct
12 Correct 148 ms 2496 KB Output is correct
13 Correct 169 ms 2488 KB Output is correct
14 Correct 157 ms 2496 KB Output is correct
15 Correct 148 ms 2504 KB Output is correct
16 Correct 149 ms 2492 KB Output is correct
17 Correct 141 ms 2488 KB Output is correct
18 Correct 139 ms 2412 KB Output is correct
19 Correct 142 ms 2488 KB Output is correct