oj.uz

Submission #14794

# Submission time Handle Problem Language Result Execution time Memory
14794 2015-06-24T07:49:05 Z gs14004 Parrots (IOI11_parrots) C++14
100 / 100
 276 ms 143456 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <cstring>
using namespace std;

struct bignum{
    short arr[100];
    void init(char i){
        memset(arr,0,sizeof(arr));
        arr[0] = i;
    }
};

bignum operator+(bignum a, bignum b){
    for (int i=0; i<100; i++) {
        a.arr[i] += b.arr[i];
        if(a.arr[i] >= 256) {
            a.arr[i] -= 256;
            a.arr[i+1] ++;
        }
    }
    return a;
}

bool operator<(bignum a, bignum b){
    for (int i=99; i>=0; i--) {
        if(a.arr[i] < b.arr[i]) return 1;
        if(a.arr[i] > b.arr[i]) return 0;
    }
    return 0;
}

bignum bino[600][600];
int precalc;


void encode(int N, int* M){
    if(!precalc){
        for (int i=0; i<600; i++) {
            bino[i][0].init(1);
            for (int j=1; j<=i; j++) {
                bino[i][j].init(0);
                bino[i][j] = bino[i-1][j] + bino[i-1][j-1];
            }
            for (int j=i+1; j<600; j++) {
                bino[i][j].init(0);
            }
        }
        precalc = 1;
    }
    bignum base, t;
    t.init(0);
    for (int i=0; i<N; i++) {
        t.arr[i] = M[i];
    }
    base.init(0);
    t = t + base;
    base.init(0);
    int length = 255 + 5 * N;
    for(int i=0; i<5*N; i++){
        while (t < bino[length-1][5 * N - i] + base) {
            length--;
        }
        send(5 * N + 255 - length - i - 1);
        base = base + bino[length-1][5 * N - i];
        length--;
    }
}
#include "decoder.h"
#include "decoderlib.h"
#include <algorithm>
#include <cstring>
using namespace std;

struct bignum{
    short arr[100];
    void init(char i){
        memset(arr,0,sizeof(arr));
        arr[0] = i;
    }
};

bignum operator+(bignum a, bignum b){
    for (int i=0; i<100; i++) {
        a.arr[i] += b.arr[i];
        if(a.arr[i] >= 256) {
            a.arr[i] -= 256;
            a.arr[i+1] ++;
        }
    }
    return a;
}

bool operator<(bignum a, bignum b){
    for (int i=99; i>=0; i--) {
        if(a.arr[i] < b.arr[i]) return 1;
        if(a.arr[i] > b.arr[i]) return 0;
    }
    return 0;
}

int precalc;
bignum bino[600][600];

void decode(int N, int L, int X[])
{
    if(!precalc){
        for (int i=0; i<600; i++) {
            bino[i][0].init(1);
            for (int j=1; j<=i; j++) {
                bino[i][j].init(0);
                bino[i][j] = bino[i-1][j] + bino[i-1][j-1];
            }
            for (int j=i+1; j<600; j++) {
                bino[i][j].init(0);
            }
        }
        precalc = 1;
    }
    sort(X,X+L);
    bignum ret;
    ret.init(0);
    for (int i=0; i<L; i++) {
        ret = ret + bino[5 * N + 255 - X[i] - i - 2][5 * N - i];
    }
    for (int i=0; i<N; i++) {
        output(ret.arr[i]);
    }
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 141696 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 142792 KB Output is correct
2 Correct 240 ms 142792 KB Output is correct
3 Correct 246 ms 143064 KB Output is correct
4 Correct 247 ms 143064 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 143112 KB Output is correct
2 Correct 237 ms 143112 KB Output is correct
3 Correct 242 ms 143112 KB Output is correct
4 Correct 247 ms 143112 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 271 ms 143112 KB Output is correct
2 Correct 243 ms 143112 KB Output is correct
3 Correct 246 ms 143112 KB Output is correct
4 Correct 276 ms 143200 KB Output is correct
5 Correct 246 ms 143328 KB Output is correct
6 Correct 246 ms 143328 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 143328 KB Output is correct - P = 5.000000
2 Correct 245 ms 143328 KB Output is correct - P = 5.000000
3 Correct 267 ms 143328 KB Output is correct - P = 5.000000
4 Correct 255 ms 143328 KB Output is correct - P = 5.000000
5 Correct 256 ms 143328 KB Output is correct - P = 5.000000
6 Correct 262 ms 143328 KB Output is correct - P = 5.000000
7 Correct 255 ms 143456 KB Output is correct - P = 5.000000