Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
A block contributes its middle value. So for every median you choose, you must “waste” one number larger than it in the same block.
Think of every block as . The large elements contribute nothing to the score, so they should be the unavoidable very largest numbers.
There are only numbers bigger than . Since each median needs a bigger partner, the medians cannot beat the next values below those.
Try making the medians exactly . Then the remaining numbers split perfectly into lows and highs .
Output blocks for . Each block has median , and those are the largest possible medians. That's the whole trick.
Every block can be viewed as
So each chosen median needs one strictly larger number in its block. Those larger numbers do not contribute to the answer, so in an optimal construction they should be the largest values:
After reserving those as the “large” elements, the biggest possible medians are exactly
Thus no answer can have median sum larger than
Use blocks
for every .
Since
the median of the -th block is . Therefore the total sum is
which matches the upper bound. Optimal. No gymnastics required.
We output numbers per test case, so the time complexity is
and memory usage is
besides output.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cout << i << ' ' << n + i << ' ' << 2 * n + i;
if (i == n) cout << '\n';
else cout << ' ';
}
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cout << i << ' ' << n + i << ' ' << 2 * n + i;
if (i == n) cout << '\n';
else cout << ' ';
}
}
return 0;
}