Submission #1157401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157401		alexdd	Parrots (IOI11_parrots)	C++20	52 / 100	2 ms	840 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
void encode(int N, int M[])
{
    vector<int> sir;
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<8;j++)
        {
            if((1<<j)&M[i])
                sir.push_back(1);
            else
                sir.push_back(0);
        }
    }
    assert((int)sir.size() == 8*N);

    for(int lun=1;lun<=15*N;lun++)
    {
        int cnt_id = log2(lun);
        if((1<<cnt_id) < lun)
            cnt_id++;
        int cnt_val = 8 - cnt_id;
        if(cnt_val*lun >= 8*N)
        {
            for(int i=0;i<lun;i++)
            {
                int aux=i;
                for(int j=0;j<cnt_val;j++)
                    if(sir[i*cnt_val+j])
                        aux += (1<<(cnt_id+j));
                send(aux);
            }
            return;
        }
    }
    assert(0);
}
/*

primii log2(N) biti -> id
urmatorii log2(8 - log2(N)) biti -> bucket
ultimii 8 - log2(N) - log2(8 - log2(N)) biti -> valoare

K = N * (8 / (8 - log2(N) - log2(8 - log2(N))))



*/

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
void decode(int N, int lun, int X[])
{
    int cnt_id = log2(lun);
    if((1<<cnt_id) < lun)
        cnt_id++;
    int cnt_val = 8 - cnt_id;
    assert(cnt_val*lun >= 8*N);
    vector<int> sir(8*N,0);
    for(int i=0;i<lun;i++)
    {
        int id=0;
        for(int j=0;j<cnt_id;j++)
            if((1<<j)&X[i])
                id += (1<<j);
        for(int j=0;j<cnt_val;j++)
            if((1<<(cnt_id+j))&X[i])
                sir[id*cnt_val+j]=1;
    }
    for(int i=0;i<N;i++)
    {
        int val=0;
        for(int b=0;b<8;b++)
            if(sir[i*8+b])
                val += (1<<b);
        output(val);
    }
}

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