Submission #704638

#	Time	Username	Problem	Language	Result	Execution time	Memory
704638		bin9638	Parrots (IOI11_parrots)	C++17	100 / 100	11 ms	1392 KiB

encoder

#ifndef SKY
#include "encoder.h"
#include "encoderlib.h"
#endif // SKY

#include <bits/stdc++.h>
using namespace std;

#define mot (__int128_t)1
#define i128 __int128_t

#ifdef SKY
vector<int> tokens;
void send(int x) {
    tokens.push_back(x);
}

void write(__int128_t x)
{
    if(x==0)
    {
        cout<<0<<endl;
        return;
    }
    string s="";
    while(x>0)
    {
        s=(char)(x%10+'0')+s;
        x/=10;
    }
    cout<<s<<endl;
}

#endif // SKY

void encode(int n, int M[])
{
    if(n==1)
    {
        send(M[0]);
        return;
    }
    int length=n*5/8;
     __int128_t dp[45][35]={};
     for(int i=0;i<32;i++)
        dp[length][i]=1;
    for(int i=length-1;i>=1;i--)
        for(int j=0;j<32;j++)
            for(int t=j;t<32;t++)
                dp[i][j]+=dp[i+1][t];
    for(int k=0;k<8;k++)
    {
        i128 vt=0;
        for(int i=0;i<n;i++)
            if((M[i]>>k)&1)
                vt+=(mot<<i);
      //  write(vt);
        vt++;
        int cuoi=0;
        for(int i=1;i<=length;i++)
        {
            for(int j=cuoi;j<32;j++)
                if(dp[i][j]<vt)
                {
                    vt-=dp[i][j];
                }else
                {
                //    cout<<j<<endl;
                    send((k<<5)+j);
                    cuoi=j;
                    break;
                }
        }
    }
}

#ifdef SKY
int main(void) {
    freopen("ENCODE.inp","r",stdin);
    freopen("ENCODE.out","w",stdout);
    srand(time(0));
    int n; cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    encode(n, a);
    random_shuffle(tokens.begin(),tokens.end());
    cout << n << endl;
    cout << tokens.size() << endl;
    for (int x : tokens) cout << x << " " ; cout << endl;

    return 0;
}
#endif // SKY

decoder

#ifndef SKY
#include "decoder.h"
#include "decoderlib.h"
#endif // SKY

#include <bits/stdc++.h>
using namespace std;

#define mot (__int128_t)1
#define i128 __int128_t

#ifdef SKY
vector<int> tokens;
void output(int b) {
    cout<<b<<" ";
}

void write(__int128_t x)
{
    if(x==0)
    {
        cout<<0<<endl;
        return;
    }
    string s="";
    while(x>0)
    {
        s=(char)(x%10+'0')+s;
        x/=10;
    }
    cout<<s<<endl;
}

#endif // SKY

void decode(int n, int l,int X[])
{
   if(n==1)
   {
       output(X[0]);
       return;
   }
   int length=n*5/8,f[n];
     __int128_t dp[45][35]={};
     for(int i=0;i<32;i++)
        dp[length][i]=1;
    for(int i=length-1;i>=1;i--)
        for(int j=0;j<32;j++)
            for(int t=j;t<32;t++)
                dp[i][j]+=dp[i+1][t];
    int kq[n]={};
    for(int k=0;k<8;k++)
    {
        i128 vt=0;
        int a[n+5]={},dem=0;
        for(int i=0;i<l;i++)
            if((X[i]>>5)==k)
            {
                a[++dem]=(X[i]&((1<<5)-1));
              //  cout<<a[dem]<<endl;
            }
        sort(a+1,a+1+dem);
        //for(int i=1;i<=dem;i++)cout<<a[i]<<" ";cout<<endl;
        for(int i=dem;i>=1;i--)
        {
            int cuoi=(i==1 ? 0 : a[i-1]);
            for(int j=cuoi;j<a[i];j++)
                vt+=dp[i][j];
        }
       // write(vt);
        for(int i=0;i<n;i++)
            if((vt>>i)&1)
                kq[i]+=(1<<k);
    }
    for(int i=0;i<n;i++)
        output(kq[i]);
}

#ifdef SKY
int main(void) {
    freopen("DECODE.inp","r",stdin);
    freopen("DECODE.out","w",stdout);
    int n,l;
    cin>>n>>l;
    int a[l];
    for(int i=0;i<l;i++)
        cin>>a[i];
    decode(n,l,a);
    return 0;
}
#endif // SKY

Compilation message (stderr)

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:43:21: warning: unused variable 'f' [-Wunused-variable]
   43 |    int length=n*5/8,f[n];
      |                     ^

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