Submission #123898

#	Time	Username	Problem	Language	Result	Execution time	Memory
123898		baluteshih	Parrots (IOI11_parrots)	C++14	98 / 100	13 ms	2032 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
#define MP make_pair
#define F first
#define S second
#define pb push_back
#define MEM(i,j) memset(i,j,sizeof i)
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<vector<int>> v;
vector<int> tmp(4,0);

void dfs(int d,int sum)
{
	if(d==4)
		return v.pb(tmp);
	for(int i=0;i+sum<=7;++i)
		tmp[d]=i,dfs(d+1,sum+i);
}

void encode(int N, int M[])
{
	v.clear(),dfs(0,0);
	for(int i=0;i<N;++i)
		for(int j=0;j<4;++j)
			for(int k=0;k<v[M[i]][j];++k)
				send(i<<2|j);
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
#define MP make_pair
#define F first
#define S second
#define pb push_back
#define MEM(i,j) memset(i,j,sizeof i)
#define ET cout << "\n"
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<vector<int>> vv;
vector<int> tmpp(4,0),cnt[64];

void dfs2(int d,int sum)
{
	if(d==4)
		return vv.pb(tmpp);
	for(int i=0;i+sum<=7;++i)
		tmpp[d]=i,dfs2(d+1,sum+i);
}

void decode(int N, int L, int X[])
{
	vv.clear(),dfs2(0,0);
	for(int i=0;i<N;++i)
		cnt[i].clear(),cnt[i].resize(4,0);
	for(int i=0;i<L;++i)
		++cnt[X[i]>>2][X[i]&3];
	for(int i=0;i<N;++i)
		output(lower_bound(ALL(vv),cnt[i])-vv.begin());
}

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