Submission #1307250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307250		Zero_OP	Parrots (IOI11_parrots)	C++20	100 / 100	5 ms	848 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
namespace{ //BEGIN MY_TEMPLATE
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple

#define tcT template<class T

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) for(int i = 0; i < (r); ++i)
#define FORD(i, l, r) for(int i = (l) - 1; i >= (r); --i)

tcT> bool minimize(T& a, const T& b){
    return (a > b ? a = b, 1 : 0);
}

tcT> bool maximize(T& a, const T& b){
    return (a < b ? a = b, 1 : 0);
}

tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;
tcT> using max_heap = priority_queue<T>;

using ll = long long;
using db = double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;

using vpi = vector<pi>;
using vpl = vector<pl>;

#define task "task"
void setIO(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
}

tcT> void _print(const T& x){ cerr << x; }
void _print(const string& s){ cerr << '"' << s << '"'; }
void _print(const char* s){ cerr << '"' << s << '"'; }
void _print(char c){ cerr << '\'' << c << '\''; }
void _print(bool b){ cerr << (b ? "True" : "False"); }

tcT, class U> void _print(const pair<U, T>& p){
    cerr << "("; _print(p.ff); cerr << ", "; _print(p.ss); cerr << ")";
}

tcT, class U, class V> void _print(const tuple<T, U, V>& t){
    cerr << "("; _print(get<0>(t)); cerr << ", "; _print(get<1>(t)); cerr << ", "; _print(get<2>(t)); cerr << ")";
}

template<class it> void _print(it a, it b, string sep = ", "){
    cerr << "{";
    bool first = false;
    for(it c = a; c != b; ++c){
        if(first) cerr << sep;
        _print(*c);
        first = true;
    }
    cerr << "}";
}

tcT> void _print(const vector<T>& v){ _print(begin(v), end(v)); }
tcT> void _print(const set<T>& v){ _print(begin(v), end(v)); }
tcT> void _print(const multiset<T>& v){ _print(begin(v), end(v)); }
tcT, class U> void _print(const map<T, U>& v){ _print(begin(v), end(v)); }

void mainPrint(){ cerr << '\n'; }
tcT> void mainPrint(const T& a){ _print(a); cerr << '\n';}
tcT, class... U> void mainPrint(const T& a, const U&... b){
    _print(a); 
    cerr << " | ";
    mainPrint(b...);
}

#define debug(...) (cerr << "[" << __FILE__ << "|#" << __LINE__ << "]" << " [" << #__VA_ARGS__ << "] = ", mainPrint(__VA_ARGS__))

ll dp[50][50], sum[50];

vi findKthSequence(ll K, int len){ //from 1
    assert(sum[len] >= K);
    vi seq;
    int last = 15;
    for(int i = len; i >= 1; --i){
        bool found = false;
        for(int j = 0; j <= last; ++j){
            if(dp[i][j] < K){
                K -= dp[i][j];
            } else{
                last = j;
                seq.pb(j);
                found = true;
                break;
            }
        }
        assert(found);
    }
    return seq;
}

vi findKthSequence(ll K){
    ++K;
    for(int len = 1; len <= 20; ++len){
        if(sum[len] < K){
            K -= sum[len];
        } else{
            return findKthSequence(K, len);
        }
    }
    assert(false);
}

} //END MY_TEMPLATE


void encode(int N, int M[]){
    if(N <= 15){
        F0R(i, N){
            //bit 0-1
            F0R(bit, 8) if(M[i] >> bit & 1){
                int num = i + (bit << 5);
                send(num);
            }
        }
        return;
    }
    //group the adjacent quadruplet into 1 big number P[j] = A[i] + 256 * A[i + 1] * 256^2 * A[i + 2] + 256^3 * A[i + 3]
    //we will have ceil(N / 4) number of elements = 16 group (it takes 4 bits to declare the group)
    //Note that the number of non-decreasing arrays of the maximum length 20 of integers in range [0, 16) is slightly more than 256^3
    //so we map each number equal to the P[j]-th non-decreasing array (by lexicographical order)
    //for each P[j], we send at most 20 integers
    //so the total number of messages is 16 * 20 = 320 is much better tham 320
    
    memset(dp, 0, sizeof(dp));
    memset(sum, 0, sizeof(sum));
    dp[0][0] = 1;
    FOR(i, 1, 22){
        F0R(j, 16){
            F0R(k, j + 1){
                dp[i][j] += dp[i - 1][k];
            }
        }

        F0R(j, 16) sum[i] += dp[i][j];
    }

    for(int s = 0; s < N; s += 4){
        ll num = 0;
        for(int j = s + 3; j >= s; --j){
            int x = (j < N ? M[j] : 0);
            num = num * 256 + x;
        }

        int group = s / 4;
        vector<int> seq = findKthSequence(num);
        // cerr << "send " ;
        // for(auto u : seq) cerr << u << ' '; cerr << '\n';
        for(auto x : seq){
            send(group + (x << 4));
        }
    }
    // cerr << "end encode process\n";
}

decoder

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

namespace{ //BEGIN MY_TEMPLATE
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple

#define tcT template<class T

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define F0R(i, r) for(int i = 0; i < (r); ++i)
#define FORD(i, l, r) for(int i = (l) - 1; i >= (r); --i)

tcT> bool minimize(T& a, const T& b){
    return (a > b ? a = b, 1 : 0);
}

tcT> bool maximize(T& a, const T& b){
    return (a < b ? a = b, 1 : 0);
}

tcT> using min_heap = priority_queue<T, vector<T>, greater<T>>;
tcT> using max_heap = priority_queue<T>;

using ll = long long;
using db = double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;

using vpi = vector<pi>;
using vpl = vector<pl>;

#define task "task"
void setIO(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
}

tcT> void _print(const T& x){ cerr << x; }
void _print(const string& s){ cerr << '"' << s << '"'; }
void _print(const char* s){ cerr << '"' << s << '"'; }
void _print(char c){ cerr << '\'' << c << '\''; }
void _print(bool b){ cerr << (b ? "True" : "False"); }

tcT, class U> void _print(const pair<U, T>& p){
    cerr << "("; _print(p.ff); cerr << ", "; _print(p.ss); cerr << ")";
}

tcT, class U, class V> void _print(const tuple<T, U, V>& t){
    cerr << "("; _print(get<0>(t)); cerr << ", "; _print(get<1>(t)); cerr << ", "; _print(get<2>(t)); cerr << ")";
}

template<class it> void _print(it a, it b, string sep = ", "){
    cerr << "{";
    bool first = false;
    for(it c = a; c != b; ++c){
        if(first) cerr << sep;
        _print(*c);
        first = true;
    }
    cerr << "}";
}

tcT> void _print(const vector<T>& v){ _print(begin(v), end(v)); }
tcT> void _print(const set<T>& v){ _print(begin(v), end(v)); }
tcT> void _print(const multiset<T>& v){ _print(begin(v), end(v)); }
tcT, class U> void _print(const map<T, U>& v){ _print(begin(v), end(v)); }

void mainPrint(){ cerr << '\n'; }
tcT> void mainPrint(const T& a){ _print(a); cerr << '\n';}
tcT, class... U> void mainPrint(const T& a, const U&... b){
    _print(a); 
    cerr << " | ";
    mainPrint(b...);
}

#define debug(...) (cerr << "[" << __FILE__ << "|#" << __LINE__ << "]" << " [" << #__VA_ARGS__ << "] = ", mainPrint(__VA_ARGS__))

ll dp[50][50], sum[50];

ll countLowerLexi(vi seq){
    ll ans = 0;
    F0R(i, sz(seq)){
        if(i) ans += sum[i];
        F0R(j, seq[i]) ans += dp[sz(seq) - i][j];
    }
    return ans;
}

} //END MY_TEMPLATE

void decode(int N, int L, int X[]){
    if(N <= 15){
        vector<int> ans(N);
        F0R(i, L){
            int num = X[i];
            int first5 = num & ((1 << 5) - 1);
            int last3 = num >> 5;
            ans[first5] |= (1 << last3);
        }

        F0R(i, N) output(ans[i]);
        return;
    }
    //group the adjacent quadruplet into 1 big number P[j] = A[i] + 256 * A[i + 1] * 256^2 * A[i + 2] + 256^3 * A[i + 3]
    //we will have ceil(N / 4) number of elements = 16 group (it takes 4 bits to declare the group)
    //Note that the number of non-decreasing arrays of the maximum length 20 of integers in range [0, 16) is slightly more than 256^3
    //so we map each number equal to the P[j]-th non-decreasing array (by lexicographical order)
    //for each P[j], we send at most 20 integers
    //so the total number of messages is 16 * 20 = 320 is much better tham 320
    
    memset(dp, 0, sizeof(dp));
    memset(sum, 0, sizeof(sum));
    dp[0][0] = 1;
    FOR(i, 1, 22){
        F0R(j, 16){
            F0R(k, j + 1){
                dp[i][j] += dp[i - 1][k];
            }
        }

        F0R(j, 16) sum[i] += dp[i][j];
    }


    vector<vi> groups(N);
    F0R(i, L){
        int g = X[i] & ((1 << 4) - 1);
        int num = X[i] >> 4;
        // cerr << g << ' ' << num << '\n';
        groups[g].eb(num);
    }

    vi ans;
    F0R(i, N){
        if(groups[i].empty()) break;
        sort(rall(groups[i]));
        // cerr << i << " : " << sz(groups[i]) << '\n';
        // for(auto x : groups[i]) cerr << x << ' ';
        // cerr << '\n';

        ll num = countLowerLexi(groups[i]);
        F0R(_, 4){
            ans.eb(num % 256);
            num /= 256; 
        }
    }   

    // cerr << "decoder : ";
    // F0R(i, N) cerr << ans[i] << " "; cerr << '\n';
    F0R(i, N) output(ans[i]);
}

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