제출 #1279553

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279553		karn7777	앵무새 (IOI11_parrots)	C++20	81 / 100	6 ms	844 KiB

encoder

#include<vector>
#include<algorithm>
#include<utility>
#include "encoder.h"
#include "encoderlib.h"
using namespace std;
void encode(int n, int M[]){
    int dp[18][14];
    for(int i=0;i<=17;i++)for(int j=0;j<=13;j++)dp[i][j]=0;
    dp[0][0]=1;
    for(int i=1;i<=17;i++){
        for(int j=0;j<=13;j++){
            int sum=0;
            for(int k=0;k<=j;k++)sum+=dp[i-1][k];
            dp[i][j]=sum;
        }
    }
    vector<int> v;
    //encodes M to v
    int ans;
    for(int i=0;i<=(n/3);i++){
        vector<int> temp;
        if(i==n/3){
            if(n%3==0)break;
            if(n%3==1){
                ans=M[i*3];
                for(int k=0;k<=4;k++)temp.push_back(0);
            }
            if(n%3==2){
                ans=M[i*3]*256+M[i*3+1];
                for(int k=0;k<=9;k++)temp.push_back(0);
            }
        }else{
            int a=M[i*3],b=M[i*3+1],c=M[i*3+2];
            ans=a*256*256+b*256+c;
            for(int k=0;k<=14;k++)temp.push_back(0);
        }
        //Encode ans->temp
        int sum=0,remaining=12;
        for(int j=temp.size()-1;j>0;j--){
            for(int k=0;k<remaining;k++){
                if(sum+dp[j+1][remaining-k]<=ans){
                    sum+=dp[j+1][remaining-k];
                    temp[j]=k+1;
                }else break;
            }
            remaining-=temp[j];
        }
        temp[0]=ans-sum;
        for(auto x:temp)v.push_back(x);
    }
    //
    //for(auto x:v)cout << x << " ";
    //cout << endl;
    int sum=0;
    for(auto x:v){
        sum+=x;
        send(sum);
        //cout << sum << " ";
    }
    return;
}

decoder

#include<vector>
#include<algorithm>
#include<utility>
#include "decoder.h"
#include "decoderlib.h"
using namespace std;
void decode(int N, int l, int X[]){
    int dp[19][15];
    for(int i=0;i<=17;i++)for(int j=0;j<=13;j++)dp[i][j]=0;
    dp[0][0]=1;
    for(int i=1;i<=17;i++){
        for(int j=0;j<=13;j++){
            int sum=0;
            for(int k=0;k<=j;k++)sum+=dp[i-1][k];
            dp[i][j]=sum;
        }
    }
    vector<int> v;
    for(int i=0;i<l;i++){
        v.push_back(X[i]);
    }
    sort(v.begin(),v.end());
    int last=0,temp=0;
    for(int i=0;i<v.size();i++){
        int temp=v[i]-last;
        last=v[i];
        v[i]=temp;
    }
    for(int tempi=0;tempi<v.size()/15;tempi++){
        int i=tempi*15;
        vector<int> temp;
        int tempsum=0;
        for(int j=i;j<i+15;j++){
            temp.push_back(v[j]);
            tempsum+=v[j];
        }
        temp.insert(temp.begin(),12-tempsum);
        int ans=0,remaining=12;
        //decode temp into ans
        for(int j=temp.size()-1;j>=2;j--){
            for(int k=temp[j]-1;k>=0;k--){
                ans+=dp[j][remaining-k];
            }
            remaining-=temp[j];
        }
        ans+=temp[1];
        //
        int a,b,c;
        a=ans/(256*256);
        ans-=(256*256*a);
        b=ans/256;
        c=ans%256;
        output(a);
        output(b);
        output(c);
    }
    if(v.size()%15==5){
        int ans=0,tempsum=0;
        vector<int> temp;
        for(int j=((v.size()/15)*15);j<v.size();j++){
                temp.push_back(v[j]);
                tempsum+=v[j];
        }
        for(int i=0;i<10;i++)temp.push_back(0);
        temp.insert(temp.begin(),12-tempsum);
        //decode temp to ans
        int remaining=12;
        for(int j=temp.size()-1;j>=2;j--){
            for(int k=temp[j]-1;k>=0;k--){
                ans+=dp[j][remaining-k];
            }
            remaining-=temp[j];
        }
        ans+=temp[1];
        //
        output(ans);
    }
    if(v.size()%15==10){
        int ans=0,tempsum=0;
        vector<int> temp;
        for(int j=((v.size()/15)*15);j<v.size();j++){
                temp.push_back(v[j]);
                tempsum+=v[j];
        }
        for(int i=0;i<5;i++)temp.push_back(0);
        temp.insert(temp.begin(),12-tempsum);
        //decode temp to ans
        int remaining=12;
        for(int j=temp.size()-1;j>=2;j--){
            for(int k=temp[j]-1;k>=0;k--){
                ans+=dp[j][remaining-k];
            }
            remaining-=temp[j];
        }
        ans+=temp[1];
        //
        output(ans/256);
        output(ans%256);
    }
    return;
}

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