Submission #94052

#	Time	Username	Problem	Language	Result	Execution time	Memory
94052		fjzzq2002	Parrots (IOI11_parrots)	C++14	100 / 100	494 ms	170320 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef vector<int> vi;
namespace Enc{
void go(vi&p)
{
	while(p.size()&&!p.back()) p.pop_back();
}
vi operator + (const vi& a,const vi& b)
{
	vi p(max(a.size(),b.size())+1);
	for(int i=0;i<a.size();++i) p[i]+=a[i];
	for(int i=0;i<b.size();++i) p[i]+=b[i];
	for(int i=0;i+1<p.size();++i)
		while(p[i]>=2) p[i]-=2,p[i+1]++;
	go(p); return p;
}
bool cmp(vi& a,vi& b)
{
	go(a); go(b);
	if(a.size()!=b.size()) return a.size()<b.size();
	for(int i=int(a.size())-1;i>=0;--i)
		if(a[i]!=b[i]) return a[i]<b[i];
	return 0;
}
vi operator - (const vi& a,const vi& b)
{
	vi p(max(a.size(),b.size()));
	for(int i=0;i<a.size();++i) p[i]+=a[i];
	for(int i=0;i<b.size();++i) p[i]-=b[i];
	for(int i=0;i+1<p.size();++i)
		while(p[i]<0) p[i]+=2,p[i+1]--;
	go(p); return p;
}
vi f[257][335];
vi enc(vi a,int b)
{
	vi w;
	for(int i=1;i<=256;++i)
		for(int j=0;j<=b;++j)
		{
			if(cmp(a,f[256-i][b-j]))
			{
				w.pb(j),b-=j;
				break;
			}
			a=a-f[256-i][b-j];
		}
	return w;
}
vi dec(vi a,int b)
{
	vi w;
	for(int i=1;i<=256;++i)
		for(int j=0;j<=b;++j)
		{
			if(j==a[i-1]) {b-=j; break;}
			w=w+f[256-i][b-j];
		}
	return w;
}
}
void encode(int N,int X[])
{
	using namespace Enc;
	static bool ini=0;
	if(!ini)
	{
	ini=1;
	f[0][0].pb(1);
	for(int i=1;i<=256;++i)
		for(int j=0;j<=330;++j)
		{
			f[i][j]=f[i-1][j];
			if(j) f[i][j]=f[i][j]+f[i][j-1];
		}
	}
	vi sh;
	for(int i=0;i<N*8;++i) sh.pb(1);
	int B=0;
	while(!cmp(sh,f[256][B])) ++B;
	vi u,t;
//	for(int i=0;i<N;++i)
//		cerr<<X[i]<<",";cerr<<"\n";
	for(int i=0;i<N;++i)
		for(int k=7;k>=0;--k)
			u.pb((X[i]>>k)&1);
//	for(auto x:u) cerr<<x;cerr<<"EN\n";
	u=enc(u,B);
	for(int i=0;i<256;++i)
		for(int j=0;j<u[i];++j) t.pb(i);
	assert(t.size()==B);
	for(auto x:t) send(x);
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef vector<int> vi;
namespace Dec{
void go(vi&p)
{
	while(p.size()&&!p.back()) p.pop_back();
}
vi operator + (const vi& a,const vi& b)
{
	vi p(max(a.size(),b.size())+1);
	for(int i=0;i<a.size();++i) p[i]+=a[i];
	for(int i=0;i<b.size();++i) p[i]+=b[i];
	for(int i=0;i+1<p.size();++i)
		while(p[i]>=2) p[i]-=2,p[i+1]++;
	go(p); return p;
}
bool cmp(vi& a,vi& b)
{
	go(a); go(b);
	if(a.size()!=b.size()) return a.size()<b.size();
	for(int i=int(a.size())-1;i>=0;--i)
		if(a[i]!=b[i]) return a[i]<b[i];
	return 0;
}
vi operator - (const vi& a,const vi& b)
{
	vi p(max(a.size(),b.size()));
	for(int i=0;i<a.size();++i) p[i]+=a[i];
	for(int i=0;i<b.size();++i) p[i]-=b[i];
	for(int i=0;i+1<p.size();++i)
		while(p[i]<0) p[i]+=2,p[i+1]--;
	go(p); return p;
}
vi f[257][335];
vi enc(vi a,int b)
{
	vi w;
	for(int i=1;i<=256;++i)
		for(int j=0;j<=b;++j)
		{
			if(cmp(a,f[256-i][b-j]))
			{
				w.pb(j),b-=j;
				break;
			}
			a=a-f[256-i][b-j];
		}
	return w;
}
vi dec(vi a,int b)
{
	vi w;
	for(int i=1;i<=256;++i)
		for(int j=0;j<=b;++j)
		{
			if(j==a[i-1]) {b-=j; break;}
			w=w+f[256-i][b-j];
		}
	return w;
}
}
void decode(int N, int L, int X[])
{
	using namespace Dec;
	static bool ini=0;
	if(!ini)
	{
	ini=1;
	f[0][0].pb(1);
	for(int i=1;i<=256;++i)
		for(int j=0;j<=330;++j)
		{
			f[i][j]=f[i-1][j];
			if(j) f[i][j]=f[i][j]+f[i][j-1];
		}
	}
	vi sh;
	for(int i=0;i<N*8;++i) sh.pb(1);
	int B=0;
	while(!cmp(sh,f[256][B])) ++B;
	vi t(256);
	for(int i=0;i<L;++i) ++t[X[i]];
	vi s=dec(t,B);
	s.resize(N*8);
//	for(auto x:s) cerr<<x;cerr<<"DE\n";
	for(int i=0;i<N;++i)
	{
		int p=0;
		for(int j=0;j<=7;++j)
			p=p*2+s[i*8+j];
//		cerr<<p<<",";
		output(p);
	}
//	cerr<<"\n";
}

Compilation message (stderr)

encoder.cpp: In function 'vi Enc::operator+(const vi&, const vi&)':
encoder.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();++i) p[i]+=a[i];
              ~^~~~~~~~~
encoder.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b.size();++i) p[i]+=b[i];
              ~^~~~~~~~~
encoder.cpp:17:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i+1<p.size();++i)
              ~~~^~~~~~~~~
encoder.cpp: In function 'vi Enc::operator-(const vi&, const vi&)':
encoder.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();++i) p[i]+=a[i];
              ~^~~~~~~~~
encoder.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b.size();++i) p[i]-=b[i];
              ~^~~~~~~~~
encoder.cpp:34:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i+1<p.size();++i)
              ~~~^~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from encoder.cpp:3:
encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:95:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(t.size()==B);
         ~~~~~~~~^~~

decoder.cpp: In function 'vi Dec::operator+(const vi&, const vi&)':
decoder.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();++i) p[i]+=a[i];
              ~^~~~~~~~~
decoder.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b.size();++i) p[i]+=b[i];
              ~^~~~~~~~~
decoder.cpp:17:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i+1<p.size();++i)
              ~~~^~~~~~~~~
decoder.cpp: In function 'vi Dec::operator-(const vi&, const vi&)':
decoder.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<a.size();++i) p[i]+=a[i];
              ~^~~~~~~~~
decoder.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<b.size();++i) p[i]-=b[i];
              ~^~~~~~~~~
decoder.cpp:34:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i+1<p.size();++i)
              ~~~^~~~~~~~~

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