Uva 10909

/**
You can use a binary search tree to generate the list of luckies.
The tree should be able to remove an element and return k-th smallest element in O(log n) time.

Once you have this list, you can solve each test case by bruteforcing L1, starting from L1 = floor(N / 2) and going down to 1.

Also note, that no odd number can be represented as a sum of luckies.
**/
#include <bits/stdc++.h>

#define Max 666667  /* max. number of nodes in the tree */
#define MaxN 2000001

/* Tree's housekeeping...*/
int left[Max], right[Max], parent[Max], key[Max], count[Max], N, root;

int Lucky[(MaxN >> 5) + 10];

/* Returns the index of the k-th smallest element in the tree. */
int find(int k) {
    for (int x = root;;)
        if (k < count[left[x]])
            x = left[x];
        else if (k == count[left[x]])
            return x;
        else
            k -= count[left[x]] + 1, x = right[x];
}

/*
 *  Removes the element with index 'x' from the tree.
 *  Implemented algorithm ensures that the height of the tree does not increase.
 */
void remove(int x) {
    int y;

    if (left[x] != 0 and right[x] != 0) {
        if (count[right[x]] >= count[left[x]])
            for (y = right[x]; left[y] != 0; y = left[y]);
        else
            for (y = left[x]; right[y] != 0; y = right[y]);
        key[x] = key[y];
        x = y;
    }

    if (left[x] == 0 and right[x] == 0) {
        if (left[parent[x]] == x)
            left[parent[x]] = 0;
        else
            right[parent[x]] = 0;
    } else {
        y = (left[x] == 0) ? right[x] : left[x];

        if (parent[x] == 0) {
            parent[root = y] = 0;
            return;
        }

        if (left[parent[x]] == x)
            left[parent[x]] = y;
        else
            right[parent[x]] = y;
        parent[y] = parent[x];
    }

    for (x = parent[x]; x != 0; x = parent[x])
        count[x]--;
}

/* Constructs a balanced tree with b - a + 1 elements; returns index of its root.
   The tree's nodes will get consecutive indices in their order in the tree. */
int build(int a, int b) {
    if (a > b) return 0;
    if (a == b) {
        N++; left[N] = right[N] = 0;
        count[N] = 1;
        return N;
    }
    int c = (a + b) / 2;
    int t = build(a, c - 1);
    left[++N] = t;
    t = N;
    right[t] = build(c + 1, b);
    count[t] = count[left[t]] + count[right[t]] + 1;
    parent[left[t]] = parent[right[t]] = t;
    return t;
}

int Set(int N, int pos){
    return N = N | (1 << pos);
}
bool Check(int N, int pos) {
    return (bool)(N & (1 << pos));
}

void mark(int x) {
    for (; x; x = right[x]) {
        Lucky[key[x] >> 5] = Set(Lucky[key[x] >> 5], key[x] & 31);
        mark(left[x]);
    }
}

/* Constructs the list of lucky numbers */
void make() {
    int i, j, k;

    /* First off, initialize the tree... */

    N = count[0] = 0;
    parent[root = build(0, Max)] = 0;

    /*
     *  As an optimization, we start with the tree, containing all numbers
     *  of form 6k+1 and 6k+3 in the range of interest.
     *  These are the numbers, which remain after the first two elimination
     *  rounds.
     */
    for (i = 1, j = 1; i <= Max; j += 6)
        key[i++] = j, key[i++] = j + 2;

    /* Now just simulation... */
    for (k = 2; k < count[root]; k++) {
        j = key[find(k)] - 1;
        if (j >= count[root]) break;

        for (i = j; i < count[root]; i += j)
            remove(find(i));
    }

    /* Finally, mark the remaining numbers in the boolean array lucky[] */
    memset(Lucky, 0, sizeof Lucky);
    mark(root);
}

int main(void) {
    int a, n;

    for (make(); ~scanf("%d", &n);) {
        a = 0;
        if (n >= 1 and (n & 1) == 0) {
            for (a = n/2; a > 0 and !Check(Lucky[a >> 5], a & 31); a--);
            for (; a > 0; a -= 2)
                if(Check(Lucky[a >> 5], a & 31) and Check(Lucky[(n - a) >> 5], (n - a) & 31))
                    break;
        }

        if (a <= 0)
            printf("%d is not the sum of two luckies!\n", n);
        else
            printf("%d is the sum of %d and %d.\n", n, a, n - a);
    }
    return 0;
}