Submission #829887

#	Time	Username	Problem	Language	Result	Execution time	Memory
829887		MrDeboo	Data Transfer (IOI19_transfer)	C++17	100 / 100	600 ms	2536 KiB

transfer

#include "transfer.h"
#include "bits/stdc++.h"
using namespace std;
std::vector<int> get_attachment(std::vector<int> v) {
	int n=v.size();
	vector<int>voc((n==255?8:6));
	for(int i=1;i<=n;i++){
		for(int w=0;w<voc.size();w++){
			if(i&(1<<w))voc[w]^=v[i-1];
		}
	}
	int g=0;
	for(auto &i:voc)g^=i;
	voc.push_back(g);
	return voc;
}

std::vector<int> retrieve(std::vector<int> v) {
	int nn=(v.size()>100?9:7);
	int n=v.size()-nn;
	int g=0;
	for(int i=v.size()-2;i>=v.size()-nn;i--)g^=v[i];
	if(g!=v.back()){
		for(int i=0;i<nn;i++)v.pop_back();
		return v;
	}
	vector<int>voc(nn-1);
	for(int i=1;i<=n;i++){
		for(int w=0;w<nn-1;w++){
			if(i&(1<<w))voc[w]^=v[i-1];
		}
	}
	int f=0;
	for(int i=0;i<nn-1;i++){
		if(v[i+n]!=voc[i])f++;
	}
	if(f==0){
		for(int i=0;i<nn;i++)v.pop_back();
		return v;
	}
	for(int i=0;i<n;i++){
		int k=0;
		for(int w=0;w<nn-1;w++){
			if((i+1)&(1<<w)){
				if(voc[w]!=v[w+n])k++;
			}
		}
		if(k==f){
			v[i]^=1;
			break;
		}
	}
	for(int i=0;i<nn;i++)v.pop_back();
	return v;
}

Compilation message (stderr)

transfer.cpp: In function 'std::vector<int> get_attachment(std::vector<int>)':
transfer.cpp:8:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |   for(int w=0;w<voc.size();w++){
      |               ~^~~~~~~~~~~
transfer.cpp: In function 'std::vector<int> retrieve(std::vector<int>)':
transfer.cpp:22:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=v.size()-2;i>=v.size()-nn;i--)g^=v[i];
      |                       ~^~~~~~~~~~~~~

• Subtask 1: 60 / 60
• Subtask 2: 40 / 40