oj.uz

Submission #352206

# Submission time Handle Problem Language Result Execution time Memory
352206 2021-01-20T13:32:36 Z talant117408 Parrots (IOI11_parrots) C++17
99 / 100
 18 ms 1572 KB 
#include "encoder.h"
#include "encoderlib.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;

void encode(int N, int M[]){
    int res = 0, ind = -1;
    vector <int> ans, vec;
    for(int i = 0; i < N; i++){
        ans.pb(M[i]);
        vec.pb(M[i]);
        for(int bit = 0; bit < 4; bit++)
            if(M[i]&(1<<bit))
                res++;
        for(int bit = 0; bit < 4; bit++)
            if(M[i]&(1<<(bit+4)))
                res += 2;
    }
    for(int k = 0; k < 256; k++){
        for(auto &to : vec) to ^= k;
        int cnt = 0;
        for(int i = 0; i < N; i++){
            for(int bit = 0; bit < 4; bit++)
                if(vec[i]&(1<<bit))
                    cnt++;
            for(int bit = 0; bit < 4; bit++)
                if(vec[i]&(1<<(bit+4)))
                    cnt += 2;
        }
        if(cnt < res){
            ind = k;
            res = cnt;
            ans = vec;
        }
        for(auto &to : vec) to ^= k;
    }
    vector <int> one;
    for(int i = 0; i < N; i++){
        int num = i;
        for(int bit = 0; bit < 4; bit++){
            if(ans[i]&(1<<bit)){
                if(!bit) one.pb(num);
                else if(bit == 1) one.pb(num+64);
                else if(bit == 2) one.pb(num+128);
                else one.pb(num+192);
            }
        }
        for(int bit = 0; bit < 4; bit++){
            if(ans[i]&(1<<(bit+4))){
                if(!bit){
                    one.pb(num);
                    one.pb(num);
                }
                else if(bit == 1){
                    one.pb(num+64);
                    one.pb(num+64);
                }
                else if(bit == 2){
                    one.pb(num+128);
                    one.pb(num+128);
                }
                else{
                    one.pb(num+192);
                    one.pb(num+192);
                }
            }
        }
    }
    for(auto to : one) send(to);
    if(ind == -1){
        for(int i = 0; i < 5; i++)
            send(0);
    }
    else{
        for(int i = 0; i < 4; i++){
            send(ind);
        }
    }
}

#include "decoder.h"
#include "decoderlib.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;

void decode(int N, int L, int X[]){
    vector <int> cnt(256), ans(N);
    int flag = 1, xr;
    for(int i = 0; i < L; i++){
        cnt[X[i]]++;
    }
    if(cnt[0] > 4){
        flag = 0;
        cnt[0] -= 5;
    }
    else{
        for(int i = 0; i < 256; i++){
            if(cnt[i] > 3){
                cnt[i] -= 4;
                xr = i;
                break;
            }
        }
    }
    for(int i = 0; i < 256; i++){
        if(cnt[i] > 1){
            cnt[i] -= 2;
            int ind = 0, which = 0;
            for(int bit = 0; bit < 6; bit++){
                if(i&(1<<bit)) ind |= (1<<bit);
            }
            if((i&(1<<6)) && (i&(1<<7))) which = 7;
            else if(i&(1<<7)) which = 6;
            else if(i&(1<<6)) which = 5;
            else which = 4;
            ans[ind] |= (1<<which);
        }
        if(cnt[i]){
            cnt[i]--;
            int ind = 0, which = 0;
            for(int bit = 0; bit < 6; bit++){
                if(i&(1<<bit)) ind |= (1<<bit);
            }
            if((i&(1<<6)) && (i&(1<<7))) which = 3;
            else if(i&(1<<7)) which = 2;
            else if(i&(1<<6)) which = 1;
            else which = 0;
            ans[ind] |= (1<<which);
        }
    }
    for(auto &to : ans){
        if(flag) to ^= xr;
    }
    for(auto to : ans) output(to);
}
/*
8
0 0 1 1 0 0 1 0

6 
1 255 13 26 49 216
*/

Compilation message

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:74:21: warning: 'xr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |         if(flag) to ^= xr;
      |                  ~~~^~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 880 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1132 KB Output is correct
2 Correct 4 ms 1264 KB Output is correct
3 Correct 5 ms 1312 KB Output is correct
4 Correct 5 ms 1140 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1328 KB Output is correct
2 Correct 4 ms 1136 KB Output is correct
3 Correct 4 ms 1268 KB Output is correct
4 Correct 6 ms 1320 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1132 KB Output is correct
2 Correct 5 ms 1140 KB Output is correct
3 Correct 5 ms 1272 KB Output is correct
4 Correct 8 ms 1308 KB Output is correct
5 Correct 9 ms 1284 KB Output is correct
6 Correct 9 ms 1300 KB Output is correct

Subtask #5
18.0 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 1140 KB Output is partially correct - P = 5.750000
2 Partially correct 9 ms 1156 KB Output is partially correct - P = 5.781250
3 Partially correct 9 ms 1284 KB Output is partially correct - P = 5.666667
4 Partially correct 13 ms 1304 KB Output is partially correct - P = 5.900000
5 Partially correct 16 ms 1572 KB Output is partially correct - P = 5.783333
6 Partially correct 16 ms 1444 KB Output is partially correct - P = 5.793651
7 Partially correct 18 ms 1320 KB Output is partially correct - P = 5.875000