oj.uz

Submission #94050

# Submission time Handle Problem Language Result Execution time Memory
94050 2019-01-15T06:32:16 Z fjzzq2002 Parrots (IOI11_parrots) C++14
100 / 100
 484 ms 170224 KB 
#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];
		}
	}
	int B=N*5;
	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);
}
#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 t(256);
	for(int i=0;i<L;++i) ++t[X[i]];
	int B=N*5;
	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

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:92: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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 169824 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 170120 KB Output is correct
2 Correct 436 ms 170024 KB Output is correct
3 Correct 443 ms 170040 KB Output is correct
4 Correct 431 ms 170176 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 170136 KB Output is correct
2 Correct 407 ms 169968 KB Output is correct
3 Correct 430 ms 170224 KB Output is correct
4 Correct 439 ms 169968 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 170136 KB Output is correct
2 Correct 448 ms 169856 KB Output is correct
3 Correct 461 ms 169968 KB Output is correct
4 Correct 470 ms 169968 KB Output is correct
5 Correct 461 ms 169968 KB Output is correct
6 Correct 431 ms 170224 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 170000 KB Output is correct - P = 5.000000
2 Correct 426 ms 170224 KB Output is correct - P = 5.000000
3 Correct 430 ms 169968 KB Output is correct - P = 5.000000
4 Correct 456 ms 170216 KB Output is correct - P = 5.000000
5 Correct 467 ms 170064 KB Output is correct - P = 5.000000
6 Correct 484 ms 170224 KB Output is correct - P = 5.000000
7 Correct 480 ms 170224 KB Output is correct - P = 5.000000