oj.uz

Submission #923231

# Submission time Handle Problem Language Result Execution time Memory
923231 2024-02-07T02:17:13 Z daoquanglinh2007 Parrots (IOI11_parrots) C++17
100 / 100
 962 ms 14420 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
 
#define isz(a) (int)(a).size()
#define ll long long
#define vu vector <unsigned>
 
const int NM = 64;
const ll base = 1LL<<32;
 
int N, L, M[NM+5], X[5*NM+5];
vu dp[5*NM+5][256];

vu create(ll x){
	vu s = {};
	while (x > 0){
		s.push_back(x%base);
		x /= base;
	}
	if (s.empty()) s.push_back(0);
	reverse(s.begin(), s.end());
	return s;
}
 
ll decreate(vu s){
	ll x = 0;
	for (int i = 0; i < isz(s); i++)
		x = x*base+s[i];
	return x;
}
 
int cmp(vu a, vu b){
	if (isz(a) < isz(b)) return -1;
	if (isz(a) > isz(b)) return 1;
	if (a < b) return -1;
	if (a > b) return 1;
	return 0;
}
 
vu add(vu a, vu b){
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	while (isz(a) < isz(b)) a.push_back(0);
	while (isz(b) < isz(a)) b.push_back(0);
	vu c = {};
	ll carry = 0;
	for (int i = 0; i < isz(a); i++){
		ll s = (ll)a[i]+b[i]+carry;
		c.push_back(s%base);
		carry = s/base;
	}
	if (carry > 0) c.push_back(1);
	reverse(c.begin(), c.end());
	return c;
}
 
vu sub(vu a, vu b){
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	while (isz(a) < isz(b)) a.push_back(0);
	while (isz(b) < isz(a)) b.push_back(0);
	vu c = {};
	int borrow = 0;
	for (int i = 0; i < isz(a); i++){
		ll h = (ll)a[i]-b[i]-borrow;
		if (h < 0){
			h += base;
			borrow = 1;
		}
		else{
			borrow = 0;
		}
		c.push_back(h);
	}
	while (isz(c) > 1 && c[isz(c)-1] == 0) c.pop_back();
	reverse(c.begin(), c.end());
	return c;
}
 
void preprocess(){
	for (int i = 255; i >= 0; i--){
		dp[L][i] = create(256-i);
	}
	for (int i = L-1; i >= 1; i--)
		for (int j = 255; j >= 0; j--){
			dp[i][j] = dp[i+1][j];
			if (j < 255) dp[i][j] = add(dp[i][j], dp[i][j+1]);
		}
}
 
vu mul(vu a, ll b){
	vu c = {};
	ll carry = 0;
	for (int i = isz(a)-1; i >= 0; i--){
		ll s = (ll)a[i]*b+carry;
		c.push_back(s%base);
		carry = s/base;
	}
	while (carry > 0){
		c.push_back(carry%base);
		carry /= base;
	}
	while (isz(c) > 1 && c[isz(c)-1] == 0) c.pop_back();
	reverse(c.begin(), c.end());
	return c;
}
 
void trace(int i, vu s){
	if (i > L) return;
	for (int j = 255; j >= 0; j--){
		if (cmp(dp[i][j], s) >= 0){
			send(j);
			if (j < 255) s = sub(s, dp[i][j+1]);
			trace(i+1, s);
			return;
		}
	}
}
 
void encode(int _N, int _M[]){
	N = _N;
	L = 4*N+10;
	for (int i = 0; i < N; i++) M[i] = _M[i];
	
	preprocess();
	vu tmp = create(0);
	for (int i = 0; i < N; i++){
		tmp = add(mul(tmp, 256), create(M[i]));
	}
	tmp = add(tmp, create(1));
	trace(1, tmp);
}
#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
 
#define isz(a) (int)(a).size()
#define ll long long
#define vu vector <unsigned>
 
const int NM = 64;
const ll base = 1LL<<32;
 
int N, L, M[NM+5], X[5*NM+5];
vu dp[5*NM+5][256];

vu create(ll x){
	vu s = {};
	while (x > 0){
		s.push_back(x%base);
		x /= base;
	}
	if (s.empty()) s.push_back(0);
	reverse(s.begin(), s.end());
	return s;
}
 
ll decreate(vu s){
	ll x = 0;
	for (int i = 0; i < isz(s); i++)
		x = x*base+s[i];
	return x;
}
 
int cmp(vu a, vu b){
	if (isz(a) < isz(b)) return -1;
	if (isz(a) > isz(b)) return 1;
	if (a < b) return -1;
	if (a > b) return 1;
	return 0;
}
 
vu add(vu a, vu b){
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	while (isz(a) < isz(b)) a.push_back(0);
	while (isz(b) < isz(a)) b.push_back(0);
	vu c = {};
	ll carry = 0;
	for (int i = 0; i < isz(a); i++){
		ll s = (ll)a[i]+b[i]+carry;
		c.push_back(s%base);
		carry = s/base;
	}
	if (carry > 0) c.push_back(1);
	reverse(c.begin(), c.end());
	return c;
}
 
vu sub(vu a, vu b){
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	while (isz(a) < isz(b)) a.push_back(0);
	while (isz(b) < isz(a)) b.push_back(0);
	vu c = {};
	int borrow = 0;
	for (int i = 0; i < isz(a); i++){
		ll h = (ll)a[i]-b[i]-borrow;
		if (h < 0){
			h += base;
			borrow = 1;
		}
		else{
			borrow = 0;
		}
		c.push_back(h);
	}
	while (isz(c) > 1 && c[isz(c)-1] == 0) c.pop_back();
	reverse(c.begin(), c.end());
	return c;
}
 
void preprocess(){
	for (int i = 255; i >= 0; i--){
		dp[L][i] = create(256-i);
	}
	for (int i = L-1; i >= 1; i--)
		for (int j = 255; j >= 0; j--){
			dp[i][j] = dp[i+1][j];
			if (j < 255) dp[i][j] = add(dp[i][j], dp[i][j+1]);
		}
}
 
vu find_order(int i){
	if (i > L) return create(1);
	vu res = create(0);
	if (X[i] < 255) res = dp[i][X[i]+1];
	return add(res, find_order(i+1));
}
 
vu div(vu a, ll b){
	vu c = {};
	ll h = 0;
	for (int i = 0; i < isz(a); i++){
		h = (ll)h*base+a[i];
		c.push_back(h/b);
		h %= b;
	}
	reverse(c.begin(), c.end());
	while (isz(c) > 1 && c[isz(c)-1] == 0) c.pop_back();
	reverse(c.begin(), c.end());
	return c;
}
 
ll mod(vu a, ll b){
	ll h = 0;
	for (int i = 0; i < isz(a); i++){
		h = ((ll)h*base+a[i])%b;
	}
	return h;
}

void decode(int _N, int _L, int _X[]){
	N = _N;
	L = _L;
	for (int i = 1; i <= L; i++) X[i] = _X[i-1];
	sort(X+1, X+1+L);
	
	preprocess();
	
	vu tmp = sub(find_order(1), create(1));
	
	for (int i = N-1; i >= 0; i--){
		M[i] = mod(tmp, 256);
		tmp = div(tmp, 256);
	}
	
	for (int i = 0; i < N; i++) output(M[i]);
}

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 7616 KB Output is correct
2 Correct 150 ms 7860 KB Output is correct
3 Correct 190 ms 8036 KB Output is correct
4 Correct 209 ms 8308 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 7360 KB Output is correct
2 Correct 163 ms 7588 KB Output is correct
3 Correct 198 ms 8436 KB Output is correct
4 Correct 217 ms 8048 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 7612 KB Output is correct
2 Correct 205 ms 8056 KB Output is correct
3 Correct 254 ms 8616 KB Output is correct
4 Correct 435 ms 9824 KB Output is correct
5 Correct 449 ms 9944 KB Output is correct
6 Correct 432 ms 10072 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 8244 KB Output is correct
2 Correct 431 ms 10240 KB Output is correct
3 Correct 452 ms 10044 KB Output is correct
4 Correct 739 ms 12480 KB Output is correct
5 Correct 883 ms 13836 KB Output is correct
6 Correct 945 ms 14244 KB Output is correct
7 Correct 962 ms 14420 KB Output is correct