Submission #712383

#	Time	Username	Problem	Language	Result	Execution time	Memory
712383		BackNoob	Parrots (IOI11_parrots)	C++14	0 / 100	2064 ms	32896 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
using namespace std;


string getstring(int x)
{
    string res = "";
    while(x) {
        res += char('0' + x % 10);
        x /= 10;
    }
    reverse(all(res));
    return res;
}

int getval(string tmp)
{
    int res = 0;
    for(auto it : tmp) res = res * 10 + it - '0';
    return res;
}

string add(string &a, string &b)
{
    string res = "";
    int i = sz(a) - 1;
    int j = sz(b) - 1;
    int carry = 0;
    while(i >= 0 || j >= 0) {
        int x, y;
        if(i >= 0) x = a[i] - '0';
        else x = 0;
        if(j >= 0) y = b[j] - '0';
        else y = 0;

        int tmp = (x + y + carry) % 10;
        carry = (x + y + carry) / 10;
        res += char('0' + tmp);
        --i;
        --j;
    }

    if(carry) res += char('1');
    reverse(all(res));
    return res;
}

string sub(string &a, string &b)
{
    string res = "";
    int i = sz(a) - 1;
    int j = sz(b) - 1;
    int carry = 0;
    while(i >= 0 || j >= 0) {
        int x, y;
        if(i >= 0) x = a[i] - '0';
        else x = 0;
        if(j >= 0) y = b[j] - '0';
        else y = 0;

        x -= carry;
        if(x < y) {
            x += 10;
            carry = 1;
        }
        else carry = 0;
        res += char('0' + (x - y));
        --i;
        --j;
    }

    while(res.back() == '0') res.pop_back();
    if(sz(res) == 0) res = "0";

    reverse(all(res));
    return res;
}

string Div(string &a, int b)
{
    string res = "";
    int cur = 0;
    for(int i = 0; i < sz(a); i++) {
        cur = cur * 10 + a[i] - '0';
        if(sz(res) > 0 || (sz(res) == 0 && cur / b > 0)) 
            res += char('0' + cur / b);
        cur %= b;
    }
    return res;
}

int Mod(string &a, int b)
{
    int cur = 0;
    for(auto it : a) {
        cur = cur * 10 + (it - '0');
        cur %= b;
    }
    return cur;
}

int cmp(string &a, string &b)
{
    if(sz(a) == sz(b)) {
        for(int i = 0; i < sz(a); i++) {
            if(a[i] == b[i]) continue;
            if(a[i] < b[i]) return -1;
            return 1;
        }

        return 0;
    }
    if(sz(a) < sz(b)) return -1;
    return 1;

}

void encode(int n, int a[])
{
    string x = "0";
    for(int i = 0; i < n; i++) {
        string tmp = getstring(a[i]);
        string t = x;
        for(int j = 1; j < 256; j++) x = add(x, t);
        x = add(x, tmp);
    }

    vector<vector<string>> choose;
    choose.resize(507, vector<string>(300));

    for(int i = 0; i <= 500; i++) {
        choose[i][0] = "1";
        for(int j = 1; j <= min(256, i); j++) {
            choose[i][j] = add(choose[i - 1][j], choose[i - 1][j - 1]);
        }
    }

    string lim = "1";
    for(int i = 1; i <= 8 * n; i++) {
        lim = add(lim, lim);
    }

    int k = 1;
    while(cmp(choose[256 + k][256], lim) == -1) ++k;

    int sta = 0;
    for(int i = 1; i <= k; i++) {
        for(int j = sta; j <= 255; j++) {
            string way = choose[255 - j + (k - i)][255 - j];
            int tmp = cmp(x, way);
            if(tmp <= 0) {
                send(j); 
                sta = j;
                break;
            }
            else {
                x = sub(x, way);
            }
        }
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
using namespace std;


string getstring(int x)
{
    string res = "";
    while(x) {
        res += char('0' + x % 10);
        x /= 10;
    }
    reverse(all(res));
    return res;
}

int getval(string tmp)
{
    int res = 0;
    for(auto it : tmp) res = res * 10 + it - '0';
    return res;
}

string add(string &a, string &b)
{
    string res = "";
    int i = sz(a) - 1;
    int j = sz(b) - 1;
    int carry = 0;
    while(i >= 0 || j >= 0) {
        int x, y;
        if(i >= 0) x = a[i] - '0';
        else x = 0;
        if(j >= 0) y = b[j] - '0';
        else y = 0;

        int tmp = (x + y + carry) % 10;
        carry = (x + y + carry) / 10;
        res += char('0' + tmp);
        --i;
        --j;
    }

    if(carry) res += char('1');
    reverse(all(res));
    return res;
}

string sub(string &a, string &b)
{
    string res = "";
    int i = sz(a) - 1;
    int j = sz(b) - 1;
    int carry = 0;
    while(i >= 0 || j >= 0) {
        int x, y;
        if(i >= 0) x = a[i] - '0';
        else x = 0;
        if(j >= 0) y = b[j] - '0';
        else y = 0;

        x -= carry;
        if(x < y) {
            x += 10;
            carry = 1;
        }
        else carry = 0;
        res += char('0' + (x - y));
        --i;
        --j;
    }

    while(res.back() == '0') res.pop_back();
    if(sz(res) == 0) res = "0";

    reverse(all(res));
    return res;
}

string Div(string &a, int b)
{
    string res = "";
    int cur = 0;
    for(int i = 0; i < sz(a); i++) {
        cur = cur * 10 + a[i] - '0';
        if(sz(res) > 0 || (sz(res) == 0 && cur / b > 0)) 
            res += char('0' + cur / b);
        cur %= b;
    }
    return res;
}

int Mod(string &a, int b)
{
    int cur = 0;
    for(auto it : a) {
        cur = cur * 10 + (it - '0');
        cur %= b;
    }
    return cur;
}

int cmp(string &a, string &b)
{
    if(sz(a) == sz(b)) {
        for(int i = 0; i < sz(a); i++) {
            if(a[i] == b[i]) continue;
            if(a[i] < b[i]) return -1;
            return 1;
        }

        return 0;
    }
    if(sz(a) < sz(b)) return -1;
    return 1;

}

void decode(int n, int l, int a[])
{   
    vector<int> v;
    for(int i = 0; i < l; i++) v.pb(a[i]);
    sort(all(v));
    
    vector<vector<string>> choose;
    choose.resize(507, vector<string>(300));

    for(int i = 0; i <= 500; i++) {
        choose[i][0] = "1";
        for(int j = 1; j <= min(256, i); j++) {
            choose[i][j] = add(choose[i - 1][j], choose[i - 1][j - 1]);
        }
    }

    string res = "1";

    int sta = 0;
    for(int i = 1; i <= sz(v); i++) {
        int x = v[i - 1];
        for(int j = sta; j < x; j++) {
            res = add(res, choose[(255 - j) + (sz(v) - i)][(255 - j)]);
        }
        sta = x;
    }

    vector<int> ans;
    for(int i = 1; i <= n; i++) {
        ans.pb(Mod(res, 256));
        res = Div(res, 256);
    }

    reverse(all(ans));
    for(auto it : ans) output(it);
}

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