Submission #389742

#	Time	Username	Problem	Language	Result	Execution time	Memory
389742		quickn	Parrots (IOI11_parrots)	C++14	98 / 100	11 ms	1336 KiB

encoder

#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;
    }
}

decoder

#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 (stderr)

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 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 17 / 19