| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 47522 | sampriti | 앵무새 (IOI11_parrots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "grader.h"
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
// dp[i][j] = number of non-decreasing subsequences of length i with prev element j
const int K = 16;
void encode(int N, int M[]) {
long long dp[21][K];
for(int j = 0; j < K; j++) dp[0][j] = 1;
for(int i = 1; i <= 20; i++) {
for(int j = 0; j < K; j++) {
dp[i][j] = 0;
for(int k = j; k < K; k++) dp[i][j] += dp[i - 1][k];
}
}
long long sum[21];
sum[0] = 0;
for(int i = 1; i <= 20; i++) sum[i] = sum[i - 1] + dp[i][0];
vector<int> A;
for(int i = 0; i < N; i++) A.push_back(M[i]);
if(N % 4 != 0) {
for(int i = 0; i < (4 - (N % 4)); i++) A.push_back(0);
N += 4 - (N % 4);
}
for(int i = 0; i < N; i += 4) {
int grp_num = i/4;
long long num = 0;
for(int j = 0; j < 4; j++) {
num |= ((long long)A[i+j]) << (j*8);
}
int len_req = -1;
for(int j = 1; j <= 20; j++) {
if(num < sum[j]) {
len_req = j;
break;
}
}
assert(len_req != -1);
num -= sum[len_req - 1];
vector<int> ans;
int prv = 0;
for(int j = len_req; j > 0; j--) {
long long sum = 0;
for(int k = prv; k < K; k++) {
if(num < (sum + dp[j - 1][k])) {
send((grp_num << 4) | k);
num -= sum;
prv = k;
break;
}
sum += dp[j - 1][k];
}
}
}
}
#include "grader.h"
#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;
// dp[i][j] = number of non-decreasing subsequences of length i with prev element j
const int K = 16;
void decode(int N, int L, int X[]) {
long long dp[21][K];
for(int j = 0; j < K; j++) dp[0][j] = 1;
for(int i = 1; i <= 20; i++) {
for(int j = 0; j < K; j++) {
dp[i][j] = 0;
for(int k = j; k < K; k++) dp[i][j] += dp[i - 1][k];
}
}
long long sum[21];
sum[0] = 0;
for(int i = 1; i <= 20; i++) sum[i] = sum[i - 1] + dp[i][0];
int N_ = N;
if(N % 4 != 0) N += 4 - (N % 4);
for(int grp_num = 0; grp_num < N/4; grp_num++) {
vector<int> perm;
for(int i = 0; i < L; i++) {
if((X[i] >> 4) == grp_num) {
perm.push_back(X[i] % (1 << 4));
}
}
sort(perm.begin(), perm.end());
int len_req = perm.size();
long long num = 0;
int prv = 0;
for(int i = len_req; i > 0; i--) {
for(int j = prv; j < perm[len_req - i]; j++) {
num += dp[i - 1][j];
}
prv = perm[len_req - i];
}
num += sum[len_req - 1];
for(int i = 0; i < 4; i++) {
if(grp_num * 4 + i < N_) {
output((num >> (i*8)) % (1 << 8));
}
}
}
};