제출 #769393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
769393		MilosMilutinovic	앵무새 (IOI11_parrots)	C++14	0 / 100	2089 ms	51576 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;

const int C = 160;
const int B = 256;
const int N = 5 * 64;

struct NumBig {
    int d[C];
    void init() { for (int i = 0; i < C; i++) d[i] = 0; }
    NumBig() { /* init(); */ }
    void print() {
        for (int i = 0; i < 50; i++) {
            printf("%d ", d[i]);
        }
        printf("\n");
    }
};
NumBig const operator + (NumBig a, NumBig b) {
    NumBig res;
    res.d[C - 1] = -1e9;
    for (int i = 0; i < C; i++) {
        res.d[i] += a.d[i] + b.d[i];
        while (res.d[i] >= 10) {
            res.d[i] -= 10;
            res.d[i + 1] += 1;
        }
    }
    res.d[C - 1] = 0;
    return res;
}
NumBig const operator * (NumBig a, int c) {
    //printf("mnozim sa %d\n", c);
    NumBig res;
    res.d[C - 1] = -1e9;
    for (int i = 0; i < C; i++) {
        res.d[i] += a.d[i] * c;
        while (res.d[i] >= 10) {
            res.d[i] -= 10;
            res.d[i + 1] += 1;
        }
    }
    res.d[C - 1] = 0;
    return res;
}
bool const operator >= (NumBig a, NumBig b) {
    for (int i = C - 1; i >= 0; i--) {
        if (a.d[i] != b.d[i]) {
            return a.d[i] > b.d[i];
        }
    }
    return true;
}
NumBig const operator - (NumBig a, NumBig b) {
    NumBig res;
    for (int i = 0; i < C; i++) {
        res.d[i] = a.d[i] - b.d[i];
        while (res.d[i] < 0) {
            res.d[i] += 10;
            a.d[i + 1] -= 1;
        }
    }
    return res;
}

NumBig pd[N][B];

void dp_make(int n) {
    for (int i = 0; i < B; i++) {
        pd[n - 1][i].init();
        pd[n - 1][i].d[0] = 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        NumBig sum;
        for (int j = B - 1; j >= 0; j--) {
            sum = sum + pd[i + 1][j];
            pd[i][j] = sum;
        }
    }
}

void encode(int N, int M[])
{
    dp_make(5 * N);
    NumBig val, pw;
    pw.d[0] = 1;
    for (int i = 0; i < N; i++) {
        val = val + (pw * M[i]);
        pw = pw * B;
    }
    NumBig ONE;
    ONE.d[0] = 1;
    val = val + ONE;
//    printf("DECODE VAL = "); val.print();
    int lst = 0;
//    printf("SEQUENCE\n");
    NumBig cur_sum;
    for (int i = 0; i < 5 * N; i++) {
        for (int j = lst; j < B; j++) {
            if (cur_sum + pd[i][j] >= val) {
                lst = j;
//                printf("%d ", lst);
                send(lst);
                break;
            }
            cur_sum = cur_sum + pd[i][j];
        }
    }
//    printf("\n");
//    sort(M, M + N);
//    dp_make(N);
//    NumBig val;
//    int lst = 0;
//    for (int i = 0; i < N; i++) {
//        while (lst != M[i]) {
//            val = val + pd[i][lst];
//            lst += 1;
//        }
//    }
//    printf("SEQ VAL = ");
//    val.print();
//  int i;
//  for(i=0; i<N; i++)
//    send(M[i]);
}

/*
8
1 0 1 0 0 1 1 0
*/

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;

const int C = 160;
const int B = 256;
const int N = 5 * 64;

struct BigNum {
    int d[C];
    void init() { for (int i = 0; i < C; i++) d[i] = 0; }
    BigNum() {  /* init(); */ }
    void print() {
        for (int i = 0; i < 50; i++) {
            printf("%d ", d[i]);
        }
        printf("\n");
    }
};
BigNum const operator + (BigNum a, BigNum b) {
    BigNum res;
    res.d[C - 1] = -1e9;
    for (int i = 0; i < C; i++) {
        res.d[i] += a.d[i] + b.d[i];
        while (res.d[i] >= 10) {
            res.d[i] -= 10;
            res.d[i + 1] += 1;
        }
    }
    res.d[C - 1] = 0;
    return res;
}
BigNum const operator * (BigNum a, int c) {
//    printf("mnozim sa %d\n", c);
    BigNum res;
    res.d[C - 1] = -1e9;
    for (int i = 0; i < C; i++) {
        res.d[i] += a.d[i] * c;
        while (res.d[i] >= 10) {
            res.d[i] -= 10;
            res.d[i + 1] += 1;
        }
    }
    res.d[C - 1] = 0;
    return res;
}
bool const operator >= (BigNum a, BigNum b) {
    for (int i = C - 1; i >= 0; i--) {
        if (a.d[i] != b.d[i]) {
            return a.d[i] > b.d[i];
        }
    }
    return true;
}
BigNum const operator - (BigNum a, BigNum b) {
    BigNum res;
    for (int i = 0; i < C; i++) {
        res.d[i] = a.d[i] - b.d[i];
        while (res.d[i] < 0) {
            res.d[i] += 10;
            a.d[i + 1] -= 1;
        }
    }
    return res;
}

BigNum dp[N][B];

void make_dp(int n) {
    for (int i = 0; i < B; i++) {
        dp[n - 1][i].init();
        dp[n - 1][i].d[0] = 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        BigNum sum;
        for (int j = B - 1; j >= 0; j--) {
            sum = sum + dp[i + 1][j];
            dp[i][j] = sum;
        }
    }
}

void decode(int N, int L, int X[])
{
    sort(X, X + L);
//    printf("got decode seq = ");
//    for (int i = 0; i < L; i++)
//        printf("%d ", X[i]);
//    printf("\n");
    make_dp(L);
    BigNum val;
    int lst = 0;
    for (int i = 0; i < L; i++) {
        while (lst != X[i]) {
            val = val + dp[i][lst];
            lst += 1;
        }
    }
//    printf("SEQ VAL = ");
//    val.print();
    vector<int> ans;
    for (int i = N - 1; i >= 0; i--) {
        BigNum pw;
        pw.d[0] = 1;
        for (int j = 0; j < i; j++) {
            pw = pw * B;
        }
        ans.push_back(0);
        BigNum nm = pw;
        while (val >= nm) {
            ans.back() += 1;
            nm = nm + pw;
        }
        nm = nm - pw;
        val = val - nm;
    }
    reverse(ans.begin(), ans.end());
    for (int x : ans)
        output(x);
//  int i, b;
//  for(i=0; i<L; i++) {
//    b = X[i];
//    output(b);
//  }
}

/*
8
1 0 1 0 0 1 1 0

10
1 1 2 1 2 3 1 7 10 9

*/

• Subtask 1: 0 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 29
• Subtask 5: 0 / 19