제출 #1157390

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157390		alexdd	앵무새 (IOI11_parrots)	C++20	52 / 100	2095 ms	840 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
void calc_cnts(int N, int &cnt_id, int &cnt_val, int &cnt_bucket)
{
    cnt_id = log2(N);
    if((1<<cnt_id) < N)
        cnt_id++;
    assert((1<<cnt_id) >= N);
    bool gasit=0;
    for(cnt_val=8-cnt_id;cnt_val>0;cnt_val--)
    {
        int cate_buc = (8-1)/cnt_val + 1;
        cnt_bucket = log2(cate_buc);
        if((1<<cnt_bucket) < cate_buc)
            cnt_bucket++;
        assert((1<<cnt_bucket) >= cate_buc);

        if(cnt_id + cnt_val + cnt_bucket <= 8)
        {
            gasit=1;
            break;
        }
    }
    if(!gasit)
        while(1);
    assert(gasit);
}
void encode(int N, int M[])
{
    int cnt_id,cnt_val,cnt_bucket;
    calc_cnts(N,cnt_id,cnt_val,cnt_bucket);
    for(int i=0;i<N;i++)
    {
        int bucket=0;
        for(int le=0;le<8;le+=cnt_val)
        {
            int aux=0;
            for(int j=0;j<cnt_id;j++)
                if((1<<j)&i)
                    aux += (1<<j);
            for(int j=0;j<cnt_bucket;j++)
                if(bucket&(1<<j))
                    aux += (1<<(cnt_id + j));
            for(int b=le;b<min(8,le+cnt_val);b++)
                if(M[i]&(1<<b))
                    aux += (1<<(cnt_id + cnt_bucket + (b-le)));
            send(aux);
            bucket++;
        }
    }
}
/*

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 calc_cnts2(int N, int &cnt_id, int &cnt_val, int &cnt_bucket)
{
  cnt_id = log2(N);
  if((1<<cnt_id) < N)
    cnt_id++;
  assert((1<<cnt_id) >= N);
  bool gasit=0;
  for(cnt_val=8-cnt_id;cnt_val>0;cnt_val--)
  {
    int cate_buc = (8-1)/cnt_val + 1;
    cnt_bucket = log2(cate_buc);
    if((1<<cnt_bucket) < cate_buc)
      cnt_bucket++;
    assert((1<<cnt_bucket) >= cate_buc);

    if(cnt_id + cnt_val + cnt_bucket <= 8)
    {
      gasit=1;
      break;
    }
  }
  assert(gasit);
}
void decode(int N, int L, int X[])
{
  int cnt_id,cnt_val,cnt_bucket;
  calc_cnts2(N,cnt_id,cnt_val,cnt_bucket);
  vector<int> val(N,0);
  for(int i=0;i<L;i++)
  {
    int id=0;
    for(int b=0;b<cnt_id;b++)
      if((1<<b)&X[i])
        id+=(1<<b);
    int bucket=0;
    for(int b=0;b<cnt_bucket;b++)
      if((1<<(cnt_id+b))&X[i])
        bucket+=(1<<b);
    int le = bucket*cnt_val;
    for(int b=0;b<cnt_val;b++)
      if((1<<(cnt_id+cnt_bucket+b))&X[i])
        val[id] += (1<<(le+b));
  }
  for(int i=0;i<N;i++)
    output(val[i]);
}

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