Sorting Stress Test

Points 100 5.0s 1G

The following program passes all tests:

#include<algorithm>
#include<iostream>
const int SIZE = 20000000;
uint64_t a[SIZE];
int main() {
    int n;
    std::cin >> a[0] >> n;
    for(int i = 1; i < n; i++) {
        uint64_t x = a[i - 1];
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        a[i] = x;
    }
    std::sort(a, a + n);
    std::cout << a[n / 2] << std::endl;
    return 0;
}

Input

The input consists of a single line containing two positive integers \(a[0]\) and \(n\). The value \(a[0]\) fits in an unsigned 64-bit integer, and \(1 \le n \le 2 \times 10^7\).

Output

Output a single line containing the answer.

Sample Input 1

1969464034641677472 5

Sample Output 1

13532146017095035750

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.