oj.uz

Submission #360865

# Submission time Handle Problem Language Result Execution time Memory
360865 2021-01-28T07:19:39 Z 79brue Parrots (IOI11_parrots) C++14
100 / 100
 9 ms 1532 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace{
    int n;
    ll arr[102];
    ll comb[52][52];

    int const1[] = {5, 10, 15, 20};
    int const2[] = {16+5, 16+10, 16+15, 16+20};
}

void encode(int N, int M[]){
    comb[0][0] = 1LL;
    for(int i=1; i<=50; i++){
        comb[i][0] = comb[i][i] = 1LL;
        for(int j=1; j<i; j++){
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
        }
    }

    n = N;
    memset(arr, 0, sizeof(arr));
    for(int i=0; i<n; i++){
        int tmp = M[i];
        arr[i] = tmp;
    }

    for(int c=0; c<n; c+=4){
        int tConst = (c+4 < n ? 4 : n-c);
        int c1 = const1[tConst-1];
        int c2 = const2[tConst-1];

        ll par = (arr[c+3]<<24LL) + (arr[c+2]<<16LL) + (arr[c+1]<<8LL) + arr[c] + 1;
        vector<int> vec;
        int leftK = c1;
        for(int i=0; i<c2 && leftK; i++){
            if(par <= comb[c2-1-i][leftK]){
                continue;
            }
            par -= comb[c2-1-i][leftK];
            vec.push_back(i);
            leftK--;
        }
        for(int i=0; i<c1; i++) vec[i] -= i;
        for(int i=0; i<c1; i++){
            if(vec[i] < 16) send((c/4) * 16 + vec[i]);
        }
    }
}

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

using namespace std;

typedef long long ll;

namespace {
    int n, k;
    ll arr[102];
    ll code[200002];
    ll comb[52][52];
    int const1[] = {5, 10, 15, 20};
    int const2[] = {16+5, 16+10, 16+15, 16+20};
}

void decode(int N, int L, int X[]){
    comb[0][0] = 1;
    for(int i=1; i<=50; i++){
        comb[i][0] = comb[i][i] = 1;
        for(int j=1; j<i; j++){
            comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
        }
    }

    memset(arr, 0, sizeof(arr));
    n = N, k = L;
    for(int i=0; i<k; i++) code[i] = X[i];
    sort(code, code+k);

    int pnt = 0;
    for(int c=0; c<n; c+=4){
        int tConst = (c+4 < n ? 4 : n-c);
        int c1 = const1[tConst-1];
        int c2 = const2[tConst-1];

        vector<int> codes;
        while(pnt < k && code[pnt]/16 == c/4){
            codes.push_back(code[pnt]%16);
            pnt++;
        }
        while((int)codes.size() < c1) codes.push_back(16);
        for(int i=0; i<c1; i++) codes[i] += i;

        ll parm = 0;
        for(int i=0; i<c1; i++){
            parm += comb[c2-1-codes[i]][c1-i];
        }

        arr[c+3] = parm >> 24;
        arr[c+2] = (parm >> 16) & 255;
        arr[c+1] = (parm >> 8) & 255;
        arr[c] = parm & 255;
    }

    for(int i=0; i<n; i++){
        output(arr[i]);
    }
}

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1132 KB Output is correct
2 Correct 3 ms 1136 KB Output is correct
3 Correct 3 ms 1300 KB Output is correct
4 Correct 3 ms 1304 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1260 KB Output is correct
2 Correct 3 ms 1308 KB Output is correct
3 Correct 3 ms 1140 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1440 KB Output is correct
2 Correct 3 ms 1140 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 5 ms 1280 KB Output is correct
5 Correct 5 ms 1280 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1268 KB Output is correct - P = 5.000000
2 Correct 5 ms 1292 KB Output is correct - P = 4.937500
3 Correct 5 ms 1156 KB Output is correct - P = 4.969697
4 Correct 9 ms 1532 KB Output is correct - P = 4.860000
5 Correct 9 ms 1440 KB Output is correct - P = 4.850000
6 Correct 9 ms 1440 KB Output is correct - P = 4.888889
7 Correct 9 ms 1444 KB Output is correct - P = 4.875000