oj.uz

Submission #543764

# Submission time Handle Problem Language Result Execution time Memory
543764 2022-03-31T10:36:02 Z neki Parrots (IOI11_parrots) C++14
81 / 100
 426 ms 7592 KB 
#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;}
    }
}
#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

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

# Verdict Execution time Memory Grader output
1 Correct 206 ms 7076 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 7440 KB Output is correct
2 Correct 269 ms 7376 KB Output is correct
3 Correct 295 ms 7400 KB Output is correct
4 Correct 286 ms 7436 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 7408 KB Output is correct
2 Correct 257 ms 7348 KB Output is correct
3 Correct 308 ms 7440 KB Output is correct
4 Correct 286 ms 7548 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 7420 KB Output is correct
2 Correct 316 ms 7412 KB Output is correct
3 Correct 329 ms 7392 KB Output is correct
4 Correct 410 ms 7412 KB Output is correct
5 Correct 411 ms 7348 KB Output is correct
6 Correct 411 ms 7416 KB Output is correct

Subtask #5
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 7592 KB Output is correct - P = 1.750000
2 Correct 423 ms 7436 KB Output is correct - P = 2.437500
3 Correct 426 ms 7444 KB Output is correct - P = 2.484848
4 Incorrect 230 ms 7232 KB Error : Output is wrong
5 Incorrect 210 ms 7248 KB Error : Output is wrong
6 Incorrect 201 ms 7176 KB Error : Output is wrong
7 Incorrect 193 ms 7176 KB Error : Output is wrong