oj.uz

Submission #284804

# Submission time Handle Problem Language Result Execution time Memory
284804 2020-08-28T04:24:46 Z TMJN Parrots (IOI11_parrots) C++17
99 / 100
 9 ms 1792 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

static ll c[26][26];


/*
vector<int>k;
void send(int t){
	k.push_back(t);
}
*/
ll comb(int n,int r){
	if(n<r)return 0;
	return c[n-r][r];
}

vector<int>F(ll t){
	vector<int>v(16,0);
	int s=20;
	for(int i=0;i<15;i++){
		ll k=0;
		for(int j=0;j<=s;j++){
			k+=comb(14-i+j,j);
		}
//		cout<<t<<' '<<k<<endl;
		if(t>k){
			t-=k;
			v[i]++;
			s--;
			i--;
		}
	}
	v[15]=t;
	return v;
}

void encode(int N, int M[]){
	for(int i=0;i<=25;i++){
		for(int j=0;j<=25;j++){
			c[i][j]=0;
		}
	}
	c[0][0]=1;
	for(int i=0;i<=25;i++){
		for(int j=0;j<=25;j++){
			if(i)c[i][j]+=c[i-1][j];
			if(j)c[i][j]+=c[i][j-1];
		}
	}
	for(int i=0;i*4<N;i++){
		ll t=0;
		for(int j=i*4;j<i*4+4;j++){
			t*=256;
			if(N<=j)continue;
			t+=M[j];
		}
		vector<int>v=F(t);
		for(int j=0;j<16;j++){
			for(int k=0;k<v[j];k++){
				send(i*16+j);
			}
		}
	}
}

/*
int main(){
	int n,m[100];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>m[i];
	}
	encode(n,m);
	cout<<n<<' '<<k.size()<<endl;
	for(int i:k){
		cout<<i<<endl;
	}
}
*/

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

static int C[256],res[64];
static ll c[26][26];

/*
void output(int x){
	cout<<x<<endl;
}
*/

ll dcomb(int n,int r){
	if(n<r)return 0;
	return c[n-r][r];
}

ll f(vector<int>v){
	ll t=0;
	int s=20;
	for(int i=0;i<15;i++){
		if(v[i]){
			v[i]--;
			for(int j=0;j<=s;j++){
				t+=dcomb(14-i+j,j);
			}
			s--;
			i--;
		}
	}
	t+=v[15];
	return t;
}

void decode(int N, int L, int X[]){
	for(int i=0;i<=25;i++){
		for(int j=0;j<=25;j++){
			c[i][j]=0;
		}
	}
	c[0][0]=1;
	for(int i=0;i<=25;i++){
		for(int j=0;j<=25;j++){
			if(i)c[i][j]+=c[i-1][j];
			if(j)c[i][j]+=c[i][j-1];
		}
	}
	for(int i=0;i<256;i++){
		C[i]=0;
	}
	for(int i=0;i<L;i++){
		C[X[i]]++;
	}
	for(int i=0;i<16;i++){
		vector<int>v(16,0);
		for(int j=0;j<16;j++){
			v[j]=C[i*16+j];
		}
		ll t=f(v);
		for(int j=3;j>=0;j--){
			res[i*4+j]=t%256;
			t/=256;
		}
	}
	for(int i=0;i<N;i++){
		output(res[i]);
	}
}

/*
int main(){
	int n,l,x[100];
	cin>>n>>l;
	for(int i=0;i<l;i++){
		cin>>x[i];
	}
	decode(n,l,x);
}
*/

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1536 KB Output is correct
2 Correct 3 ms 1536 KB Output is correct
3 Correct 4 ms 1536 KB Output is correct
4 Correct 4 ms 1536 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1536 KB Output is correct
2 Correct 3 ms 1536 KB Output is correct
3 Correct 3 ms 1536 KB Output is correct
4 Correct 3 ms 1536 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1536 KB Output is correct
2 Correct 3 ms 1536 KB Output is correct
3 Correct 3 ms 1536 KB Output is correct
4 Correct 6 ms 1536 KB Output is correct
5 Correct 5 ms 1536 KB Output is correct
6 Correct 5 ms 1536 KB Output is correct

Subtask #5
18.0 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 1536 KB Output is partially correct - P = 5.250000
2 Partially correct 5 ms 1536 KB Output is partially correct - P = 5.250000
3 Partially correct 6 ms 1536 KB Output is partially correct - P = 5.666667
4 Partially correct 8 ms 1792 KB Output is partially correct - P = 5.420000
5 Partially correct 9 ms 1792 KB Output is partially correct - P = 5.250000
6 Partially correct 9 ms 1792 KB Output is partially correct - P = 5.269841
7 Partially correct 9 ms 1792 KB Output is partially correct - P = 5.250000