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.
First ask the boring lower-bound question: how small can any array possibly become? The operation deletes exactly one element from a length- subarray, so once the array has length , the party is over.
For , the answer can never be less than . So the whole problem is: can we always keep any chosen alive until only two elements remain?
If the chosen element is inside some length- subarray, you are never forced to delete it. In that triple, at least one of the other two elements is either smaller than or larger than , so one of them is deletable.
Look at the current array while its length is at least . If there is any element on the left of , use the triple ending at or crossing toward to delete something not equal to . If not, use a triple starting at . Either way, you can shrink without killing .
The answer is stupidly simple: if , print ; otherwise print for every position. The permutation values do not matter at all. Classic Codeforces A: big statement, tiny knife.
The operation always changes the length by exactly and is only possible while the current length is at least .
So:
For , we obviously cannot do anything, so the answer is .
Now the only real question is whether, for any chosen element , we can always delete elements until exactly two remain while never deleting .
Consider any moment when the current array has length at least and still contains .
Choose any length- subarray containing if possible. If is not the median of that triple, then itself is deletable, but we are not forced to delete it. We may delete the other extreme instead if it is available.
If is the median of the triple, then the other two elements are the minimum and maximum, so both of them are deletable. Great, is completely safe.
In short: in any triple containing , there is always some element different from that can be deleted. No magic. Just three distinct numbers, and the median is the only one that cannot be deleted.
Since the whole array has length at least , unless only exists, we can always find a triple containing or use nearby elements so that some non- element gets removed. Repeating this deletes other elements and leaves an array of length containing .
Therefore the lower bound is achievable for every element when .
Thus the answer is:
The permutation itself is a red herring. A very shiny red herring, but still.
For each test case, we only read the permutation and print numbers.
#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 = 0; i < n; i++) {
int x;
cin >> x;
}
for (int i = 0; i < n; i++) {
if (i) cout << ' ';
cout << (n == 1 ? 1 : 2);
}
cout << '\n';
}
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 = 0; i < n; i++) {
int x;
cin >> x;
}
for (int i = 0; i < n; i++) {
if (i) cout << ' ';
cout << (n == 1 ? 1 : 2);
}
cout << '\n';
}
return 0;
}