HITCON QUALS 2016 - Reverse (Reverse 500)

generate.py

from binascii import crc32

def lcg_step():
    global lcg
    lcg = (0x5851F42D4C957F2D * lcg + 0x14057B7EF767814F) % 2**64
    return lcg

def extract(val):
    res = 32 + val - 95 * ((
        ((val - (0x58ED2308158ED231 * val >> 64)) >> 1) +
        (0x58ED2308158ED231 * val >> 64)) >> 6)
    return res & 0xff

buf = bytearray()
lcg = 8323979853562951413

crc = 0
print 31415926
for i in xrange(31415926):
    # append a symbol
    c = extract( lcg_step() )
    buf.append(c)

    # reverse interval
    x = lcg_step() % len(buf)
    y = lcg_step() % len(buf)
    l, r = min(x, y), max(x, y)
    print l, r

open("buf", "w").write(buf)

solve.cpp

#include <bits/stdc++.h>

/*
g++ --std=c++11 -O3 solve.cpp -o solve && ./solve
*/

using namespace std;

typedef long long LL;

#define CONCAT3_NX(x, y, z) x ## y ## z
#define CONCAT3(x, y, z) CONCAT3_NX(x, y, z)
#define VAR(name) CONCAT3(__tmpvar__, name, __LINE__)
#define TYPE(x) __typeof(x)

// pretty for's
#define FOR(i, s, n)  for (TYPE(n) i=(s),   VAR(end)=(n);  i <  VAR(end);  i++)
#define RFOR(i, s, n) for (TYPE(n) i=(n)-1, VAR(end)=(s);  i >= VAR(end);  i--)
#define FORN(i, n)    FOR(i, 0, n)
#define RFORN(i, n)   RFOR(i, 0, n)
#define FOREACH(i, v) for (auto& i: v)

uint32_t POLY = 0xedb88320L;
uint32_t HI = 1u << 31;
uint32_t LO = 1;
uint32_t ONEBYTE = (1u << 31) >> 8;

uint32_t BYTE_CRC[256];
uint32_t SHIFT_BYTES[100 * 1000 * 1000];

inline uint32_t poly_mul(uint32_t a, uint32_t b) {
    uint32_t p = 0;
    while (b) {
        if (b & HI) p ^= a;
        b <<= 1;
        if (a & LO) a = (a >> 1) ^ POLY;
        else a >>= 1;
    }
    return p;
}

void precompute() {
    SHIFT_BYTES[0] = HI; // 1
    FOR(i, 1, 100 * 1000 * 1000) {
        SHIFT_BYTES[i] = poly_mul(SHIFT_BYTES[i-1], ONEBYTE);
    }
    FORN(c, 256) {
        BYTE_CRC[c] = poly_mul(c, ONEBYTE);
    }
}

inline uint32_t lift(uint32_t crc, LL num) {
    return poly_mul(crc, SHIFT_BYTES[num]);
}

// Treap

typedef struct item * pitem;
struct item {
    int prior, value, cnt;
    bool rev;
    pitem l, r;
    uint32_t crc_forward, crc_backward;
};

inline int cnt (pitem it) {
    return it ? it->cnt : 0;
}

inline uint32_t crc1(pitem it) {
    if (!it) return 0;
    if (it->rev) return it->crc_backward;
    return it->crc_forward;
}
inline uint32_t crc2(pitem it) {
    if (!it) return 0;
    if (it->rev) return it->crc_forward;
    return it->crc_backward;
}

inline void update_up (pitem it) {
    if (it) {
        it->cnt = cnt(it->l) + cnt(it->r) + 1;

        int left_size = cnt(it->l);
        int right_size = cnt(it->r);
        uint32_t cl, cr, cmid;
        cmid = BYTE_CRC[it->value];

        cl = crc1(it->l);
        cr = crc1(it->r);
        it->crc_forward = lift(cl, right_size + 1) ^ lift(cmid, right_size) ^ cr;

        cl = crc2(it->l);
        cr = crc2(it->r);
        it->crc_backward = cl ^ lift(cmid, left_size) ^ lift(cr, left_size + 1);
    }
}

inline void push (pitem it) {
    if (it && it->rev) {
        swap(it->crc_forward, it->crc_backward);
        it->rev = false;
        swap (it->l, it->r);
        if (it->l)  it->l->rev ^= true;
        if (it->r)  it->r->rev ^= true;
    }
}

void merge (pitem & t, pitem l, pitem r) {
    push (l);
    push (r);
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
    update_up (t);
}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
    if (!t)
        return void( l = r = 0 );
    push (t);
    int cur_key = add + cnt(t->l);
    if (key <= cur_key)
        split (t->l, l, t->l, key, add),  r = t;
    else
        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
    update_up (t);
}

inline void reverse (pitem t, int l, int r) {
    pitem t1, t2, t3;
    split (t, t1, t2, l);
    split (t2, t2, t3, r-l+1);
    t2->rev ^= true;
    merge (t, t1, t2);
    merge (t, t, t3);
}

inline void insert(pitem &t, pitem new_item, int pos){
    if (!t) {
        t = new_item;
        return;
    }
    pitem t1, t2;
    split(t, t1, t2, pos);
    merge(t1, t1, new_item);
    merge(t, t1, t2);
}

// prealloc instead of calling new
int top = 0;
item itemspace[33 * 1000 * 1000];

unsigned char buf[33 * 1000 * 1000];

int main() {
    precompute();

    FILE *fd;
    fd = fopen("buf", "r");
    int N = (int)fread(buf, 1, sizeof(buf), fd);
    fclose(fd);

    printf("N = %d\n", N);

    pitem root = NULL;
    uint32_t curcrc = 0xffffffff;
    auto t0 = time(NULL);
    fd = fopen("reverses", "r");
    fscanf(fd, "%d", &N);
    FORN(i, N) {
        // append c
        itemspace[top] = {rand() ^ (rand() << 24), buf[i]};
        pitem t = itemspace + top;
        top++;
        t->crc_forward = t->crc_backward = BYTE_CRC[buf[i]];
        insert(root, t, i);

        // reverse [l, r]
        int l, r;
        fscanf(fd, "%d %d\n", &l, &r);
        assert (l <= r && r <= i);
        reverse(root, l, r);

        if (i % 100000 == 0) {
            fprintf(stderr, "i %d curcrc: %08x (%d seconds)\n", i, curcrc ^ 0xffffffff, time(NULL) - t0);
        }
        // update CRC
        curcrc = lift(curcrc, cnt(root));
        curcrc ^= crc1(root);

    }
    fprintf(stderr, "final: %08x\n", curcrc ^ 0xffffffff);
    fclose(fd);
    return 0;
}