Submission #902938

#	Time	Username	Problem	Language	Result	Execution time	Memory
902938		heavylightdecomp	Parrots (IOI11_parrots)	C++14	81 / 100	108 ms	1628 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define vt vector
#define pb push_back
#define X first
#define Y second
using pii = pair<int,int>;
#define debug(x) do\
{auto _x=x; cerr<<#x<<" = "<<_x<<'\n';}while(0);
#define f0r(i,a,b) for(auto i=(a);i<(b);i++)
#define r0f(i,a,b) for(auto i=(a);i>=(b);i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
//There was a bug: position collisions
//Instead:
//First 5 bits for position (guaranteed distinct)
//Next bit for head/tail
//Next 2 bits for block
//remaining 2 bits in the times
void mysend(int a, int times) {
    debug(bitset<8>(a));
    debug(bitset<3>(times));
    f0r(i,0,times) send(a);
}
void encode(int N, int M[]) {
    set<int> cs; //collision sanity check
    f0r(pos,0,N) {
        debug(pos)
        //BUG: swapped around heads and tails order
        int body = pos << 3;
        int ha = M[pos] & ((1 << 2) - 1);
        int hb = (M[pos] >> 2) & ((1<<2)-1);
        int ta = (M[pos] >> 4) & ((1<<2)-1);
        int tb = (M[pos] >> 6) & ((1<<2)-1);
        //BUG: added twice
        assert(!cs.count(body | ha));
        assert(!cs.count(body|(1<<2)|ta));
        mysend(body | ha, hb+1);
        mysend(body | (1 << 2) | ta, tb+1);
        cs.insert(body | ha);
        cs.insert(body | (1 << 2) | ta);
    }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define vt vector
#define pb push_back
#define X first
#define Y second
using pii = pair<int,int>;
#define debug(x) do\
{auto _x=x; cerr<<#x<<" = "<<_x<<'\n';}while(0);
#define f0r(i,a,b) for(auto i=(a);i<(b);i++)
#define r0f(i,a,b) for(auto i=(a);i>=(b);i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
//potential bug: confusion between N and L
void decode(int d_sz, int N, int xs[]) {
    vt<int> freq (256); //BUG: 256 size -> [0, 255]
    vt<int> ans (d_sz);
    f0r(i,0,N) {
        freq[xs[i]]++;
    }
    //BUG: exclusive for loop
    f0r(a,0,256) if(freq[a]) { //BUG : need to check if 0 times
        int b_block = freq[a] - 1;
        int a_block = a & ((1<<2)-1);
        bool is_heads = !!(a & (1 << 2));
        int pos = a >> 3;
        debug(pos)
        debug(is_heads);
        debug(bitset<2>(b_block))
        debug(bitset<2>(a_block))
        //BUG: |=
        ans[pos] |= ((b_block << 2) | a_block) << (is_heads ? 4 : 0);
    }
    debug("I THINK....")
    f0r(i,0,d_sz) {
        cerr << ans[i] << ' ';
        output(ans[i]);
    }
    cerr << '\n';
}

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