oj.uz

Submission #389742

# Submission time Handle Problem Language Result Execution time Memory
389742 2021-04-14T12:37:47 Z quickn Parrots (IOI11_parrots) C++14
98 / 100
 11 ms 1336 KB 
#include <bits/stdc++.h>

#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"

using namespace std;

typedef unsigned long long i64;
const int MAX_LENGTH = 40;

void encode(int N, int M[]) {
    vector<pair<int, int>> list(N, make_pair(0, 0));
	for (int i = 0; i < N; i++) {
        list[i] = make_pair(M[i], i);
    }
    vector<i64> msg_block;
    for (int i = 0; i < N/8; i++) {
        i64 msg = 0;
        for (int j = 0; j < 8; j++) {
            msg = msg*256 + static_cast<i64>(list[i*8 + j].first);
        }
        msg_block.push_back(msg);
    }
    i64 msg = 0;
    for (int i = 8*(N/8); i < N; i++) {
        msg = msg*256 + static_cast<i64>(list[i].first);
    }
    if (N % 8 != 0)
    msg_block.push_back(msg);
    vector<vector<i64>> dp(MAX_LENGTH, vector<i64>(32, 0));
    for (int j = 0; j < 32; j++)
        dp[0][j] = 1;
    for (int i = 1; i < MAX_LENGTH; i++) {
        for (int j = 0; j < 32; j++)
            if (j > 0)
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            else
                dp[i][j] = dp[i-1][j];
    }
    int cnt = 0;
    vector<int> q;
    for (auto msg: msg_block) {
        i64 m = msg;
        int i = MAX_LENGTH-1;
        int j = 30;
        vector<int> arr;
        while (i >= 0) {
            bool non = false;
            while (m > 0 && j > 0) {
                if (dp[i][j-1] == m) {
                    m -= dp[i][j-1];
                    arr.push_back(j);
                    non = true;
                    break;
                } else if (dp[i][j-1] < m) {
                    m -= dp[i][j-1];
                    arr.push_back(j+1);
                    non = true;
                    break;
                }
                j--;
            }
            if (!non) { arr.push_back(0); }
            i--;
        }
        for (auto a: arr) {
            send(cnt*32 + a);
        }
        cnt += 1;
    }
}
#include <bits/stdc++.h>

#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"

using namespace std;

typedef unsigned long long i64;
const int MAX_LENGTH = 40;

void decode(int N, int L, int X[]) {
        vector<vector<i64>> dp(MAX_LENGTH, vector<i64>(32, 0));
    for (int j = 0; j < 32; j++)
        dp[0][j] = 1;
    for (int i = 1; i < MAX_LENGTH; i++) {
        for (int j = 0; j < 32; j++)
            if (j > 0)
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            else
                dp[i][j] = dp[i-1][j];
    }
    vector<vector<int>> recover(static_cast<int>(ceil(static_cast<long double>(N)/8.0)));
    for (int i = 0; i < L; i++) {
        recover[X[i] / 32].push_back(X[i] % 32);
    }
    for (int i = 0; i < recover.size(); i++) {
        sort(recover[i].begin(), recover[i].end(), greater<int>());
        i64 nth = 0;
        for (int j = 0; j < recover[i].size(); j++) {
            if (recover[i][j] == 0)
                break;
            if (j == recover[i].size()-1 || recover[i][j+1] == 0) {
                nth += dp[recover[i].size()-j-1][recover[i][j]-1];
            } else {
                nth += dp[recover[i].size()-j-1][recover[i][j]-2];
            }
        }
        vector<int> out;
        if (i == recover.size()-1 && N % 8 != 0) {
            for (int j = 8*(N/8); j < N; j++) {
                out.push_back(nth % 256);
                nth /= 256;
            }
        } else {
            for (int j = 0; j < 8; j++) {
                out.push_back(nth % 256);
                nth /= 256;
            }
        }
        for (int j = out.size()-1; j >= 0; j--)
            output(out[j]);// out[j] << " ";
    }
}

Compilation message

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i = 0; i < recover.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~
decoder.cpp:31:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for (int j = 0; j < recover[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
decoder.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             if (j == recover[i].size()-1 || recover[i][j+1] == 0) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~
decoder.cpp:41:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if (i == recover.size()-1 && N % 8 != 0) {
      |             ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1012 KB Output is correct
2 Correct 4 ms 1020 KB Output is correct
3 Correct 3 ms 1032 KB Output is correct
4 Correct 3 ms 1020 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1012 KB Output is correct
2 Correct 3 ms 1148 KB Output is correct
3 Correct 4 ms 1132 KB Output is correct
4 Correct 4 ms 1028 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1012 KB Output is correct
2 Correct 3 ms 1020 KB Output is correct
3 Correct 5 ms 1156 KB Output is correct
4 Correct 6 ms 1176 KB Output is correct
5 Correct 6 ms 1164 KB Output is correct
6 Correct 6 ms 1172 KB Output is correct

Subtask #5
17.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1020 KB Output is correct - P = 5.000000
2 Correct 7 ms 1168 KB Output is correct - P = 5.000000
3 Partially correct 6 ms 1176 KB Output is partially correct - P = 6.060606
4 Partially correct 11 ms 1312 KB Output is partially correct - P = 5.600000
5 Partially correct 10 ms 1320 KB Output is partially correct - P = 5.333333
6 Partially correct 10 ms 1336 KB Output is partially correct - P = 5.079365
7 Correct 9 ms 1244 KB Output is correct - P = 5.000000