oj.uz

Submission #926499

# Submission time Handle Problem Language Result Execution time Memory
926499 2024-02-13T06:49:59 Z hotboy2703 Parrots (IOI11_parrots) C++14
81 / 100
 41 ms 3584 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"
namespace {
    ll p[101][256];
    void init(){
        mt19937_64 rng(45345);
        for (ll i = 0;i < 100;i ++){
            for (ll j = 0;j < 256;j ++){
                p[i][j] = j;
            }
            shuffle(p[i],p[i]+256,rng);
        }
    }
}
void encode(int N, int M[]){
    init();
    ll n = N;
    vector <bool> all;
    for (ll i = 0;i < n;i ++){M[i] = p[i][M[i]];}
    for (ll i = 0;i < n;i ++)for (ll j = 0;j < 8;j ++)all.push_back(BIT(M[i],j));
    ll cnt[2];
    for (auto x:all)cnt[x]++;
    if (cnt[1] < 4 * n){
        all.insert(all.begin(),0);
        for (ll i = 1;i < sz(all);i++)all[i] = 1-all[i];
    }
    else{
        all.insert(all.begin(),1);
    }
//    for (auto x:all)cout<<x;
//    cout<<endl;
    cnt[0] = cnt[1] = 0;
    for (auto x:all){
        cnt[x]++;
        if (x==1){
            send(cnt[0]);
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
#include "decoder.h"
#include "decoderlib.h"
#include "encoder.h"
#include "encoderlib.h"
namespace {
    ll p[101][256];
    void init(){
        mt19937_64 rng(45345);
        for (ll i = 0;i < 100;i ++){
            for (ll j = 0;j < 256;j ++){
                p[i][j] = j;
            }
            shuffle(p[i],p[i]+256,rng);
        }
    }
}
void decode(int N, int L, int X[]){
    init();
    ll n = N;
    ll cnt[300] = {};
    for (ll i = 0;i < L;i ++){
        cnt[X[i]]++;
    }
    vector <ll> bit;
    for (ll i = 0;i < 256;i ++){
        while (cnt[i]--){
            bit.push_back(i);
        }
    }
    vector <bool> all;
    ll last = 0;
    for (auto x:bit){
        for (ll i= 0 ;i  < x - last;i ++){
            all.push_back(0);
        }
        all.push_back(1);
        last = x;
    }
    while (sz(all)<300)all.push_back(0);
//    for (auto x:all)cout<<x;
//    cout<<endl;
    if (all[0] == 0){
        for (ll j = 0;j < sz(all);j ++)all[j] = 1-all[j];
    }
    for (ll i = 0,ptr = 1;i < n;i ++,ptr += 8){
        ll res = 0;
        for (ll j = 0;j < 8;j ++){
            res += MASK(j) * all[ptr+j];
        }
//        cout<<i<<' '<<res<<endl;
        for (ll j = 0;j < 256;j ++){
            if (p[i][j]==res){
//                cout<<i<<' '<<j<<endl;
                output(j);
            }
        }
    }
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3356 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3352 KB Output is correct
2 Correct 38 ms 3392 KB Output is correct
3 Correct 38 ms 3236 KB Output is correct
4 Correct 38 ms 3528 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3328 KB Output is correct
2 Correct 38 ms 3356 KB Output is correct
3 Correct 38 ms 3356 KB Output is correct
4 Correct 38 ms 3356 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3392 KB Output is correct
2 Correct 38 ms 3416 KB Output is correct
3 Correct 39 ms 3276 KB Output is correct
4 Correct 39 ms 3352 KB Output is correct
5 Correct 39 ms 3360 KB Output is correct
6 Correct 40 ms 3368 KB Output is correct

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3356 KB Output is correct
2 Correct 40 ms 3296 KB Output is correct
3 Correct 39 ms 3584 KB Output is correct
4 Correct 41 ms 3456 KB Output is correct
5 Incorrect 4 ms 3096 KB Error : Bad encoded integer
6 Halted 0 ms 0 KB -