/** * Solution to IOI 2009 problem "museum" * * To solve this problem, we start by observing that if we have three * vases with heights A, B and C, such that either A is odd and C even or * A even and C odd, then no matter what B is these three vases will not * violate the condition of the exhibition organisers. This is because * A + C must therefore be odd, and so is not divisble by 2, meaning that * it is impossible for B to be the average of A and C. * * We therefore start by arranging the vases such that we place all the * even vases first, and all the odd vases second. This gives an * arrangement that looks like this: * * E1 E2 E3 ... Ex O1 O2 O3 ... Oy * * Since we know from the above observation that it is impossible to * choose A = Ei and B = Oj for any i and j such that there is a vase C * between these which violates the organisers' condition, it follows * that if there is a violation we must have either A = Ei and B = Ej * or A = Oi and B = Oj. * * Consider the even vases -- each has height 2X for some X. Suppose we * pick three vases with heights A = 2X, B = 2Y and C = 2Z such that * they violate the condition. We must then have 2 * 2Y = 2X + 2Z, which * implies that 2Y = X + Z. Similarly to above, it follows that X and Z * must either both be even or both be odd. If X and Z are even, then A * and C are divisible by 4, and if X and Z are odd then A and C are not * divisible by 4. To eliminate these condition violations, we thus arrange * the even group of vases such that they start with those divisible by 4 * and are followed by those not divisible by 4. * * The odd case is similar -- if we pick three vases from the Oi's such * that A = 2X + 1, B = 2Y + 1 and C = 2Z + 1, it follows that for the * condition to be violated we must have 2Y = X + Z. This corresponds * to A and C both being congruent to either 1 or 3 modulo 4, and we can * avoid these conflicts by grouping the odd vases to have the ones whose * height modulo 4 is 1 first, followed by those whose height is 3 modulo * 4. * * We continue this process, regrouping for modulo 8, 16 etc until we * have reached N. * * A more cunning solution is to simply represent each height in binary, * reverse the binary digits, and sort according to these reversed values. * In this way, all even numbers will appear first (since their last binary * digit is 0, which after the reversal is their first digit). Sorting on * the second binary digit will sort according to residues modulo 4, by * the third according to modulo 8, etc. * * Carl Hultquist, chultquist@gmail.com */ #include #include #include using namespace std; int main() { int n; cin >> n; // Determine the number of bits we need to represent the height // of the tallest vase. int bits = 0; int cur = n; while (cur != 0) { cur >>= 1; bits++; } // Instead of storing explicit strings, we create a reverse numeric // encoding on the fly. For each vase, we store its encoding and the // actual vase height as a pair of integers. Sorting these later will // sort by the encoded value, giving us the order we want. pair order[n]; for (int i = 0; i < n; i++) { int x = 0; int b = bits - 1; cur = i + 1; while (cur != 0) { // Only add powers of two for bits that matter if (cur & 1) x += (1 << b); cur >>= 1; b--; } order[i] = make_pair(x, i + 1); } // Sort everything sort(order, order + n); // And output the final ordering for (int i = 0; i < n; i++) cout << order[i].second << endl; return 0; }