Editorial for CCC '17 S2 - High Tide, Low Tide


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

Sort the tide measurements in increasing order, and find the index of the middle element. Afterwards, alternate printing the next smallest and next greater element.

Time Complexity: \mathcal O(N \log N)

import std.stdio;
import std.algorithm.sorting;

int N, a;
int[] tides;
void main() {
    scanf("%d", &N);
    foreach(i;0..N) {
        scanf("%d", &a);
        tides ~= a;
    }
    tides.sort();
    int lo= N - 1 >> 1, hi = lo + 1;
    foreach(i;0..N) {
        if(i & 1)
            printf("%d ", tides[hi++]);
        else
            printf("%d ", tides[lo--]);
    }
}

Comments

There are no comments at the moment.