Submission #207088

#	Time	Username	Problem	Language	Result	Execution time	Memory
207088		AlexLuchianov	Parrots (IOI11_parrots)	C++14	98 / 100	30 ms	1784 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <map>
#include <iostream>

void encode(int N, int M[])
{
  int i;
  int ptr = 0;
  std::map<int,int> code;

  for(i=0; i<N; i++){
    for(int j = 0; j < 8; j++) {
      if(0 < (M[i] & (1 << j)))
        code[ptr] = 1;
      ptr++;
    }
  }

  int cost = 0, change = 0;
  for(int i = 0; i < N * 8; i += 2){
    if(code[i] == 1)
      cost += 2;
    if(code[i + 1] == 1)
      cost++;
  }

  if(3 * N * 4 - cost < cost) {
    change = 1;
    send(0);
    send(0);
    send(0);
    send(0);
  }
  ptr = 0;

  for(int i = 0; i < N * 8; i += 2){
    if(change == 1) {
      code[i] ^= 1;
      code[i + 1] ^= 1;
    }
    if(code[i] == 1) {
      send(ptr);
      send(ptr);
    }
    if(code[i + 1] == 1)
      send(ptr);
    ptr++;
  }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <map>
#include <iostream>

void decode(int N, int L, int X[])
{
  std::map<int,int> code;
  std::map<int,int> frec;

  for(int i = 0; i < L; i++)
    frec[X[i]]++;
  int change = (4 <= frec[0]);
  if(change == 1)
    frec[0] -= 4;

  int ptr = 0;
  for(int i = 0; i < 8 * N; i += 2){
    if(2 <= frec[ptr])
      code[i] = 1;
    if(frec[ptr] % 2 == 1)
      code[i + 1] = 1;
    ptr++;
  }

  ptr = 0;
  for(int i = 0; i < N; i++){
    int number = 0;
    for(int j = 0; j < 8; j++){
      if((code[ptr] ^ change) == 1)
        number |= (1 << j);
      ptr++;
    }
    output(number);
  }
}

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