#include
#include
#define EVEN 0
#define ODD 1
#define OR 1
#define XOR 0
extern void registerme();
extern int rangequery ( int, int, int );
extern void verifysoln ( int [] );
/* We maintain a queue of mutually disjoint intervals with each stored
interval guaranteed to store at leaast one solution. */
typedef struct {
int l; /* the left endpoint of the interval */
int r; /* the right endpoint of the interval */
int parity; /* whether the interval contains an even or an odd number of solutions */
} interval;
/* Standard binary search procudure to locate a solution in [L,R].
If the number of solutions in [L,R] is even, we call this function with
type = OR. The function returns the index of the leftmost one bit in the
interval [L,R]. In this case, we make only OR range queries.
If the number of solutions in [L,R] is odd, a solution can be found by
making XOR range queries only, so we pass type = XOR. However it is now
not guaranteed that the solution is leftmost or rightmost. Since the
successive bisection of the search interval will ensure that one of
the half-sized sub-intervals contains an odd number of solutions, we
can pinpoint a solution using log_2 n XOR range queries.
*/
int binsearch ( int L, int R, int type )
{
int M;
while (L < R) {
M = (L + R) / 2;
if (rangequery(L,M,type)) R = M; else L = M+1;
}
return L;
}
/* Note: There remains a possibility that you end up with too many XOR
queries (for example, when k = 2^t-1, and XOR-based binary search always
gives the central solution). This problem may be solved by maintaining
your private counts of range queries. At any point of time, an XOR-based
binary search can be replaced by a (more powerful) OR-based binary
search. In the following function, this is not implemented for the
sake of simplicity. */
void findpos ( int A[], int n )
{
interval Q[100]; /* The queue of intervals */
int front, back, L, R;
int i, j, k, t;
/* Initially, we know that the interval [0,n-1] contains ten (an even
number of) solutions. */
Q[0].l = 0; Q[0].r = n-1; Q[0].parity = EVEN; front = back = 0; k = 0;
/* Repeat so long as Q is not empty */
while (front <= back) {
L = Q[front].l; R = Q[front].r;
if (Q[front].parity == EVEN) { /* OR-based binary search */
/* A[k] stores the leftmost solution */
A[k] = binsearch(L,R,OR);
/* To the right of A[k], there exist an odd (in particular non-zero)
number of solutions */
++back; Q[back].l = A[k]+1; Q[back].r = R; Q[back].parity = ODD; /* Enqueue */
++k;
} else { /* XOR-based binary search */
/* Find one solution in A[k] */
A[k] = binsearch(L,R,XOR);
/* To the left of A[k], there are k1 solutions, and to the right
of A[k] there are k2 solutions. Since k1+k2 is even, k1 and k2
must have the same parity (both even or both odd). The case
both-even is problematic, because 0 is even. So by making
single OR range queries, we identify which of the two sides
of A[k] actually contain(s) solutions. */
t = EVEN;
if ((L <= A[k]-1) && (rangequery(L,A[k]-1,OR))) {
/* At leat one solution to the left of A[k] */
++back; Q[back].l = L; Q[back].r = A[k]-1; /* Enqueue */
/* An XOR query reveals the parity of the number of solutions */
t = Q[back].parity = rangequery(L,A[k]-1,XOR);
}
if ((t == ODD) || ((A[k]+1 <= R) && (rangequery(A[k]+1,R,OR)))) {
/* At leat one solution to the right of A[k] */
++back; Q[back].l = A[k]+1; Q[back].r = R; /* Enqueue */
/* An XOR query is not needed now, since k1,k2 have the same parity */
Q[back].parity = t;
}
++k; /* Next write location in the solutions array A[] */
}
++front; /* Dequeue */
}
/* Bubble sort the solutions array */
for (j=9; j>0; --j) {
for (i=0; i A[i+1]) {
t = A[i]; A[i] = A[i+1]; A[i+1] = t;
}
}
}
}
int main ( )
{
int A[10];
registerme();
findpos(A,65536);
verifysoln(A);
exit(0);
}