Submission #543764

#	Time	Username	Problem	Language	Result	Execution time	Memory
543764		neki	Parrots (IOI11_parrots)	C++14	81 / 100	426 ms	7592 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
 
#include <bits/stdc++.h>
#define ll long long
#define loop(i, a, b) for(ll i=a;i<b;++i)
#define pool(i, a, b) for(ll i=a-1;i>=b;--i)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define par pair<ll, ll>
#define ld long double
#define mod 998244353
 
bool addb(bool b1, bool b2, bool& carry){
    bool ret = b1 ^ b2 ^ carry;
    carry= (b1 && carry) || (b2 && carry) || (b1 && b2);
    return ret;
}
bool subb(bool b1, bool b2, bool& carry){
    bool ret = b1 ^ b2 ^ carry;
    carry=(!b1 && carry) || (!b1 && b2) || (b1 && b2 && carry);
    return ret;
}
struct int512{
    bitset<512> arr;
    
    int512(){}
    int512(int n){arr=bitset<512> (n);}
    int512(int n, int m[]){
        loop(i, 0, n) loop(j, 0, 8) arr[i * 8+j]=((m[i] & (1<<j))>0);
    }
    
    int512 operator+(const int512& oth){
        int512 ret;
        
        bool carry=false;
        loop(i, 0, 512) ret.arr[i]=addb(arr[i], oth.arr[i], carry);
        
        return ret;
    }
    int512 operator-(const int512& oth){
        int512 ret;
        
        bool carry=false;
        loop(i, 0, 512) ret.arr[i]=subb(arr[i], oth.arr[i], carry);
        
        return ret;
    }
    
    bool operator<(const int512& oth){
        pool(i, 512, 0){
            if(arr[i]==0 and oth.arr[i]==1 ) return true;
            if(arr[i]==1 and oth.arr[i]==0 ) return false;
        }
        return false;
    }
    bool operator<=( int512& oth){return *this<oth or !(oth<*this);}
};
 
bool ze=0;
 
const int mk=100;
int512 dp[mk][256], pr[mk][256];
void init(){
    if(ze) return;
    
    loop(i, 0, 256) dp[0][i]=int512(1);
    
    loop(i, 1, mk) {
        dp[i][0]=int512(1);
        loop(j, 1, 256) dp[i][j]=dp[i][j-1]+dp[i-1][j];
    }
    
    loop(i, 0, mk){
        loop(j, 0, 256) pr[i][j]=dp[i][j];
        loop(j, 1, 256) pr[i][j]=pr[i][j] + pr[i][j-1];
        //loop(j, 0, 256) cout << pr[i][j].arr.to_ulong()<<" ";
        //cout << endl;
        
    }
    
    ze=1;
}
 
void encode(int n, int m[]){
    init();
    
    int512 a(n, m);
    
    int myk;
    loop(i, 0, mk) if(a<pr[i][255]) {myk=i;break;}
    
    pool(k, myk+1, 0){
        loop(i, 0, 256) if(a<pr[k][i]){ if(i-1>=0)a=a-pr[k][i-1];send(i);break;}
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
 
#include <bits/stdc++.h>
#define ll long long
#define loop(i, a, b) for(ll i=a;i<b;++i)
#define pool(i, a, b) for(ll i=a-1;i>=b;--i)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define par pair<ll, ll>
#define ld long double
#define mod 998244353
 
bool addb(bool b1, bool b2, bool& carry){
    bool ret = b1 ^ b2 ^ carry;
    carry= (b1 && carry) || (b2 && carry) || (b1 && b2);
    return ret;
}
bool subb(bool b1, bool b2, bool& carry){
    bool ret = b1 ^ b2 ^ carry;
    carry=(!b1 && carry) || (!b1 && b2) || (b1 && b2 && carry);
    return ret;
}
struct int512{
    bitset<512> arr;
    
    int512(){}
    int512(int n){arr=bitset<512> (n);}
    int512(int n, int m[]){
        loop(i, 0, n) loop(j, 0, 8) arr[i * 8+j]=((m[i] & (1<<j))>0);
    }
    
    int512 operator+(const int512& oth){
        int512 ret;
        
        bool carry=false;
        loop(i, 0, 512) ret.arr[i]=addb(arr[i], oth.arr[i], carry);
        
        return ret;
    }
    int512 operator-(const int512& oth){
        int512 ret;
        
        bool carry=false;
        loop(i, 0, 512) ret.arr[i]=subb(arr[i], oth.arr[i], carry);
        
        return ret;
    }
    
    bool operator<(const int512& oth){
        pool(i, 512, 0){
            if(arr[i]==0 and oth.arr[i]==1 ) return true;
            if(arr[i]==1 and oth.arr[i]==0 ) return false;
        }
        return false;
    }
    bool operator<=( int512& oth){return *this<oth or !(oth<*this);}
};
 
bool ze=0;
 
const int mk=100;
int512 dp[mk][256], pr[mk][256];
void init(){
    if(ze) return;
    
    loop(i, 0, 256) dp[0][i]=int512(1);
    
    loop(i, 1, mk) {
        dp[i][0]=int512(1);
        loop(j, 1, 256) dp[i][j]=dp[i][j-1]+dp[i-1][j];
    }
    
    loop(i, 0, mk){
        loop(j, 0, 256) pr[i][j]=dp[i][j];
        loop(j, 1, 256) pr[i][j]=pr[i][j] + pr[i][j-1];
        //loop(j, 0, 256) cout << pr[i][j].arr.to_ulong()<<" ";
        //cout << endl;
        
    }
    
    ze=1;
}
 
void decode(int n, int l, int k[]){
    init();
    sort(k, k+l);
    int512 ans;
    
    loop(i, 0, l){ 
        if(k[i]!=0) ans= ans+pr[i][k[i]-1];
    }
    
    //ans=ans + int512(1);
    
    for(int i=0;i<n * 8;i+=8){
        ll cans=0;
        loop(j, 0, 8) cans+=(1<<j) * ans.arr[i+j]; 
        
        output(cans);
    }
}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:102:9: warning: 'myk' may be used uninitialized in this function [-Wmaybe-uninitialized]
  102 |     int myk;
      |         ^~~

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