oj.uz

Submission #14846

# Submission time Handle Problem Language Result Execution time Memory
14846 2015-06-30T16:11:08 Z minsu Parrots (IOI11_parrots) C++14
100 / 100
 12 ms 2400 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;

static const int R = 20;
static lld cache[R+1][R+1];
static bool chk;
static lld H(int n, int r){
  if(!chk){
    for(int i=0;i<=R;i++)
      for(int j=0;j<=R;j++)
        cache[i][j] = !j ? 1: !i ? 0 : cache[i-1][j]+cache[i][j-1];
    chk = 1;
  }
  return cache[n][r];
}

//     257 ** 4 = 4362470401L
// H ( 17, 20 ) = 7307872110L
void encode(int N, int M[])
{
  lld num = 0; vector<lld> packet;
  for(int i=0; i<N; i++){
    num = num * 257 + ( i < N ? M[i] + 1 : 0 );
    if( i%4 == 3 || i == N-1 ) { packet.push_back( num ); num=0; }
  }
  // _ 0 1 2 3 4 .. 15
  for(int i=0; i<packet.size(); i++){
    lld p = packet[i]; int r = R;
    for(int j=1; j<=17; j++){
      int k;
      for(k = r; k>=0; k--){
        if( H(17-j, r-k) <= p ) p-= H(17-j, r-k);
        else break;
      } r-=k;
      while( (j-1) && k--) send(i*16 + j-2);
    }
  }
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;

static const int R = 20;
static lld cache[R+1][R+1];
static bool chk;
static lld H(int n, int r){
  if(!chk){
    for(int i=0;i<=R;i++)
      for(int j=0;j<=R;j++)
        cache[i][j] = !j ? 1: !i ? 0 : cache[i-1][j]+cache[i][j-1];
    chk = 1;
  }
  return cache[n][r];
}

static int cnt[16][17];
void decode(int N, int L, int X[])
{
  int n = 0;
  memset(cnt, 0, sizeof cnt);
  for(int i=0; i<L; i++){
    int x = X[i];
    cnt[x/16][x%16+1]++;
    cnt[x/16][0]--;
    n = max(n, x/16);
  }
  for(int i=0; i<=n; i++){
    lld num = 0LL; cnt[i][0]+=R;
    int r = R;
    for(int j=1; j<=17; j++){
      int k;
      for(k = r; k>cnt[i][j-1]; k--)
        num+= H(17-j, r-k);
      r-=k;
    }
    vector<int> ans;
    while(num){
      ans.push_back(num%257);
      num/=257;
    }
    for(auto it = ans.rbegin(); it!= ans.rend(); ++it)
      if(*it!=0) output(*it-1);
  }
}

Compilation message

encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:30:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<packet.size(); i++){
                ~^~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 752 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1848 KB Output is correct
2 Correct 5 ms 1848 KB Output is correct
3 Correct 5 ms 2152 KB Output is correct
4 Correct 6 ms 2152 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2152 KB Output is correct
2 Correct 5 ms 2152 KB Output is correct
3 Correct 5 ms 2152 KB Output is correct
4 Correct 6 ms 2152 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2152 KB Output is correct
2 Correct 5 ms 2152 KB Output is correct
3 Correct 7 ms 2152 KB Output is correct
4 Correct 7 ms 2152 KB Output is correct
5 Correct 8 ms 2168 KB Output is correct
6 Correct 8 ms 2168 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2168 KB Output is correct - P = 5.000000
2 Correct 11 ms 2168 KB Output is correct - P = 5.000000
3 Correct 9 ms 2168 KB Output is correct - P = 4.939394
4 Correct 10 ms 2168 KB Output is correct - P = 4.920000
5 Correct 11 ms 2320 KB Output is correct - P = 5.000000
6 Correct 11 ms 2400 KB Output is correct - P = 4.952381
7 Correct 12 ms 2400 KB Output is correct - P = 5.000000