oj.uz

Submission #798320

# Submission time Handle Problem Language Result Execution time Memory
798320 2023-07-30T15:15:56 Z khshg Parrots (IOI11_parrots) C++14
100 / 100
 1355 ms 17124 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int BASE = 1e9;
int LEN;
 
struct BIGNUM {
	vector<int> d;
}dp[262][256];
 
BIGNUM add(const BIGNUM& A, const BIGNUM& B) {
	BIGNUM res;
	int C = 0;
	for(int i = 0; i < max((int)A.d.size(), (int)B.d.size()) || C; ++i) {
		int cur = C;
		if(i < (int)A.d.size()) cur += A.d[i];
		if(i < (int)B.d.size()) cur += B.d[i];
		C = cur >= BASE;
		if(C) cur -= BASE;
		res.d.push_back(cur);
	}
	return res;
}
 
void sub(BIGNUM& A, const BIGNUM& B) {
	int C = 0;
	for(int i = 0; i < (int)B.d.size() || C; ++i) {
		A.d[i] -= C + (i < (int)B.d.size() ? B.d[i] : 0);
		C = A.d[i] < 0;
		if(C) A.d[i] += BASE;
	}
	while((int)A.d.size() && A.d.back() == 0) A.d.pop_back();
}
 
BIGNUM mul(const int& A, const BIGNUM& B) {
	BIGNUM res;
	int C = 0;
	for(int i = 0; i < (int)B.d.size() || C; ++i) {
		int cur = C;
		if(i < (int)B.d.size()) cur += A * B.d[i];
		C = cur / BASE;
		res.d.push_back(cur - C * BASE);
	}
	while((int)res.d.size() && res.d.back() == 0) res.d.pop_back();
	return res;
}
 
bool cmp(const BIGNUM& A, const BIGNUM& B) {
	if((int)A.d.size() != (int)B.d.size()) return (int)A.d.size() < (int)B.d.size();
	for(int i = (int)A.d.size() - 1; i >= 0; --i) {
		if(A.d[i] != B.d[i]) return A.d[i] < B.d[i];
	}
	return 0;
}
 
void encode(int32_t N, int32_t M[]) {
	LEN = 41 * N / 10;
	for(int i = 0; i < 256; ++i) dp[0][i].d = {1};// ONE
	for(int i = 1; i < LEN; ++i) dp[i][0].d = {1};// ONE
	for(int i = 1; i < LEN; ++i) {
		for(int j = 1; j < 256; ++j) {
			dp[i][j] = add(dp[i][j - 1], dp[i - 1][j]);
		}
	}
	BIGNUM val, pwi;
	pwi.d = {1};
	for(int i = N - 1; i >= 0; --i) {
		val = add(val, mul(M[i], pwi));
		if(i > 0) pwi = mul(256, pwi);
	}
	for(int i = LEN - 1; i >= 0; --i) {
		int j;
		for(j = 0; j < 256; ++j) {
			if(cmp(val, dp[i][j])) {
				break;
			}
			sub(val, dp[i][j]);
		}
		send(j);
	}
}

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int BASE = 1e9;
int LEN;
 
struct BIGNUM {
	vector<int> d;
}dp[262][256];
 
BIGNUM add(const BIGNUM& A, const BIGNUM& B) {
	BIGNUM res;
	int C = 0;
	for(int i = 0; i < max((int)A.d.size(), (int)B.d.size()) || C; ++i) {
		int cur = C;
		if(i < (int)A.d.size()) cur += A.d[i];
		if(i < (int)B.d.size()) cur += B.d[i];
		C = cur >= BASE;
		if(C) cur -= BASE;
		res.d.push_back(cur);
	}
	return res;
}
 
void sub(BIGNUM& A, const BIGNUM& B) {
	int C = 0;
	for(int i = 0; i < (int)B.d.size() || C; ++i) {
		A.d[i] -= C + (i < (int)B.d.size() ? B.d[i] : 0);
		C = A.d[i] < 0;
		if(C) A.d[i] += BASE;
	}
	while((int)A.d.size() && A.d.back() == 0) A.d.pop_back();
}
 
BIGNUM mul(const int& A, const BIGNUM& B) {
	BIGNUM res;
	int C = 0;
	for(int i = 0; i < (int)B.d.size() || C; ++i) {
		int cur = C;
		if(i < (int)B.d.size()) cur += A * B.d[i];
		C = cur / BASE;
		res.d.push_back(cur - C * BASE);
	}
	while((int)res.d.size() && res.d.back() == 0) res.d.pop_back();
	return res;
}
 
bool cmp(const BIGNUM& A, const BIGNUM& B) {
	if((int)A.d.size() != (int)B.d.size()) return (int)A.d.size() < (int)B.d.size();
	for(int i = (int)A.d.size() - 1; i >= 0; --i) {
		if(A.d[i] != B.d[i]) return A.d[i] < B.d[i];
	}
	return 0;
}
 
void decode(int32_t N, int32_t L, int32_t X[]) {
	LEN = 41 * N / 10;
	sort(X, X + L);
	for(int i = 0; i < 256; ++i) dp[0][i].d = {1};// ONE
	for(int i = 1; i < LEN; ++i) dp[i][0].d = {1};// ONE
	for(int i = 1; i < LEN; ++i) {
		for(int j = 1; j < 256; ++j) {
			dp[i][j] = add(dp[i][j - 1], dp[i - 1][j]);
		}
	}
	BIGNUM val;
	for(int i = LEN - 1; i >= 0; --i) {
		for(int j = 0; j < X[i]; ++j) val = add(val, dp[i][j]);
	}
	vector<BIGNUM> p(N);
	p[0].d = {1};
	for(int i = 1; i < N; ++i) {
		p[i] = mul(256, p[i - 1]);
	}
	for(int i = N - 1; i >= 0; --i) {
		int L = 0, R = 255;
		while(L < R) {
			int M = (L + R + 1) / 2;
			if(cmp(val, mul(M, p[i]))) {
				R = M - 1;
			} else {
				L = M;
			}
		}
		output(L);
		sub(val, mul(L, p[i]));
	}
}

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 4776 KB Output is correct
2 Correct 92 ms 5248 KB Output is correct
3 Correct 169 ms 5820 KB Output is correct
4 Correct 165 ms 5964 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4752 KB Output is correct
2 Correct 91 ms 5284 KB Output is correct
3 Correct 145 ms 5972 KB Output is correct
4 Correct 156 ms 5960 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 4816 KB Output is correct
2 Correct 156 ms 5828 KB Output is correct
3 Correct 219 ms 6556 KB Output is correct
4 Correct 426 ms 8828 KB Output is correct
5 Correct 449 ms 8944 KB Output is correct
6 Correct 508 ms 9144 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 5752 KB Output is correct - P = 4.062500
2 Correct 465 ms 9152 KB Output is correct - P = 4.093750
3 Correct 475 ms 9372 KB Output is correct - P = 4.090909
4 Correct 914 ms 13492 KB Output is correct - P = 4.100000
5 Correct 1321 ms 16028 KB Output is correct - P = 4.100000
6 Correct 1355 ms 16976 KB Output is correct - P = 4.095238
7 Correct 1351 ms 17124 KB Output is correct - P = 4.093750