oj.uz

Submission #103760

# Submission time Handle Problem Language Result Execution time Memory
103760 2019-04-02T12:56:47 Z wxh010910 Parrots (IOI11_parrots) C++17
100 / 100
 13 ms 1792 KB 
#include <bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"

using namespace std;

void encode(int N, int M[]) {
  vector<vector<long long>> dp(21, vector<long long>(16));
  for (int i = 0; i < 16; ++i) {
    dp[0][i] = 1;
  }
  for (int i = 1; i < 21; ++i) {
    for (int j = 0; j < 16; ++j) {
      for (int k = j; k < 16; ++k) {
        dp[i][j] += dp[i - 1][k];
      }
    }
  }
  vector<long long> sum(21);
  for (int i = 1; i < 21; ++i) {
    sum[i] = sum[i - 1] + dp[i][0];
  }
  vector<int> a(M, M + N);
  while (a.size() % 4) {
    a.push_back(0);
    ++N;
  }
  for (int i = 0; i < N; i += 4) {
    long long state = 0;
    for (int j = 0; j < 4; ++j) {
      state |= (long long) a[i + j] << (j * 8);
    }
    int len = 0;
    while (state >= sum[len]) {
      ++len;
    }
    state -= sum[len - 1];
    int last = 0;
    for (int j = len - 1; ~j; --j) {
      long long sum = 0;
      for (int k = last; k < 16; ++k) {
        if (state < sum + dp[j][k]) {
          send(i * 4 + k);
          state -= sum;
          last = k;
          break;
        }
        sum += dp[j][k];
      }
    }
  }
}

#include <bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"

using namespace std;

void decode(int N, int L, int X[]) {
  vector<vector<long long>> dp(21, vector<long long>(16));
  for (int i = 0; i < 16; ++i) {
    dp[0][i] = 1;
  }
  for (int i = 1; i < 21; ++i) {
    for (int j = 0; j < 16; ++j) {
      for (int k = j; k < 16; ++k) {
        dp[i][j] += dp[i - 1][k];
      }
    }
  }
  vector<long long> sum(21);
  for (int i = 1; i < 21; ++i) {
    sum[i] = sum[i - 1] + dp[i][0];
  }
  int n = N;
  while (N % 4) {
    ++N;
  }
  for (int i = 0; i < N; i += 4) {
    long long state = 0;
    vector<int> sorted;
    for (int j = 0; j < L; ++j) {
      if (X[j] / 16 == i / 4) {
        sorted.push_back(X[j] % 16);
      }
    }
    sort(sorted.begin(), sorted.end());
    int len = (int) sorted.size();
    int last = 0;
    for (int j = len - 1; ~j; --j) {
      for (int k = last; k < sorted[len - 1 - j]; ++k) {
        state += dp[j][k];
      }
      last = sorted[len - 1 - j];
    }
    state += sum[len - 1];
    for (int j = 0; j < 4; ++j) {
      if (i + j < n) {
        output((state >> (j * 8)) & 255);
      }
    }
  }
}

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
18.0 / 18.0

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

Subtask #4
29.0 / 29.0

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

Subtask #5
19.0 / 19.0

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