Submission #64725

#	Time	Username	Problem	Language	Result	Execution time	Memory
64725		IvanC	Parrots (IOI11_parrots)	C++17	98 / 100	20 ms	2616 KiB

encoder

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

void encode(int N, int M[]){

	if(N <= 32){
		int qtd_bits = 5;

		for(int i = 0;i<N;i++){

			int copia = M[i];
			
			for(int j = 0;j<3;j++){
				int primeiro = (copia & 7);
				copia = copia >> 3;
				int enviar = (i | (primeiro << qtd_bits));
				for(int k = 0;k < (1 << j);k++) send(enviar);
			}

		}

	}
	else{

		vector<int> bits_mandar;

		for(int i = 0;i<N;i++){
			for(int j = 0;j<8;j++){
				if(M[i] & (1 << j)) bits_mandar.push_back(1);
				else bits_mandar.push_back(0);
			}
		}

		int nao_troca = 0,troca_sim = 0;
		for(int i = 0;i<bits_mandar.size();i++){
			if(i & 1){
				nao_troca += 2*bits_mandar[i];
				troca_sim += 2*(1 - bits_mandar[i]);
			}
			else{
				nao_troca += 1*bits_mandar[i];
				troca_sim += 1*(1 - bits_mandar[i]);
			}
		}

		if(troca_sim < nao_troca){
			for(int i = 0;i<bits_mandar.size();i++){
				bits_mandar[i] ^= 1;
			}
			for(int i = 0;i<4;i++) send(255);
		}

		int last_sent = 0;
		for(int i = 0;i<bits_mandar.size();i += 2){
			int manda_qnt = 0;
			if(bits_mandar[i]) manda_qnt++;
			if(bits_mandar[i+1]) manda_qnt += 2;
			for(int j = 0;j<manda_qnt;j++) send(last_sent);
			last_sent++;
		}

	}

}

decoder

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

void decode(int N, int L, int X[]){
 
 	if(N <= 32){
		map<int,int> mapa[65];
 	
		int ANS[65];
		memset(ANS,0,sizeof(ANS));
 	
		int qtd_bits = 5;
 	
		for(int i = 0;i < L;i++){
 	
			int pos = X[i] & ((1 << qtd_bits) - 1);
			int outros_bits = (X[i] >> qtd_bits);
 	
			mapa[pos][outros_bits]++;
 	
		}
 	
		for(int i = 0;i<N;i++){
	 
			for(auto it : mapa[i]){
				int outros_bits = it.first,freq = it.second;
				if(freq & 1) ANS[i] += outros_bits;
				if(freq & 2) ANS[i] += outros_bits*8;
				if(freq & 4) ANS[i] += outros_bits*64;
			}
 	
		}
	 
		for(int i = 0;i<N;i++) output(ANS[i]);

 	}
 	else{
		
		int troca = 0;
 		vector<int> bits_recebidos,freq;
 		freq.assign(256,0);

 		for(int i = 0;i<8*N;i++) bits_recebidos.push_back(0);
 		
 		for(int i = 0;i<L;i++){
 			freq[X[i]]++;
 		}

 		if(freq[255] >= 4){
 			freq[255] -= 4;
 			troca = 255;
 		}

 		for(int i = 0;i<freq.size();i++){
 			if(freq[i] & 1) bits_recebidos[2*i] = 1;
 			if(freq[i] & 2) bits_recebidos[2*i + 1] = 1;
 		}

 		for(int i = 0;i<N;i++){

 			int numero = 0,qual_pot = 1;
 			for(int j = 8*i;j<8*(i + 1);j++){
 				numero += bits_recebidos[j]*qual_pot;
 				qual_pot *= 2;
 			}

 			output(numero ^ troca);

 		}

 	}

}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:37:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<bits_mandar.size();i++){
                 ~^~~~~~~~~~~~~~~~~~~
encoder.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0;i<bits_mandar.size();i++){
                  ~^~~~~~~~~~~~~~~~~~~
encoder.cpp:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0;i<bits_mandar.size();i += 2){
                 ~^~~~~~~~~~~~~~~~~~~

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0;i<freq.size();i++){
                  ~^~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 17 / 19