Submission #1174950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174950		iulia_morariu	Parrots (IOI11_parrots)	C++20	81 / 100	2820 ms	26996 KiB

encoder

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
// #include "decoder.h"
// #include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"
#define in  cin
#define out cout

using namespace std;
const int B = 10; // baza

// vector<int> ce_tr;
// void send(int nr){
//     ce_tr.push_back(nr);
// }

vector<int> operator/(vector<int> & a, int b){
    int t = 0;
    vector<int> c;
    for(int i = a.size() - 1; i >= 0; i--){
        t = t * B + a[i];
        c.push_back(t / b);
        t %= b;
    }
    reverse(c.begin(), c.end());
    while(!c.empty() && c.back() == 0) c.pop_back();
    return c;
}

vector<int> operator+(vector<int> & a, vector<int> & b){
    int t = 0;
    vector<int> sl;
    for(int i = 0; i < max(a.size(), b.size()) || t > 0; i++){
        if(i < a.size()) t += a[i];
        if(i < b.size()) t += b[i];
        sl.push_back(t % B);
        t /= B;
    }
    return sl;
}

vector<int> operator-(vector<int> a, vector<int> b){ // am grija ca a >= b
    vector<int> sl;
    for(int i = 0; i < a.size(); i++){
        if(i < b.size()) sl.push_back(a[i] - b[i]);
        else sl.push_back(a[i]);
        if(sl.back() < 0){
            sl[i] += B;
            a[i + 1]--;
        }
    }
    while(sl.size() > 1 && sl.back() == 0) sl.pop_back();
    return sl;
}

vector<int> operator*(vector<int> a, vector<int> b){
    vector<int> c(a.size() + b.size() - 1, 0);
    int t = 0;
    for(int i = 0; i < a.size(); i++){
        for(int j = 0; j < b.size(); j++){
            c[i + j] += a[i] * b[j];
        }
    }

    for(int i = 0; i <= a.size() + b.size() - 2 || t > 0; i++){
        if(i < c.size()){
            t += c[i];
            c[i] = t % B;
            t /= B;
        }else{
            c.push_back(t % B);
            t /= B;
        }
    }
    return c;
}

bool mai_mic_egal(vector<int> a, vector<int> b){
    if(a.size() != b.size()) return a.size() < b.size();
    for(int i = a.size() - 1; i >= 0; i--){
        if(a[i] != b[i]) return a[i] < b[i];
    }
    return a < b;
}

vector<int> dp[5 * 64 + 1][256];

void calculeaza_dp(int n){
    
    // dp[i][j] = cate siruri sunt de i elemente cu ultimul elemnt j
    for(int i = 0; i <= 5 * 64; i++){
        for(int j = 0; j <= 255; j++){
            dp[i][j].clear();
            dp[i][j].push_back(0);
        }
    }

    for(int j = 0; j <= 255; j++){
        dp[1][j][0] = 1;
    }

    for(int i = 2; i <= 5 * n; i++){
        for(int j = 0; j <= 255; j++){
            dp[i][j] = dp[i - 1][j];
            if(j > 0) dp[i][j] = dp[i][j] + dp[i][j - 1];
            // for(int k = 0; k <= j; k++){
            //     dp[i][j] = dp[i][j] + dp[i - 1][k];
            // }
        }
    }
}

void encode(int N, int M[]){
    vector<bool> b;
    for(int i = 0; i < N; i++){
        int cnt = 0;
        while(M[i]){
            b.push_back(M[i] % 2);
            M[i] /= 2;
            cnt++;
        }
        while(cnt < 8){ b.push_back(0); cnt++; }
    }

    // cout << "b : "; // bunbun
    // for(int i = 0; i < b.size(); i++) cout << b[i];
    // cout << '\n';

    vector<int> nr;
    nr.push_back(0);
    vector<int> P; P.push_back(1); // 2 ^ ceva
    vector<int> doi; doi.push_back(2); // 2

    for(int i = b.size() - 1; i >= 0; i--){
        if(b[i]) nr = nr + P;
        P = P * doi;
    }

    calculeaza_dp(N);
    // nr.clear();
    // nr.push_back(1);
    // cout << "nr : ";
    // for(int i = nr.size() - 1; i >= 0; i--) cout << nr[i];
    // cout << '\n';

    int last = 255;
    vector<int> sending; // ce send 
    for(int i = 5 * N; i >= 1; i--){
        // cout << "i = " << i << " nr = ";
        // for(int j = nr.size() - 1; j >= 0; j--) cout << nr[j];
        // cout << '\n';
        bool ch = 0;
        for(int c = 0; c <= last; c++){
            if(mai_mic_egal(nr, dp[i][c])){
                sending.push_back(c);
                last = c;
                ch = 1;
                break;
            }
            nr = nr - dp[i][c];
        }
    }
    reverse(sending.begin(), sending.end());
    // cout << "Osa send : ";
    // for(int i = 0; i < sending.size(); i++) cout << sending[i] << " ";
    // cout << '\n';
    for(int i = 0; i < sending.size(); i++) send( sending[i] );
}

// void decode(int N, int L, int X[]){
//     calculeaza_dp(N);
//     sort(X + 0, X + L);

//     // cout << "primesc X : ";
//     // for(int i = 0; i < L; i++) cout << X[i] << " ";
//     // cout << '\n';

//     // cout << "dp[2][0] = ";
//     // for(int k = dp[2][0].size() - 1; k >= 0; k--) cout << dp[2][0][k];
//     // cout << '\n';

//     vector<int> nr; nr.push_back(0);
//     for(int i = 1; i <= L; i++){
//         for(int j = 0; j < X[i - 1]; j++){
//             nr = nr + dp[i][j];
//         }
//     }

//     // cout << "nr : ";
//     // for(int i = nr.size() - 1; i >= 0; i--) cout << nr[i];
//     // cout << '\n';

//     vector<bool> b;
//     while(!nr.empty() && nr.back() > 0){
//         // cout << "nr : ";
//         // for(int i = nr.size() - 1; i >= 0; i--) cout << nr[i];
//         // cout << '\n';
//         b.push_back(nr[0] % 2);
//         nr = (nr / 2);
//     }
//     while(b.size() != 8 * N) b.push_back(0);
//     reverse(b.begin(), b.end());

//     // cout << "b : ";
//     // for(int i = 0; i < b.size(); i++) cout << b[i];
//     // cout << '\n';

//     vector<int> jucu;
//     for(int i = 0; i < b.size(); i += 8){
//         int x = 0;
//         for(int j = 0; j < 8; j++){
//             x = x + (1 << j) * b[i + j];
//         }
//         jucu.push_back(x);
//     }
//     // cout << "M este : ";
//     // for(int i = 0; i < jucu.size(); i++) cout << jucu[i] << " ";
//     // cout << '\n';
//     for(int i = 0; i < jucu.size(); i++) output(jucu[i]);
// }

// signed main(){
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);

//     // 254 0 0 2 1 255 253 49
//     int M[] = {254, 0, 0, 2, 1, 255, 253, 49};
//     encode(8, M);

//     int cee[ce_tr.size()];
//     for(int i = 0; i < ce_tr.size(); i++) cee[i] = ce_tr[i];
//     decode(8, ce_tr.size(), cee);

//     return 0;
// }

decoder

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
#include "decoder.h"
#include "decoderlib.h"
// #include "encoder.h"
// #include "encoderlib.h"
#define in  cin
#define out cout

using namespace std;
const int B = 10; // baza

// vector<int> ce_tr;
// void send(int nr){
//     ce_tr.push_back(nr);
// }

vector<int> operator/(vector<int> & a, int b){
    int t = 0;
    vector<int> c;
    for(int i = a.size() - 1; i >= 0; i--){
        t = t * B + a[i];
        c.push_back(t / b);
        t %= b;
    }
    reverse(c.begin(), c.end());
    while(!c.empty() && c.back() == 0) c.pop_back();
    return c;
}

vector<int> operator+(vector<int> & a, vector<int> & b){
    int t = 0;
    vector<int> sl;
    for(int i = 0; i < max(a.size(), b.size()) || t > 0; i++){
        if(i < a.size()) t += a[i];
        if(i < b.size()) t += b[i];
        sl.push_back(t % B);
        t /= B;
    }
    return sl;
}

vector<int> operator-(vector<int> a, vector<int> b){ // am grija ca a >= b
    vector<int> sl;
    for(int i = 0; i < a.size(); i++){
        if(i < b.size()) sl.push_back(a[i] - b[i]);
        else sl.push_back(a[i]);
        if(sl.back() < 0){
            sl[i] += B;
            a[i + 1]--;
        }
    }
    while(sl.size() > 1 && sl.back() == 0) sl.pop_back();
    return sl;
}

vector<int> operator*(vector<int> a, vector<int> b){
    vector<int> c(a.size() + b.size() - 1, 0);
    int t = 0;
    for(int i = 0; i < a.size(); i++){
        for(int j = 0; j < b.size(); j++){
            c[i + j] += a[i] * b[j];
        }
    }

    for(int i = 0; i <= a.size() + b.size() - 2 || t > 0; i++){
        if(i < c.size()){
            t += c[i];
            c[i] = t % B;
            t /= B;
        }else{
            c.push_back(t % B);
            t /= B;
        }
    }
    return c;
}

bool mai_mic_egal(vector<int> a, vector<int> b){
    if(a.size() != b.size()) return a.size() < b.size();
    for(int i = a.size() - 1; i >= 0; i--){
        if(a[i] != b[i]) return a[i] < b[i];
    }
    return a < b;
}

vector<int> dp[5 * 64 + 1][256];

void calculeaza_dp(int n){
    
    // dp[i][j] = cate siruri sunt de i elemente cu ultimul elemnt j
    for(int i = 0; i <= 5 * 64; i++){
        for(int j = 0; j <= 255; j++){
            dp[i][j].clear();
            dp[i][j].push_back(0);
        }
    }

    for(int j = 0; j <= 255; j++){
        dp[1][j][0] = 1;
    }

    for(int i = 2; i <= 5 * n; i++){
        for(int j = 0; j <= 255; j++){
            dp[i][j] = dp[i - 1][j];
            if(j > 0) dp[i][j] = dp[i][j] + dp[i][j - 1];
            // for(int k = 0; k <= j; k++){
            //     dp[i][j] = dp[i][j] + dp[i - 1][k];
            // }
        }
    }
}

// void encode(int N, int M[]){
//     vector<bool> b;
//     for(int i = 0; i < N; i++){
//         int cnt = 0;
//         while(M[i]){
//             b.push_back(M[i] % 2);
//             M[i] /= 2;
//             cnt++;
//         }
//         while(cnt < 8){ b.push_back(0); cnt++; }
//     }

//     // cout << "b : "; // bunbun
//     // for(int i = 0; i < b.size(); i++) cout << b[i];
//     // cout << '\n';

//     vector<int> nr;
//     nr.push_back(0);
//     vector<int> P; P.push_back(1); // 2 ^ ceva
//     vector<int> doi; doi.push_back(2); // 2

//     for(int i = b.size() - 1; i >= 0; i--){
//         if(b[i]) nr = nr + P;
//         P = P * doi;
//     }

//     calculeaza_dp(N);
//     // nr.clear();
//     // nr.push_back(1);
//     // cout << "nr : ";
//     // for(int i = nr.size() - 1; i >= 0; i--) cout << nr[i];
//     // cout << '\n';

//     int last = 255;
//     vector<int> sending; // ce send 
//     for(int i = 5 * N; i >= 1; i--){
//         // cout << "i = " << i << " nr = ";
//         // for(int j = nr.size() - 1; j >= 0; j--) cout << nr[j];
//         // cout << '\n';
//         bool ch = 0;
//         for(int c = 0; c <= last; c++){
//             if(mai_mic_egal(nr, dp[i][c])){
//                 sending.push_back(c);
//                 last = c;
//                 ch = 1;
//                 break;
//             }
//             nr = nr - dp[i][c];
//         }
//     }
//     reverse(sending.begin(), sending.end());
//     // cout << "Osa send : ";
//     // for(int i = 0; i < sending.size(); i++) cout << sending[i] << " ";
//     // cout << '\n';
//     for(int i = 0; i < sending.size(); i++) send( sending[i] );
// }

void decode(int N, int L, int X[]){
    calculeaza_dp(N);
    sort(X + 0, X + L);

    // cout << "primesc X : ";
    // for(int i = 0; i < L; i++) cout << X[i] << " ";
    // cout << '\n';

    // cout << "dp[2][0] = ";
    // for(int k = dp[2][0].size() - 1; k >= 0; k--) cout << dp[2][0][k];
    // cout << '\n';

    vector<int> nr; nr.push_back(0);
    for(int i = 1; i <= L; i++){
        for(int j = 0; j < X[i - 1]; j++){
            nr = nr + dp[i][j];
        }
    }

    // cout << "nr : ";
    // for(int i = nr.size() - 1; i >= 0; i--) cout << nr[i];
    // cout << '\n';

    vector<bool> b;
    while(!nr.empty() && nr.back() > 0){
        // cout << "nr : ";
        // for(int i = nr.size() - 1; i >= 0; i--) cout << nr[i];
        // cout << '\n';
        b.push_back(nr[0] % 2);
        nr = (nr / 2);
    }
    while(b.size() != 8 * N) b.push_back(0);
    reverse(b.begin(), b.end());

    // cout << "b : ";
    // for(int i = 0; i < b.size(); i++) cout << b[i];
    // cout << '\n';

    vector<int> jucu;
    for(int i = 0; i < b.size(); i += 8){
        int x = 0;
        for(int j = 0; j < 8; j++){
            x = x + (1 << j) * b[i + j];
        }
        jucu.push_back(x);
    }
    // cout << "M este : ";
    // for(int i = 0; i < jucu.size(); i++) cout << jucu[i] << " ";
    // cout << '\n';
    for(int i = 0; i < jucu.size(); i++) output(jucu[i]);
}

// signed main(){
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);

//     // 254 0 0 2 1 255 253 49
//     int M[] = {254, 0, 0, 2, 1, 255, 253, 49};
//     encode(8, M);

//     int cee[ce_tr.size()];
//     for(int i = 0; i < ce_tr.size(); i++) cee[i] = ce_tr[i];
//     decode(8, ce_tr.size(), cee);

//     return 0;
// }

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