Submission #1140380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140380		x93bd0	Parrots (IOI11_parrots)	C++20	17 / 100	2 ms	840 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"

#include <algorithm>
#include <stdio.h>
#include <cmath>
using namespace std;

void encode(int N, int M[])
{
  uint t[0x80];
  for (uint x = 0; x < 0x80; x++)
    t[x] = 0;
  uint dis = 0, _dbg_msg_sz = 0;

  // printf("Input: ");
  pair<uint, uint> nM[2*N];
  uint rems = 0, rem = 0, p = 0;
  for (uint x = 0; x < N; p++)
  {
    uint i;
    if (rems == 7) {
      rems = 0;
      i = rem;
      rem = 0;
    } else {
      // printf("%d ", M[x]);
      i = ((M[x] << rems) + rem) & 0x7f;
      rem = M[x++] >> (8 - ++rems);
    }

    nM[p].first = i << 1;
    nM[p].second = p;
  } // printf("\n");

  if (rems)
  {
    nM[p].first = rem;
    nM[p].second = p;
    p++;
  }

  /*printf("Correct: ");
  for (uint x = 0; x < p; x++)
    printf("%u ", nM[x].first >> 1);
  printf("\n");*/

  sort(nM, nM + p);
  for (uint x = 0; x < p; x++)
  {
    send(nM[x].first);
    // printf("%d ", nM[x].second);
    uint packet = (x << 1) | 1;
    for (uint i = 0; i <= nM[x].second; i++)
      send(packet);
  } // printf("\n");
}

decoder

#include "decoder.h"
#include "decoderlib.h"

#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;

void _output(int n) {
  //printf("%u ", n);
  output(n);
}

void decode(int N, int L, int X[])
{
  uint s = (uint)ceil(N * 8 / 7) + 5;
  uint bytes[s];
  uint freq[s];

  for (uint x = 0; x < s; x++)
    freq[x] = 0;

  uint bs = 0;

  for (uint x = 0; x < L; x++)
  {
    if (X[x] & 1)
    {
      freq[X[x] >> 1]++;
    } else {
      bytes[bs++] = X[x] >> 1;
    }
  }

  sort(bytes, bytes + bs);
  /*for (uint x = 0; x < bs; x++)
    printf("%d ", bytes[x]);
  printf("\n");*/

  uint org_pos[bs];
  for (uint x = 0; x < s; x++) {
    if (!freq[x]) continue;
    org_pos[freq[x] - 1] = bytes[x];
  }

  /*printf("Guess:   ");
  for (uint x = 0; x < bs; x++)
    printf("%u ", org_pos[x]);
  printf("\n");*/

  uint c = 0;
  uint bef = 0, befs = 0;
  for (uint x = 0; c < N; x++)
  {
    if (befs < 2) {
      bef |= (org_pos[x] << befs) & 0xff;
      befs += 7;
      if (befs == 8) {
        _output(bef);
        c++;
        bef = 0, befs = 0;
      }

      continue;
    }

    _output((bef | (org_pos[x] << befs)) & 0xff);
    c++;

    bef = org_pos[x] >> (8 - befs);
    befs = 7 - (8 - befs);
  }

  if (befs && c < N)
    _output(bef);
}

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