Submission #1140434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140434		x93bd0	Parrots (IOI11_parrots)	C++20	0 / 100	2 ms	836 KiB

encoder

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

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

static uint _debug_msg_sz = 0;
void _send(int d) {
  _debug_msg_sz++;
  send(d);
}

void encode(int N, int M[])
{
  uint t[0x80];
  for (uint x = 0; x < 0x80; x++)
    t[x] = 0;
  uint dis = 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 << 1;
    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);
    // _dbg_msg_sz += 1 + nM[x].second;
    //uint packet = ((nM[x].second & 0xff) << 8) + ((x & 0x7f) << 1) | 1;
    //_send(packet);
    // printf("%d (%u, %d < %d)\n", _debug_msg_sz, nM[x].second, x, p);
    uint packet = ((nM[x].second & 0b11) << 6) | ((x & 0b11111) << 1) | 1;
    _send(packet);

    for (uint i = 0; i < (nM[x].second >> 2); i++)
      _send(packet);
  }  printf("\n");

  // printf("%d\n", _debug_msg_sz);
}

decoder

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

#include <algorithm>
#include <bitset>
#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] = 100000;

  uint bs = 0;

  for (uint x = 0; x < L; x++)
  {
    if (X[x] & 1)
    {
      uint ind = (X[x] >> 1) & 0b11111;
      if (freq[ind] == 100000)
      {
        freq[ind] = X[x] >> 6;
      } else {
        freq[ind] += 0b100;
      }
    } 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];
  bitset<100> bit1, bit2;

  for (uint x = 0; x < s; x++) {
    if (freq[x] == 100000) continue;
    org_pos[freq[x]] = bytes[x];
    bit1[x] = 1;
    bit2[freq[x]] = 1;
  }

  for (uint a = 0; a < bs; a++) {
    if (bit1[a]) continue;
    for (uint b = 0; b < bs; b++) {
      if (bit2[b]) continue;
      org_pos[b] = bytes[a];
      break;
    }
    break;
  }

  /*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: 0 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 29
• Subtask 5: 0 / 19