oj.uz

답안 #125596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125596 2019-07-06T04:08:04 Z thebes 앵무새 (IOI11_parrots) C++14
100 / 100
 11 ms 1776 KB 
#include <bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"
using namespace std;

typedef long long ll;
ll dp[22][20], i, j;
ll cmp(ll len,ll lst){
    if(len==0) return 1LL;
    else if(dp[len][lst]) return dp[len][lst];
    for(int i=lst;i<=16;i++)
        dp[len][lst]+=cmp(len-1,i);
    return dp[len][lst];
}
void enc(ll idx,ll wtf,ll len,ll lst){
    if(!len) return;
    for(ll i=lst;i<=16;i++){
        if(cmp(len,i+1)<=wtf){
            if(i<16) send((idx<<4)+i);
            wtf -= cmp(len,i+1);
            enc(idx, wtf, len-1, i);
            return;
        }
    }
}
void encode(int N,int *M){
    for(i=0;i<N;i+=4){
        ll heh = 0;
        for(j=0;j<4&&i+j<N;j++)
            heh += (1LL<<(j*8))*M[i+j];
        enc(i>>2,heh,5*j,0);
    }
}
#include <bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"
using namespace std;

typedef long long ll;
ll dp[22][20], i, j;
ll cmp(ll len,ll lst){
    if(len==0) return 1LL;
    else if(dp[len][lst]) return dp[len][lst];
    for(int i=lst;i<=16;i++)
        dp[len][lst]+=cmp(len-1,i);
    return dp[len][lst];
}
vector<int> heh[200];
ll dec(ll len,ll lst,ll id){
    if(len==0) return 0LL;
    ll ret = 0, idx = heh[id].size()-len;
    ret = cmp(len,heh[id][idx]+1);
    return ret+dec(len-1,heh[id][idx],id);
}
void decode(int N,int L,int *M){
  	for(i=0;i<200;i++) heh[i].clear();
    for(i=0;i<L;i++){
        ll idx = (M[i]>>4);
        heh[idx].push_back(M[i]&15);
    }
    for(i=0;i<ceil(N/4.0);i++){
        ll len = 5*min(N-4*i,4LL);
        while(heh[i].size()<len) heh[i].push_back(16);
        sort(heh[i].begin(),heh[i].end());
    }
    for(i=0;i<ceil(N/4.0);i++){
        ll len = min(N-4*i,4LL);
        ll wtf = dec(5*len,0,i);
        for(j=0;j<len;j++){
            output(wtf%256);
            wtf/=256;
        }
    }
}

Compilation message

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:30:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(heh[i].size()<len) heh[i].push_back(16);
               ~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 892 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1520 KB Output is correct
2 Correct 6 ms 1520 KB Output is correct
3 Correct 5 ms 1520 KB Output is correct
4 Correct 7 ms 1520 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1520 KB Output is correct
2 Correct 5 ms 1520 KB Output is correct
3 Correct 5 ms 1520 KB Output is correct
4 Correct 5 ms 1520 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1520 KB Output is correct
2 Correct 5 ms 1504 KB Output is correct
3 Correct 5 ms 1520 KB Output is correct
4 Correct 7 ms 1520 KB Output is correct
5 Correct 7 ms 1776 KB Output is correct
6 Correct 7 ms 1520 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1520 KB Output is correct - P = 5.000000
2 Correct 7 ms 1520 KB Output is correct - P = 4.937500
3 Correct 7 ms 1776 KB Output is correct - P = 4.969697
4 Correct 10 ms 1776 KB Output is correct - P = 4.860000
5 Correct 11 ms 1776 KB Output is correct - P = 4.850000
6 Correct 10 ms 1776 KB Output is correct - P = 4.888889
7 Correct 11 ms 1776 KB Output is correct - P = 4.875000