Submission #1323782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1323782		nikaa123	Parrots (IOI11_parrots)	C++20	0 / 100	15 ms	18264 KiB

encoder

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

int base = 1e9;

struct bigint{
  vector <int> d;

  bigint(){} bigint(int res) {
    if (res == 0) d.emplace_back(0);
    while (res > 0) {
      d.emplace_back(res%base);
      res /= base;
    } 
  }

  void add(const bigint& res) {
    int carry = 0;
    for (int i = 0; i < max(res.d.size(),d.size()) || carry; i++) {
      if (i == d.size()) d.emplace_back(0);
      int cur = (res.d.size() > i ? res.d[i]:0) + carry + d[i];
      d[i] = cur%base;
      carry = cur/base;
    }
  }

  void remove(const bigint& res) {
    int borrow = 0;
    for (int i = 0; i < res.d.size() || borrow; i++) {
      int cur = d[i]-(res.d.size() > i ? res.d[i]:0)-borrow;
      if (cur < 0) {
        borrow = 1;
        cur += base;
      } else {
        borrow = 0;
      }
      d[i] = cur;
    }
    while (!d.empty() && d.back() == 0) d.pop_back();
  }

  void multily(int res) {
    if (res == 0) {
      d = {0};
      return;
    }
    int carry = 0;
    for (int i = 0; i < d.size() || carry; i++) {
      if (i == d.size()) d.emplace_back(0);
      long long cur = d[i]*res + carry;
      d[i] = cur % base;
      carry = cur/base;
    }
  }

  int divide(int res) {
    if (res == 0) return 0;
    long long rem = 0;
    for (int i = d.size()-1; i >= 0; i--) {
      long long cur = d[i] + rem*base;
      d[i] = cur/res;
      rem = cur%res;
    }
    while (!d.empty() && d.back() == 0) d.pop_back();
    return rem;
  }

  bool operator<=(const bigint& res) {
    if (d.size() != res.d.size()) return d.size() < res.d.size();
    for (int i = d.size()-1; i >= 0; i--) {
      if (d[i] != res.d[i]) return d[i] < res.d[i];
    }
    return true;
  }
  bool operator<(const bigint& res) {
    if (d.size() != res.d.size()) return d.size() < res.d.size();
    for (int i = d.size()-1; i >= 0; i--) {
      if (d[i] != res.d[i]) return d[i] < res.d[i];
    }
    return false;
  }

};

bigint c[700][700];
int L = 0;

int precomp(int n) {
  c[0][0] = bigint(1);
  for (int i = 1; i <= 600; i++) {
    c[i][0] = bigint(1);
    for (int j = 1; j <= 256 && j <= i; j++) {
      c[i][j] = c[i-1][j];
      c[i][j].add(c[i-1][j-1]);
    }
  }

  bigint res = bigint(1);
  for (int i = 0; i < n; i++) {
    res.multily(256);
  }
  while (c[L+256][256] < res) {
    L++;
  }

}

void encode(int N, int M[]) {
  precomp(N);

  bigint val(0);
  for (int i = N-1; i >= 0; i--) {
    val.multily(256);
    bigint res(M[i]);
    val.add(res);
  }

  int cur = L;
  for (int x = 0; x <= 255; x++) {
    int rem = 256-x;
    for (int k = 0; k <= cur; k++) {
      int nn = (cur-k)+rem-1;
      int kk = rem-1;

      if (val < c[nn][kk]) {
        for (int i = 0; i < k; i++) send(x);
        cur -= k;
        break;
      } else {
        val.remove(c[nn][kk]);
      }
    }
  }

  while (cur--) send(255);

}

decoder

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

int base = 1e9;

struct bigint{
  vector <int> d;

  bigint(){} bigint(int res) {
    if (res == 0) d.emplace_back(0);
    while (res > 0) {
      d.emplace_back(res%base);
      res /= base;
    } 
  }

  void add(const bigint& res) {
    int carry = 0;
    for (int i = 0; i < max(res.d.size(),d.size()) || carry; i++) {
      if (i == d.size()) d.emplace_back(0);
      int cur = (res.d.size() > i ? res.d[i]:0) + carry + d[i];
      d[i] = cur%base;
      carry = cur/base;
    }
  }

  void remove(const bigint& res) {
    int borrow = 0;
    for (int i = 0; i < res.d.size() || borrow; i++) {
      int cur = d[i]-(res.d.size() > i ? res.d[i]:0)-borrow;
      if (cur < 0) {
        borrow = 1;
        cur += base;
      } else {
        borrow = 0;
      }
      d[i] = cur;
    }
    while (!d.empty() && d.back() == 0) d.pop_back();
  }

  void multily(int res) {
    if (res == 0) {
      d = {0};
      return;
    }
    int carry = 0;
    for (int i = 0; i < d.size() || carry; i++) {
      if (i == d.size()) d.emplace_back(0);
      long long cur = d[i]*res + carry;
      d[i] = cur % res;
      carry = cur/res;
    }
  }

  int divide(int res) {
    if (res == 0) return 0;
    int rem = 0;
    for (int i = d.size()-1; i >= 0; i--) {
      long long cur = d[i] + rem*base;
      d[i] = cur/base;
      rem = cur%base;
    }
    while (!d.empty() && d.back() == 0) d.pop_back();
    return rem;
  }

  bool operator<=(const bigint& res) {
    if (d.size() != res.d.size()) return d.size() < res.d.size();
    for (int i = d.size()-1; i >= 0; i--) {
      if (d[i] != res.d[i]) return d[i] < res.d[i];
    }
    return true;
  }
  bool operator<(const bigint& res) {
    if (d.size() != res.d.size()) return d.size() < res.d.size();
    for (int i = d.size()-1; i >= 0; i--) {
      if (d[i] != res.d[i]) return d[i] < res.d[i];
    }
    return false;
  }

};

bigint c[700][700];
int L = 0;

int precomp(int n) {
  c[0][0] = bigint(1);
  for (int i = 1; i <= 600; i++) {
    c[i][0] = bigint(1);
    for (int j = 1; j <= 256 && j <= i; j++) {
      c[i][j] = c[i-1][j];
      c[i][j].add(c[i-1][j-1]);
    }
  }

}

void decode(int N, int L, int X[]){
  int cnt[256] = {0};
  for (int i = 0; i < L; i++) cnt[X[i]]++;
  bigint v = 0;
  int cur = L;
  for (int x = 0; x <= 255; x++) {
    int k = cnt[x];
    for (int i = 0; i < k; i++) {
      int remf = cur-i;
      int remt = 256-x;
      bigint ways = c[remf+remt-1][remt-1];
      v.add(ways);
    }
    cur -= k;
  } 
  for (int i = 0; i < N; i++) {
    int b = v.divide(256);
    output(b);
  }
}

Compilation message (stderr)

# 1번째 컴파일 단계

encoder.cpp: In function 'int precomp(int)':
encoder.cpp:108:1: warning: no return statement in function returning non-void [-Wreturn-type]
  108 | }
      | ^

# 2번째 컴파일 단계

decoder.cpp: In function 'int precomp(int)':
decoder.cpp:100:1: warning: no return statement in function returning non-void [-Wreturn-type]
  100 | }
      | ^

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