Submission #352078

#	Time	Username	Problem	Language	Result	Execution time	Memory
352078		amunduzbaev	Parrots (IOI11_parrots)	C++14	99 / 100	13 ms	1544 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"

#ifndef EVAL
#include "grader.cpp" 
#endif

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

#define pb push_back
#define sz(x) (int)x.size()

void encode(int n, int x[]){
	vector<int> ans;
	
	
	int xx = 0;
	
	for(int i=0;i<8;i++){
		int cnt = 0;
		for(int j=0;j<n;j++){
			if(x[j] >> i & 1) cnt++;
		}
		if(cnt * 2 >= n) xx += (1<<i);
	}
	
	//cout<<xx<<"\n";
	
	for(int i=0;i<n;i++){
		x[i] ^= xx;
		for(int j=0;j<8;j+=2){
			int f = j, s = j+1;
			if(x[i] >> f & 1) ans.pb((i << 2) + j/2);
			if(x[i] >> s & 1){
				ans.pb((i << 2) + j/2);
				ans.pb((i << 2) + j/2);
			}
		}
	}
	
	for(int i=0;i<sz(ans);i++){
		send(ans[i]);
	}
	for(int i=0;i<4;i++) send(xx);
}

decoder

#include "decoder.h"
#include "decoderlib.h"

#ifndef EVAL
#include "grader.cpp" 
#endif

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

void decode(int n, int l, int ans[]){
	map<int, int> mm;
	for(int i=0;i<l;i++) mm[ans[i]]++;
	int xx = 0;
	for(int i=0;i<l;i++){
		if(mm[ans[i]] >= 4){
			mm[ans[i]] -= 4;
			xx = ans[i];
			break;
		}
	}
	//cout<<"_____________\n";
	//cout<<xx<<"\n";
	//for(int i=0;i<l;i++){
		//for(int j=0;j<8;j++){
			//cout<<(ans[i] >> j & 1);
		//}cout<<"\n";
	//}cout<<"\n";
	
	vector<int> res(n);
	for(int i=0;i<n;i++){
		for(int j=0;j<8;j+=2){
			int gr = j/2;
			res[i] += mm[(i << 2) + gr]*(1 << j);
		}
	}
	//for(int i=0;i<n;i++) cout<<(res[i] ^ xx)<<" ";
	//cout<<"\n";
	
	
	for(int i=0;i<n;i++){
		output(res[i] ^ xx);
	}
}

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