Submission #923525

#	Time	Username	Problem	Language	Result	Execution time	Memory
923525		bachhoangxuan	Parrots (IOI11_parrots)	C++17	100 / 100	6 ms	1376 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
const int maxa = 256;
const int Max = 35;
const int Lim = 27;
ll dp[55][55];


void encode(int N, int M[])
{
    for(int i=0;i<=Max;i++){
        for(int j=0;j<Lim;j++){
            dp[i][j]=!(i|j);
            if(i) dp[i][j]+=dp[i-1][j];
            if(j) dp[i][j]+=dp[i][j-1];
        }
    }
    int cur=0;
    for(int i=0;i<N;i+=7){
        ll num=0,mul=1;
        int cnt=0;
        for(int j=i;j<min(i+7,N);j++){
            num+=1LL*M[j]*mul,mul*=maxa,cnt++;
        }
        for(int j=cnt*5;j>=1;j--){
            for(int k=0;k<min(maxa-cur,Lim);k++){
                if(dp[j][k]>num){
                    if(k) num-=dp[j][k-1];
                    send(cur+k);
                    break;
                }
            }
        }
        cur+=Lim;
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxa = 256;
const int Max = 35;
const int Lim = 27;
ll dp[55][55];

void decode(int N, int L, int X[])
{
    for(int i=0;i<=Max;i++){
        for(int j=0;j<Lim;j++){
            dp[i][j]=!(i|j);
            if(i) dp[i][j]+=dp[i-1][j];
            if(j) dp[i][j]+=dp[i][j-1];
        }
    }
    vector<vector<int>> d(N);
    for(int i=0;i<L;i++) d[X[i]/Lim].push_back(X[i]%Lim);
    for(int i=0;i<N;i++){
        if(d[i].empty()) continue;
        sort(d[i].begin(),d[i].end());
        ll num=0;
        for(int j=(int)d[i].size();j>=1;j--){
            int k=d[i][j-1];
            if(k) num+=dp[j][k-1];
        }
        for(int j=i*7;j<min((i+1)*7,N);j++){
            output(num%maxa);
            num/=maxa;
        }
    }
}

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 19 / 19