oj.uz

답안 #515983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
515983 2022-01-20T09:01:26 Z 600Mihnea 앵무새 (IOI11_parrots) C++17
100 / 100
 9 ms 1352 KB 
#pragma once
#include "encoder.h"
#include "encoderlib.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;


void encode(int n, int __message[]) {

  const ll INF = (ll) 1e18;
  int CNT[4] = {5, 10, 15, 20};

  int START[4];
  for (int i = 0; i < 4; i++) {
    START[i] = CNT[i] + 15;
  }

  vector<vector<ll>> comb(100, vector<ll> (100, 0));
  for (int i = 0; i < 100; i++) {
    comb[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      comb[i][j] = min(INF, comb[i - 1][j] + comb[i - 1][j - 1]);
    }
  }

  function<ll(int)> getvalue = [&] (int i) {
    if (0 <= i && i < n) {
      return __message[i];
    }
    return 0;
  };

  function<vector<int>(int, int, ll)> write = [&] (int CNT, int START, ll x) {
    vector<int> sol;
    int j = CNT;
    for (int i = START; i >= 0 && j >= 1; i--) {
      ll current = comb[i][j];
      if (x >= current) {
        x -= current;
        sol.push_back(START - i - (int) sol.size());
        j--;
      }
    }
    assert((int) sol.size() == CNT);
    assert(x == 0);
    return sol;
  };

  for (int l = 0; l < n; l += 4) {
    int k = min(4, n - l) - 1;
    ll num = getvalue(l) + getvalue(l + 1) * 256 + getvalue(l + 2) * 256 * 256 + getvalue(l + 3) * 256 * 256 * 256;
    vector<int> guys = write(CNT[k], START[k], num);
    for (auto &x : guys) {
      assert(0 <= x && x <= 16);
      if (x == 16) {
        continue;
      }
      send((l / 4) * 16 + x);
    }
  }
}


#pragma once
#include "decoder.h"
#include "decoderlib.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void decode(int n, int L, int guys[]) {

  const ll INF = (ll) 1e18;
  int CNT[4] = {5, 10, 15, 20};

  int START[4];
  for (int i = 0; i < 4; i++) {
    START[i] = CNT[i] + 15;
  }

  vector<vector<ll>> comb(100, vector<ll> (100, 0));
  for (int i = 0; i < 100; i++) {
    comb[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      comb[i][j] = min(INF, comb[i - 1][j] + comb[i - 1][j - 1]);
    }
  }

  function<vector<int>(int, int, ll)> write = [&] (int CNT, int START, ll x) {
    vector<int> sol;
    int j = CNT;
    for (int i = START; i >= 0 && j >= 1; i--) {
      ll current = comb[i][j];
      if (x >= current) {
        x -= current;
        sol.push_back(START - i - (int) sol.size());
        j--;
      }
    }
    assert((int) sol.size() == CNT);
    assert(x == 0);
    return sol;
  };


  sort(guys, guys + L);

  int top = 0;

  for (int l = 0; l < n; l += 4) {
    int k = min(4, n - l) - 1;
    vector<int> inds;

    for (int j = 0; j < CNT[k]; j++) {
      int val;
      if (top < L && guys[top] / 16 == l / 4) {

        val = guys[top++] % 16;
      } else {
        val = 16;
      }
      int i = START[k] - j - val;
      inds.push_back(i);
    }
    sort(inds.begin(), inds.end());
    int j = CNT[k];
    ll num = 0;
    for (int i = START[k]; i >= 0 && j >= 1; i--) {
      ll current = comb[i][j];
      assert(!inds.empty());
      if (i == inds.back()) {
        inds.pop_back();
        num += current;
        j--;
      }
    }

    vector<ll> sol;
    sol.push_back(num % 256), num /= 256;
    sol.push_back(num % 256), num /= 256;
    sol.push_back(num % 256), num /= 256;
    sol.push_back(num % 256), num /= 256;

    sol.resize(k + 1);

    for (auto &x : sol) {
      output(x);
    }
  }
}

Compilation message

encoder.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

decoder.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 880 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1132 KB Output is correct
2 Correct 3 ms 1140 KB Output is correct
3 Correct 4 ms 1144 KB Output is correct
4 Correct 4 ms 1136 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1140 KB Output is correct
2 Correct 3 ms 1196 KB Output is correct
3 Correct 3 ms 1140 KB Output is correct
4 Correct 3 ms 1140 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1140 KB Output is correct
2 Correct 3 ms 1140 KB Output is correct
3 Correct 3 ms 1156 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1228 KB Output is correct
6 Correct 5 ms 1292 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1140 KB Output is correct - P = 5.000000
2 Correct 5 ms 1284 KB Output is correct - P = 4.937500
3 Correct 5 ms 1288 KB Output is correct - P = 4.969697
4 Correct 6 ms 1344 KB Output is correct - P = 4.860000
5 Correct 9 ms 1352 KB Output is correct - P = 4.850000
6 Correct 8 ms 1316 KB Output is correct - P = 4.888889
7 Correct 8 ms 1320 KB Output is correct - P = 4.875000