제출 #887370

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887370		gustavo_d	앵무새 (IOI11_parrots)	C++17	98 / 100	12 ms	1624 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;

const int MX = 7;
bool nxt(vector<int> &v) {
  if (v == vector<int> (MX, 4)) return false;
  bool eq = true;
  for (int i=0; i<MX-1; i++) {
    if (v[i] != v[i+1]) eq = false;
  }

  int diff = -1;
  if (eq) diff = 0;
  else {
    for (int i=1; i<MX; i++) {
      if (v[i] != v[i-1]) diff = i;
    }
  }

  v[diff]++;
  for (int i=diff+1; i<MX; i++) v[i] = 0;

  return true;
};

void encode(int N, int M[])
{
  vector <int> v(MX, 0);
  vector<pair<int,int>> tmp(N);
  for (int i=0; i<N; i++) tmp[i] = {M[i], i};
  sort(tmp.begin(), tmp.end());
  int cnt = 0;
  for (int idx=0; idx<N; idx++) {
    while (cnt != tmp[idx].first) {
      nxt(v);
      cnt++;
    }
    // coloca tmp[idx]
    int id = tmp[idx].second;
    for (int tag : v) {
      if (tag != 0) {
        int val = id << 2;
        val += tag - 1;
        send(val);
      }
    }
  }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;

const int MX = 7;
bool next(vector<int> &v) {
  if (v == vector<int> (MX, 4)) return false;
  bool eq = true;
  for (int i=0; i<MX-1; i++) {
    if (v[i] != v[i+1]) eq = false;
  }

  int diff = -1;
  if (eq) diff = 0;
  else {
    for (int i=1; i<MX; i++) {
      if (v[i] != v[i-1]) diff = i;
    }
  }

  v[diff]++;
  for (int i=diff+1; i<MX; i++) v[i] = 0;

  return true;
};

bool cmp(int a, int b) {
  return (a & 3) > (b & 3);
}

void decode(int N, int L, int X[])
{
  sort(X, X+L, cmp); // id e depois segmento maior por menor

  vector<int> vec(MX, 0);
  map<vector<int>, int> mp;
  for (int cnt=0; cnt<=255; cnt++, next(vec)) {
    mp[vec] = cnt;
  }

  vector<vector<int>> vals(N);
  for(int i=0; i<L; i++) {
    int id = (X[i] >> 2);
    int val = ((X[i]) & 3); // 00000011
    vals[id].push_back(val+1);
  }
  for (int i=0; i<N; i++) {
    while (vals[i].size() != MX) {
      vals[i].push_back(0);
    }
    output(mp[vals[i]]);
  }
}

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