[Solved] Why this program does 35 percent accepted but rest is runtime errors?

by


You don’t need to recreate the array, and you don’t need to sort anything (the description even tells you that you shouldn’t: “Dino’s computer cannot perform this arrangement”).

Consider what happens if you turn the problem around slightly.

Instead of a[i] being the i:th number, let it say how many is there are in total.
(The arrangement of the input hints at this, although not as obviously as the “sorting won’t work” hint.)
This essentially makes a run-length encoded sorted array, with the indices of a doubling as elements, and the elements of a are the run lengths.

Then consider that a linear search through 105 elements (bi ≤ 105) is way faster than sorting 106 elements.

Something like this:

int main()
{
    // Keeps track of the total number of occurrences of each number.
    // The values are all less than or equal to 100000.
    // Add an extra element to simplify the rest of the code.
    // (The zero will be unused.)
    std::vector<int> counts(100001);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int count, value;
        cin >> count >> value;
        counts[value] += count;
    }
    int k;
    cin >> k;
    // Now go looking for the k:th number, adjusting k as we go.
    for (size_t number = 0; number < counts.size(); number++)
    {
        if (k <= counts[number])
        {
            std::cout << number << std::endl;
            break;
        }
        // Adjust k for the rest of the sequence.
        k -= counts[number];
    }
}

3

solved Why this program does 35 percent accepted but rest is runtime errors?