oj.uz

Submission #191633

# Submission time Handle Problem Language Result Execution time Memory
191633 2020-01-15T03:48:27 Z kdh9949 Parrots (IOI11_parrots) C++17
100 / 100
 283 ms 167704 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <algorithm>
using namespace std;

static const int N = 256, M = 64;

struct BI_enc{
  int a[N], len;

  BI_enc(){
    len = 1;
    for(int i = 0; i < N; i++) a[i] = 0;
  }

  BI_enc(int n, int b[]){
    len = 1;
    for(int i = 0; i < n; i++){
      a[i] = b[i];
      if(a[i]) len = i + 1;
    }
  }

  BI_enc operator+(const BI_enc &o) const {
    BI_enc r;
    r.len = max(len, o.len);
    
    for(int i = 0, carry = 0; i < r.len; i++){
      r.a[i] = (a[i] + o.a[i] + carry) % N;
      carry = (a[i] + o.a[i] + carry) / N;
      if(r.len <= M && i == r.len - 1 && carry) r.a[r.len++] = 1;
    }

    return r;
  }

  bool operator<(const BI_enc &o) const {
    if(len != o.len) return (len < o.len);
    for(int i = len - 1; i >= 0; i--) if(a[i] != o.a[i]) return (a[i] < o.a[i]);
    return false;
  }
};

static BI_enc d[N + 1][5 * M + 1];
static int calced;

void calc_enc(int n){
  d[0][0].a[0] = 1;

  for(int i = 1; i <= N; i++){
    for(int j = 0; j <= 5 * n; j++){
      d[i][j] = d[i - 1][j];
      if(j) d[i][j] = d[i][j] + d[i][j - 1];
    }
  }
  calced = 1;
}

BI_enc num2cmb(BI_enc num, int n){
  BI_enc res, cur;
  int left = 5 * n;

  for(int i = 0; i < N; i++){
    while(left && !(num < cur + d[N - 1 - i][left])){
      cur = cur + d[N - 1 - i][left];
      res.a[i]++;
      left--;
    }
  }

  return res;
}

void encode(int n, int a[])
{
  if(!calced) calc_enc(n);
  
  BI_enc num(n, a);
  BI_enc cmb = num2cmb(num, n);
  
  for(int i = 0; i < N; i++) for(int j = 0; j < cmb.a[i]; j++) send(i);
}

#include "decoder.h"
#include "decoderlib.h"
#include <algorithm>
using namespace std;

static const int N = 256, M = 64;

struct BI_dec{
  int a[N], len;

  BI_dec(){
    len = 1;
    for(int i = 0; i < N; i++) a[i] = 0;
  }

  BI_dec operator+(const BI_dec &o) const {
    BI_dec r;
    r.len = max(len, o.len);
    
    for(int i = 0, carry = 0; i < r.len; i++){
      r.a[i] = (a[i] + o.a[i] + carry) % N;
      carry = (a[i] + o.a[i] + carry) / N;
      if(r.len <= M && i == r.len - 1 && carry) r.a[r.len++] = 1;
    }

    return r;
  }

  bool operator<(const BI_dec &o) const {
    if(len != o.len) return (len < o.len);
    for(int i = len - 1; i >= 0; i--) if(a[i] != o.a[i]) return (a[i] < o.a[i]);
    return false;
  }
};

static BI_dec d[N + 1][5 * M + 1];
static int calced;

void calc_dec(int n){
  d[0][0].a[0] = 1;

  for(int i = 1; i <= N; i++){
    for(int j = 0; j <= 5 * n; j++){
      d[i][j] = d[i - 1][j];
      if(j) d[i][j] = d[i][j] + d[i][j - 1];
    }
  }
  calced = 1;
}

BI_dec cmb2num(BI_dec cmb, int n){
  BI_dec res;
  int left = 5 * n;

  for(int i = 0; i < N; i++){
    for(int j = 0; j < cmb.a[i]; j++){
      res = res + d[N - 1 - i][left--];
    }
  }

  return res;
}

void decode(int n, int l, int x[])
{
  if(!calced) calc_dec(n);
  
  BI_dec cmb;
  for(int i = 0; i < l; i++) cmb.a[x[i]]++;
  BI_dec res = cmb2num(cmb, n);
  
  for(int i = 0; i < n; i++) output(res.a[i]);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 166708 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 167512 KB Output is correct
2 Correct 169 ms 167352 KB Output is correct
3 Correct 175 ms 167352 KB Output is correct
4 Correct 179 ms 167312 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 167288 KB Output is correct
2 Correct 155 ms 167312 KB Output is correct
3 Correct 178 ms 167456 KB Output is correct
4 Correct 180 ms 167352 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 167408 KB Output is correct
2 Correct 180 ms 167520 KB Output is correct
3 Correct 187 ms 167344 KB Output is correct
4 Correct 203 ms 167272 KB Output is correct
5 Correct 206 ms 167496 KB Output is correct
6 Correct 212 ms 167408 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 167488 KB Output is correct - P = 5.000000
2 Correct 209 ms 167464 KB Output is correct - P = 5.000000
3 Correct 212 ms 167608 KB Output is correct - P = 5.000000
4 Correct 242 ms 167456 KB Output is correct - P = 5.000000
5 Correct 273 ms 167704 KB Output is correct - P = 5.000000
6 Correct 279 ms 167632 KB Output is correct - P = 5.000000
7 Correct 283 ms 167704 KB Output is correct - P = 5.000000