Submission #1096151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096151		MtSaka	Parrots (IOI11_parrots)	C++17	100 / 100	5 ms	1376 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include"bits/stdc++.h"
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)(a);++i)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
namespace{
vector<vector<ll>>comb(40,vector<ll>(40,0));
void init(){
    rep(i,40)rep(j,40)::comb[i][j]=0;
    rep(i,40)::comb[i][0]=1;
    rep(i,1,40)rep(j,1,i+1)::comb[i][j]=::comb[i-1][j-1]+::comb[i-1][j];
}
}
vector<int>calc(ll v,int len){
    int now=0;
    vector<int>res;
    int l=-1;
    rep(i,len+1){
        if(v>=::comb[15+i][i]){
            v-=::comb[15+i][i];
        }
        else{
            l=i;
            break;
        }
    }
    assert(l!=-1);
    assert(v<::comb[15+l][l]);
    rep(i,l){
        while(true){
            if(v>=::comb[15-now+l-i-1][l-i-1]){
                v-=::comb[15-now+l-i-1][l-i-1];
                now++;
            }
            else break;
        }
        res.emplace_back(now);
    }
    assert(res.size()==l);
    return res;
}
void encode(int N, int M[]) {
    ::init();
    for(int i=0,id=0;i<N;i+=4,id++){
        int cnt=0;
        ll now=0;
        ll tmp=1;
        for(int j=i;j<min(N,i+4);++j){
            cnt++;
            now+=tmp*M[j];
            tmp*=256;
        }
        auto a=calc(now,cnt*5);
        for(auto&e:a){
            send(id*16+e);
        }
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include"bits/stdc++.h"
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)(a);++i)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
namespace{
vector<vector<ll>>comb(40,vector<ll>(40,0));
void init(){
    rep(i,40)rep(j,40)::comb[i][j]=0;
    rep(i,40)::comb[i][0]=1;
    rep(i,1,40)rep(j,1,i+1)::comb[i][j]=::comb[i-1][j-1]+::comb[i-1][j];
}
}


vector<int>calc(vector<int>m,int sz){
    ll val=0;
    const int l=m.size();
    rep(i,l)val+=::comb[15+i][i];
    int now=0;
    rep(i,l){
        while(now<m[i]){
            val+=::comb[15-now+l-i-1][l-i-1];
            now++;
        }
    }
    vector<int>res;
    rep(i,sz){
        res.eb(val%256);
        val/=256;
    }
    return res;
}
void decode(int N, int L, int X[]){
    ::init();
    sort(X,X+L);
    int idx=0;
    rep(i,16){
        vector<int>now;
        while(idx<L&&X[idx]<(i+1)*16){
            now.eb(X[idx]-i*16);
            idx++;
        }
        auto res=calc(now,min(N,4));
        N-=min(N,4);
        for(auto e:res)output(e);
        if(N==0)break;
    }
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from encoder.cpp:3:
encoder.cpp: In function 'std::vector<int> calc(ll, int)':
encoder.cpp:58:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |     assert(res.size()==l);
      |            ~~~~~~~~~~^~~

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