oj.uz

Submission #712453

# Submission time Handle Problem Language Result Execution time Memory
712453 2023-03-18T19:37:04 Z BackNoob Parrots (IOI11_parrots) C++14
100 / 100
 798 ms 34720 KB 
#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;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int BASE = 1e9;
const int LOG = 20;

struct bigint{
    int arr[23];
    bigint(){
        memset(arr, 0, sizeof(arr));
    }
} choose[607][306];


bigint add(bigint a, bigint b)
{
    bigint res;
    for(int i = 0; i < 21; i++) {
        int tmp = a.arr[i] + b.arr[i];
        res.arr[i + 1] += tmp / BASE;
        res.arr[i] += tmp % BASE;
    }
    return res;
}

bigint sub(bigint a, bigint b)
{
    bigint res;
    for(int i = 0; i < 21; i++) {
        while(a.arr[i] < b.arr[i]) {
            a.arr[i] += BASE;   
            a.arr[i + 1]--;
        }
        res.arr[i] = a.arr[i] - b.arr[i];
    }   

    return res;
}

bigint Div(bigint a, int b)
{
    bigint res;
    ll rem = 0;
    for(int i = 20; i >= 0; i--) {
        res.arr[i] = (ll) (1LL * BASE * rem + a.arr[i]) / b;
        rem = (rem * BASE + a.arr[i]) % b;
    }
    return res;
}

int Mod(bigint a, int b)
{
    ll res = 0;
    for(int i = 20; i >= 0; i--) {
        res = 1LL * res * BASE + a.arr[i];
        res %= b;
    }
    return res;
}

int cmp(bigint a, bigint b)
{
    for(int i = 20; i >= 0; i--) {
        if(a.arr[i] == b.arr[i]) continue;
        if(a.arr[i] < b.arr[i]) return -1;
        return 1;
    }
    return 0;
}


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

    bigint t;
    t.arr[0] = 1;
    x = add(x, t);

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

    bigint lim;
    lim.arr[0] = 1;
    for(int i = 1; i <= n * 8; i++) {
        lim = add(lim, lim);
    }

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

    int sta = 0;
    for(int i = 1; i <= k; i++) {
        for(int j = sta; j <= 255; j++) {
            bigint 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);
            }
        }
    }
}
#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;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int BASE = 1e9;
const int LOG = 20;


struct bigint{
    int arr[23];
    bigint(){
        memset(arr, 0, sizeof(arr));
    }
} choose[607][306];


bigint add(bigint a, bigint b)
{
    bigint res;
    for(int i = 0; i < 21; i++) {
        int tmp = a.arr[i] + b.arr[i];
        res.arr[i + 1] += tmp / BASE;
        res.arr[i] += tmp % BASE;
    }
    return res;
}

bigint sub(bigint a, bigint b)
{
    bigint res;
    for(int i = 0; i < 21; i++) {
        while(a.arr[i] < b.arr[i]) {
            a.arr[i] += BASE;   
            a.arr[i + 1]--;
        }
        res.arr[i] = a.arr[i] - b.arr[i];
    }   

    return res;
}

bigint Div(bigint a, int b)
{
    bigint res;
    ll rem = 0;
    for(int i = 20; i >= 0; i--) {
        res.arr[i] = (ll) (1LL * BASE * rem + a.arr[i]) / b;
        rem = (rem * BASE + a.arr[i]) % b;
    }
    return res;
}

int Mod(bigint a, int b)
{
    ll res = 0;
    for(int i = 20; i >= 0; i--) {
        res = 1LL * res * BASE + a.arr[i];
        res %= b;
    }
    return res;
}

int cmp(bigint a, bigint b)
{
    for(int i = 20; i >= 0; i--) {
        if(a.arr[i] == b.arr[i]) continue;
        if(a.arr[i] < b.arr[i]) return -1;
        return 1;
    }
    return 0;
}

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));
    
    for(int i = 0; i <= 530; i++) {
        choose[i][0].arr[0] = 1;
        for(int j = 1; j <= min(256, i); j++) {
            choose[i][j] = add(choose[i - 1][j], choose[i - 1][j - 1]);
        }
    }

    bigint res;

    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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 34116 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 665 ms 34432 KB Output is correct
2 Correct 642 ms 34448 KB Output is correct
3 Correct 636 ms 34444 KB Output is correct
4 Correct 629 ms 34572 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 34332 KB Output is correct
2 Correct 702 ms 34468 KB Output is correct
3 Correct 570 ms 34448 KB Output is correct
4 Correct 600 ms 34672 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 599 ms 34468 KB Output is correct
2 Correct 665 ms 34448 KB Output is correct
3 Correct 611 ms 34384 KB Output is correct
4 Correct 619 ms 34464 KB Output is correct
5 Correct 628 ms 34488 KB Output is correct
6 Correct 696 ms 34476 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 658 ms 34436 KB Output is correct - P = 1.812500
2 Correct 641 ms 34464 KB Output is correct - P = 2.468750
3 Correct 638 ms 34484 KB Output is correct - P = 2.515152
4 Correct 690 ms 34664 KB Output is correct - P = 3.300000
5 Correct 798 ms 34720 KB Output is correct - P = 3.850000
6 Correct 653 ms 34716 KB Output is correct - P = 4.031746
7 Correct 689 ms 34644 KB Output is correct - P = 4.093750