409612: GYM103643 O Painting Fences (Hard Version)

This is the hard version of the problem, the main difference is that Takagi has another rule she will follow.

Nishikata and Takagi are standing in front of an infinitely long fence. Fenceposts are numbered from $$$1$$$ to $$$\infty$$$ and fencepost $$$i$$$ costs $$$i$$$ units of paint to paint. They both also have an infinite amount of paint. The game for today will consist of painting a bit of that fence.

To try and make it fair, Nishikata has planned a few rules.

Nishikata's rules are as follows:

1. When painting, the two of them will only ever paint a contiguous interval of fenceposts.

2. He will pick a fencepost $$$n$$$, and he gets to paint that fencepost no matter what.

3. To minimize teasing, he will pick a segment of fenceposts that are disjoint from the fenceposts Takagi picks. In other words, he and Takagi will not ever paint the same fencepost.

As Takagi plays the game, she won't tell Nishikata, but she will follow these rules:

1. She will make the game end in a draw by making sure she and Nishikata will paint the same amount.

2. To still be able to tease Nishikata, she will minimize the minimum distance between their intervals.

Takagi already knows how the game will end up, but you do not. So given the integer $$$n$$$ that Nishikata picks in rule $$$2$$$, find any two intervals $$$[a, b]$$$ that Nishikata paints and $$$[c, d]$$$ that Takagi paints that does not break either of their rules.

You will answer $$$T$$$ testcases $$$(1 \leq T \leq 10^4)$$$. Each testcase contains an integer $$$n$$$ $$$(1 \leq n \leq 10^9)$$$ corresponding to the fencepost Nishikata picks in rule $$$2$$$.

In the subtask descriptions, tests are numbered $$$1$$$ to $$$20$$$ with the sample skipped.

Test $$$1$$$ will be every number from $$$1$$$ to $$$10^4$$$.

Tests $$$2 - 10$$$ will satisfy that $$$n \leq 10^6$$$.

Output four integers $$$a, b, c, d$$$ where $$$[a, b]$$$ denotes the fenceposts Nishikata paints and $$$[c, d]$$$ denotes the fenceposts Takagi paints. It can be proven an answer always exists and it satisfies $$$(1 \leq a, b, c, d < 2^{31})$$$.

These two intervals must be disjoint and sum of $$$[a ... b]$$$ should be equal to sum of $$$[c ... d]$$$. Also $$$(a \leq n \leq b)$$$ must hold.

Since this is the hard version $$$\min(|b - c|, |a - d|)$$$ must be minimized. Your solution will be considered correct if the code's minimum distance between the two intervals is no more than what the judger has as the minimum distance between the two intervals.

2
1
9

1 2 3 3
9 12 13 15

For the second testcase, $$$9, 9, 4, 5$$$ would have worked except the minimum distance then is $$$4$$$ whereas for $$$9, 12, 13, 15$$$ the minimum distance is $$$1$$$. Since the two intervals must be disjoint, it is impossible to do better than $$$1$$$ as the minimum distance between the two intervals.

$$$---------------------------------------------$$$

Problem idea: 3366

Problem preparation: 3366

Occurrences: Intermediate 10, Advanced 8