HITCON QUALS 2016 - Reverse (Reverse 500)
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) |
#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment