oj.uz

Submission #908334

# Submission time Handle Problem Language Result Execution time Memory
908334 2024-01-16T11:20:18 Z heavylightdecomp Parrots (IOI11_parrots) C++14
100 / 100
 170 ms 109128 KB 
#include "encoder.h"
#include "encoderlib.h"
#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define vt vector
#define pb push_back
#define X first
#define Y second
using pii = pair<int,int>;
#define debug(x) do\
{auto _x=x; cerr<<#x<<" = "<<_x<<'\n';}while(0);
#define f0r(i,a,b) for(auto i=(a);i<(b);i++)
#define r0f(i,a,b) for(auto i=(a);i>=(b);i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define cerr while(0) cerr
//BUG: forgot to squeeze memory limit
//Stars and bars
//320 elements, 255 splitting points
//C(575, 255)
//from [0, 256)
//Convert bits into big integer
//be careful of leading 0s in decoder
//Find R-th combination: C(n,k,R)
//then sweep thru, unchosen elements = d
//chosen elements -> d++
//bug: chosen elements don't count towards total
//account for leading 0s
//use binary search lemma

//encoding: message -> (str append) bits -> (roll) order number
//-> (swipe + myror) chosen -> (splay) sorted sequence


// 100 * 9 bits
namespace {
const long long base = 1e9;
using ll = vt<int>;
//just make sure not a multiple of 5
const int digits = 27;
ll itov(int k) {
    vt<int> res (digits);
    res[digits-1] = k;
    return res;
}
vt<vt<ll>> cdp (600, vt<ll> (600, itov(-1)));
ostream& operator<<(ostream &lol, const ll &a) {
    bool IS_BIGNUM = sz(a) == digits;
    int lz = 0;
    if(IS_BIGNUM) {
        while(lz < sz(a) and a[lz] == 0) lz++; //BUG: almost segfaulted
    }
    //BUG: size of a instead of digits
    f0r(i,lz,sz(a)) {
        if(i == lz) lol << a[i] << ' ';
        else lol << a[i] << ' ';
    }
    if(lz >= sz(a) and lz != 0) lol << 0;
    return lol;
}
ll operator+(const ll &a, const ll &b) {
    ll c (digits);
    int carry = 0;
    r0f(i,digits-1,0) {
        long long sum = (a[i] + b[i] + carry);
        c[i] = sum % base;
        carry = sum / base;
    }
    // debug(a) debug(b) debug(c)
    return c;
}
ll operator-(const ll &a, const ll &b) {
    assert(a >= b);
    ll c (digits);
    int carry = 0;
    r0f(i,digits-1,0) {
        long long diff = (a[i] - b[i] - carry);
        int nc = 0;
        while(diff < 0) nc++, diff += base;
        c[i] = diff;
        //BUG: forgot to set c[i] = diff
        carry = nc;
    }
    // debug(a)
    // debug(b)
    // debug(c);
    return c;
}
ll operator/(const ll &a, int b) { //short division
    ll res (digits);
    int carry = 0;
    f0r(i,0,digits) {
        int ds = carry * base + a[i];
        res[i] = ds / b;
        carry = ds % b;
    }
    // debug(a) debug(res)
    return res;
}

ll comb(int n, int k) {
    if(k == 0) return itov(1);
    if(n == 0) return itov(0);
    if(cdp[n][k] != itov(-1)) return cdp[n][k];
    return cdp[n][k] = comb(n-1,k-1) + comb(n-1,k); 
}
//BUG: RE = Infinite recursion
//Also, don't use directly
void swipe(int n, int k, ll R, vt<int> &ans) {
    if(n == 0 or k == 0) return;
    // debug(n) debug(k) debug(R)
    ll a = comb(n-1,k);
    ll b = comb(n-1,k-1);
    // debug(a) debug(b)
    // assert(R <= (a+b)); currently buggy??
    // if(R <= a) {
    //     swipe(n-1,k,R,ans);
    // } else {
    //     swipe(n-1,k-1,R-a,ans);
    //     ans.pb(n-1); //0-indexing business
    // }
    assert(R <= (a+b));
    // debug(R)
    if(R <= b) {
        // debug("I chose") debug(n) debug(k)
        ans.pb(n-1);
        swipe(n-1,k-1,R,ans);
    } else {
        // debug("I didn't choose") debug(n) debug(k)
        swipe(n-1,k,R-b,ans);
    }
}
//This function should work
vt<int> myror(int n, int k, ll R) {
    vt<int> ans;
    swipe(n, k, R, ans);
    f0r(i,0,sz(ans)) {
        ans[i] = n-1-ans[i];
    }
    // debug(n) debug(k) debug(R)
    // debug(ans);
    return ans;
}
vt<int> splay(vt<int> co, int N) {
    debug("splay")
    const int sbars = 5*N + 255;
    vt<bool> chose (sbars);
    f0r(i,0,sz(co)) {
        assert(co[i] < sbars);
        chose[co[i]] = 1;
    }
    vt<int> res;
    int d = 0;
    f0r(i,0,sbars) {
        if(chose[i]) {
            d++;
        } else {
            res.pb(d);
        }
    }
    return res;
}
//decoding: sorted sequence -> (while loop and cur diff) chosen -> (guess binary search, div2) order number
//->(division roll method) bits -> (pad zeroes and stoi spam) message
ll inv(vt<int> a, int N, int K) {
    ll res = itov(0);
    assert(sz(a) == K);
    f0r(i,0,sz(a)) {
        int prev = i == 0 ? -1 : a[i-1];
        f0r(s,prev+1, a[i]) {
            res = res + comb(N-1-s, K-i-1);
        }
    }
    res = res + itov(1);
    return res;
}
void mydec(signed msz, signed N, signed xs[]) {
    sort(xs,xs+N);
    int ck = 255;
    int cn = N + 255;
    debug(cn) debug(ck);
    vt<int> chose; //0,1 array
    int c_walk = 0;
    f0r(i,0,N) {
        while(c_walk != xs[i]) c_walk++, chose.pb(1);
        chose.pb(0);
    }
    //BUG: mixed up order of operations LMAO
    //need to account for leading zeroes before constructing need, otherwise useless
    //edge case: ending 1s
    while(c_walk != 255) c_walk++, chose.pb(1);

    vt<int> need; //chosen elements
    f0r(i,0,sz(chose)) {
        if(chose[i]) {
            need.pb(i);
        }
    }
    
    // ll lo = itov(1), hi = itov(1), ord = itov(-1);
    // f0r(_,0,8*65) { //repeated doublings???
    //     hi = hi + hi;
    // }
    //binary search on order number
    // auto check = [&](ll wow) -> bool {
    //     //BUG: check if wow is even in the order number range
    //     if(wow > comb(cn, ck)) {
    //         return false;
    //     }
    //     vt<int> cur = myror(cn, ck, wow);
    //     if(cur <= need) {
    //         return true;
    //     } else {
    //         return false;
    //     }
    // };
    // debug(need);
    // while(lo <= hi) {
    //     ll mid = (lo+hi)/2;
    //     // debug(lo) debug(hi) debug(mid)
    //     // debug(mid+itov(1));
    //     // debug(mid-itov(1));
    //     if(check(mid)) {
    //         lo = mid+itov(1);
    //         ord = mid;
    //     } else {
    //         hi = mid-itov(1);
    //     }
    // }
    // if(myror(cn,ck,ord+itov(6)) == need) {
    //     debug("WTF");
    // }
    // assert(myror(cn,ck,ord) == need);
    // debug(ord);
    ll ord = inv(need, cn, ck);
    //BUG: order number + 1
    ll pay = ord - itov(1);
    string bits;
    while(pay != itov(0)) { //BUG: Inf loop here
        if(pay[digits-1] % 2 == 1) {
            bits += '1';
        } else {
            bits += '0';
        }
        //BUG: lmao forgot to set pay = pay/2
        pay = pay / 2;
    }
    while(sz(bits) != 8 * msz) { //bit string
        bits += '0';
    }
    reverse(all(bits));
    assert(sz(bits) % 8 == 0);
    vt<int> ans;
    debug("DECODING BITS")
    debug(bits);
    for(int ptr = 0; ptr < sz(bits); ptr += 8) {
        string block = bits.substr(ptr, 8);
        int ayy = stoi(block, nullptr, 2);
        ans.pb(ayy);
    }
    debug("I THINK...")
    for(int x : ans) {
        cerr << x << ' ';
        output(x);
    }
    cerr << '\n';
}
void myenc(signed N, signed M[]) {
    // cdp = vt<vt<ll>> (600, vt<ll> (600, -1));
    // assert(N == 8);
    string bits;
    //load input bit and trick
    //BUG: highest significant bit first, lmao
    f0r(i,0,N) {
        r0f(b,7,0) {
            if(M[i] & (1 << b)) {
                bits += '1';
            } else {
                bits += '0';
            }
        }
    }
    debug("ENCODING BITS")
    debug(bits);
    ll ord = itov(0);
    ll roll = itov(1);
    debug("ayo")
    r0f(i,sz(bits)-1,0) {
        if(bits[i] == '1') {
            ord = ord + roll;
        }
        roll = roll + roll;
    }
    ord = ord + itov(1); //BUG: 0 case is bad
    debug(ord);
    //bug: forgot to + 255
    vt<int> co = myror(5*N + 255, 255, ord);
    // debug(ord);
    // swipe(575,255,ord,co);
    // debug(co);
    debug(co);
    vt<int> ans = splay(co, N);
    assert(sz(ans) == 5*N);
    debug("here's my answer");
    for(int x : ans) {
        cerr << x << ' ';
    }
    cerr << '\n';
    for(int x : ans) {
        send(x);
    }
}
};
void encode(signed N, signed M[]) {
    myenc(N, M);
}
// void decode(signed msz, signed N, signed xs[]) {
//     mydec(msz, N, xs);    
// }
#include "encoder.h"
#include "encoderlib.h"
#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define vt vector
#define pb push_back
#define X first
#define Y second
using pii = pair<int,int>;
#define debug(x) do\
{auto _x=x; cerr<<#x<<" = "<<_x<<'\n';}while(0);
#define f0r(i,a,b) for(auto i=(a);i<(b);i++)
#define r0f(i,a,b) for(auto i=(a);i>=(b);i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define cerr while(0) cerr
//BUG: forgot to squeeze memory limit
//Stars and bars
//320 elements, 255 splitting points
//C(575, 255)
//from [0, 256)
//Convert bits into big integer
//be careful of leading 0s in decoder
//Find R-th combination: C(n,k,R)
//then sweep thru, unchosen elements = d
//chosen elements -> d++
//bug: chosen elements don't count towards total
//account for leading 0s
//use binary search lemma

//encoding: message -> (str append) bits -> (roll) order number
//-> (swipe + myror) chosen -> (splay) sorted sequence


// 100 * 9 bits
namespace {
const long long base = 1e9;
using ll = vt<int>;
//just make sure not a multiple of 5
const int digits = 27;
ll itov(int k) {
    vt<int> res (digits);
    res[digits-1] = k;
    return res;
}
vt<vt<ll>> cdp (600, vt<ll> (600, itov(-1)));
ostream& operator<<(ostream &lol, const ll &a) {
    bool IS_BIGNUM = sz(a) == digits;
    int lz = 0;
    if(IS_BIGNUM) {
        while(lz < sz(a) and a[lz] == 0) lz++; //BUG: almost segfaulted
    }
    //BUG: size of a instead of digits
    f0r(i,lz,sz(a)) {
        if(i == lz) lol << a[i] << ' ';
        else lol << a[i] << ' ';
    }
    if(lz >= sz(a) and lz != 0) lol << 0;
    return lol;
}
ll operator+(const ll &a, const ll &b) {
    ll c (digits);
    int carry = 0;
    r0f(i,digits-1,0) {
        long long sum = (a[i] + b[i] + carry);
        c[i] = sum % base;
        carry = sum / base;
    }
    // debug(a) debug(b) debug(c)
    return c;
}
ll operator-(const ll &a, const ll &b) {
    assert(a >= b);
    ll c (digits);
    int carry = 0;
    r0f(i,digits-1,0) {
        long long diff = (a[i] - b[i] - carry);
        int nc = 0;
        while(diff < 0) nc++, diff += base;
        c[i] = diff;
        //BUG: forgot to set c[i] = diff
        carry = nc;
    }
    // debug(a)
    // debug(b)
    // debug(c);
    return c;
}
ll operator/(const ll &a, int b) { //short division
    ll res (digits);
    int carry = 0;
    f0r(i,0,digits) {
        int ds = carry * base + a[i];
        res[i] = ds / b;
        carry = ds % b;
    }
    // debug(a) debug(res)
    return res;
}

ll comb(int n, int k) {
    if(k == 0) return itov(1);
    if(n == 0) return itov(0);
    if(cdp[n][k] != itov(-1)) return cdp[n][k];
    return cdp[n][k] = comb(n-1,k-1) + comb(n-1,k); 
}
//BUG: RE = Infinite recursion
//Also, don't use directly
void swipe(int n, int k, ll R, vt<int> &ans) {
    if(n == 0 or k == 0) return;
    // debug(n) debug(k) debug(R)
    ll a = comb(n-1,k);
    ll b = comb(n-1,k-1);
    // debug(a) debug(b)
    // assert(R <= (a+b)); currently buggy??
    // if(R <= a) {
    //     swipe(n-1,k,R,ans);
    // } else {
    //     swipe(n-1,k-1,R-a,ans);
    //     ans.pb(n-1); //0-indexing business
    // }
    assert(R <= (a+b));
    // debug(R)
    if(R <= b) {
        // debug("I chose") debug(n) debug(k)
        ans.pb(n-1);
        swipe(n-1,k-1,R,ans);
    } else {
        // debug("I didn't choose") debug(n) debug(k)
        swipe(n-1,k,R-b,ans);
    }
}
//This function should work
vt<int> myror(int n, int k, ll R) {
    vt<int> ans;
    swipe(n, k, R, ans);
    f0r(i,0,sz(ans)) {
        ans[i] = n-1-ans[i];
    }
    // debug(n) debug(k) debug(R)
    // debug(ans);
    return ans;
}
vt<int> splay(vt<int> co, int N) {
    debug("splay")
    const int sbars = 5*N + 255;
    vt<bool> chose (sbars);
    f0r(i,0,sz(co)) {
        assert(co[i] < sbars);
        chose[co[i]] = 1;
    }
    vt<int> res;
    int d = 0;
    f0r(i,0,sbars) {
        if(chose[i]) {
            d++;
        } else {
            res.pb(d);
        }
    }
    return res;
}
//decoding: sorted sequence -> (while loop and cur diff) chosen -> (guess binary search, div2) order number
//->(division roll method) bits -> (pad zeroes and stoi spam) message
ll inv(vt<int> a, int N, int K) {
    ll res = itov(0);
    assert(sz(a) == K);
    f0r(i,0,sz(a)) {
        int prev = i == 0 ? -1 : a[i-1];
        f0r(s,prev+1, a[i]) {
            res = res + comb(N-1-s, K-i-1);
        }
    }
    res = res + itov(1);
    return res;
}
void mydec(signed msz, signed N, signed xs[]) {
    sort(xs,xs+N);
    int ck = 255;
    int cn = N + 255;
    debug(cn) debug(ck);
    vt<int> chose; //0,1 array
    int c_walk = 0;
    f0r(i,0,N) {
        while(c_walk != xs[i]) c_walk++, chose.pb(1);
        chose.pb(0);
    }
    //BUG: mixed up order of operations LMAO
    //need to account for leading zeroes before constructing need, otherwise useless
    //edge case: ending 1s
    while(c_walk != 255) c_walk++, chose.pb(1);

    vt<int> need; //chosen elements
    f0r(i,0,sz(chose)) {
        if(chose[i]) {
            need.pb(i);
        }
    }
    
    // ll lo = itov(1), hi = itov(1), ord = itov(-1);
    // f0r(_,0,8*65) { //repeated doublings???
    //     hi = hi + hi;
    // }
    //binary search on order number
    // auto check = [&](ll wow) -> bool {
    //     //BUG: check if wow is even in the order number range
    //     if(wow > comb(cn, ck)) {
    //         return false;
    //     }
    //     vt<int> cur = myror(cn, ck, wow);
    //     if(cur <= need) {
    //         return true;
    //     } else {
    //         return false;
    //     }
    // };
    // debug(need);
    // while(lo <= hi) {
    //     ll mid = (lo+hi)/2;
    //     // debug(lo) debug(hi) debug(mid)
    //     // debug(mid+itov(1));
    //     // debug(mid-itov(1));
    //     if(check(mid)) {
    //         lo = mid+itov(1);
    //         ord = mid;
    //     } else {
    //         hi = mid-itov(1);
    //     }
    // }
    // if(myror(cn,ck,ord+itov(6)) == need) {
    //     debug("WTF");
    // }
    // assert(myror(cn,ck,ord) == need);
    // debug(ord);
    ll ord = inv(need, cn, ck);
    //BUG: order number + 1
    ll pay = ord - itov(1);
    string bits;
    while(pay != itov(0)) { //BUG: Inf loop here
        if(pay[digits-1] % 2 == 1) {
            bits += '1';
        } else {
            bits += '0';
        }
        //BUG: lmao forgot to set pay = pay/2
        pay = pay / 2;
    }
    while(sz(bits) != 8 * msz) { //bit string
        bits += '0';
    }
    reverse(all(bits));
    assert(sz(bits) % 8 == 0);
    vt<int> ans;
    debug("DECODING BITS")
    debug(bits);
    for(int ptr = 0; ptr < sz(bits); ptr += 8) {
        string block = bits.substr(ptr, 8);
        int ayy = stoi(block, nullptr, 2);
        ans.pb(ayy);
    }
    debug("I THINK...")
    for(int x : ans) {
        cerr << x << ' ';
        output(x);
    }
    cerr << '\n';
}
void myenc(signed N, signed M[]) {
    // cdp = vt<vt<ll>> (600, vt<ll> (600, -1));
    // assert(N == 8);
    string bits;
    //load input bit and trick
    //BUG: highest significant bit first, lmao
    f0r(i,0,N) {
        r0f(b,7,0) {
            if(M[i] & (1 << b)) {
                bits += '1';
            } else {
                bits += '0';
            }
        }
    }
    debug("ENCODING BITS")
    debug(bits);
    ll ord = itov(0);
    ll roll = itov(1);
    debug("ayo")
    r0f(i,sz(bits)-1,0) {
        if(bits[i] == '1') {
            ord = ord + roll;
        }
        roll = roll + roll;
    }
    ord = ord + itov(1); //BUG: 0 case is bad
    debug(ord);
    //bug: forgot to + 255
    vt<int> co = myror(5*N + 255, 255, ord);
    // debug(ord);
    // swipe(575,255,ord,co);
    // debug(co);
    debug(co);
    vt<int> ans = splay(co, N);
    assert(sz(ans) == 5*N);
    debug("here's my answer");
    for(int x : ans) {
        cerr << x << ' ';
    }
    cerr << '\n';
    for(int x : ans) {
        send(x);
    }
}
};
// void encode(signed N, signed M[]) {
//     myenc(N, M);
// }
void decode(signed msz, signed N, signed xs[]) {
    mydec(msz, N, xs);    
}

Compilation message

encoder.cpp:180:6: warning: 'void {anonymous}::mydec(int, int, int*)' defined but not used [-Wunused-function]
  180 | void mydec(signed msz, signed N, signed xs[]) {
      |      ^~~~~

decoder.cpp:271:6: warning: 'void {anonymous}::myenc(int, int*)' defined but not used [-Wunused-function]
  271 | void myenc(signed N, signed M[]) {
      |      ^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 108016 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 108468 KB Output is correct
2 Correct 98 ms 108476 KB Output is correct
3 Correct 100 ms 108460 KB Output is correct
4 Correct 104 ms 108476 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 108500 KB Output is correct
2 Correct 95 ms 108480 KB Output is correct
3 Correct 100 ms 108532 KB Output is correct
4 Correct 111 ms 108776 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 108468 KB Output is correct
2 Correct 110 ms 108600 KB Output is correct
3 Correct 108 ms 108752 KB Output is correct
4 Correct 112 ms 108772 KB Output is correct
5 Correct 119 ms 108852 KB Output is correct
6 Correct 122 ms 108768 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 108744 KB Output is correct - P = 5.000000
2 Correct 112 ms 108864 KB Output is correct - P = 5.000000
3 Correct 118 ms 108820 KB Output is correct - P = 5.000000
4 Correct 141 ms 109104 KB Output is correct - P = 5.000000
5 Correct 155 ms 109128 KB Output is correct - P = 5.000000
6 Correct 170 ms 109036 KB Output is correct - P = 5.000000
7 Correct 161 ms 108904 KB Output is correct - P = 5.000000