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.
Forget the ribbon length for a second. The only thing that matters at any moment is the current number of distinct colors, not the exact painted sequence.
If there are currently distinct colors, the fairy paints the next cell with color . What happens to the distinct-color count depends only on whether color already exists.
If color is already present, painting with adds nothing new, so the count stays forever. That is a fixed point.
If color is missing, painting with creates a new distinct color, so the count becomes . Then you ask the same question for .
Start with the number of distinct colors in the initial array. The answer is the first integer that was already present among the initial colors.
Let the set of initially used colors be , and let
be the number of distinct colors already on the ribbon.
Now look at one step of the process. Before painting the next cell, the fairy counts the number of distinct colors. Suppose that number is . Then she paints the cell with color .
There are only two possible outcomes:
Case 1: color is already in the set.
Then painting another cell with color changes absolutely nothing. The set of distinct colors stays the same, so the count is still for the next cell, and the next one, and the next one... forever. Congrats, we found the boring stable state. Boring is good here.
Case 2: color is not in the set.
Then painting with color adds a brand new distinct color. So the number of distinct colors increases from to .
That means the process is basically:
So we only need the first value at least that already appears in the initial array.
For example, if the initial colors are:
There are distinct colors, so start with .
Color is missing, so after one new cell the count becomes .
Color is missing, then is missing, then color exists. Once the count reaches , the fairy keeps using color forever.
Since the ribbon has cells and , there are absurdly many remaining cells. The process stabilizes very quickly because all initial colors are at most . No simulation of cells. Please do not make your CPU do interpretive dance for no reason.
Algorithm
For each test case:
Why is this valid even though we do not literally insert the missing values? Because once we move from to , we will never need to check the old again. The only question is whether the current count already existed before stabilization.
Complexity
Each test case is tiny. With the given constraints, this is effectively constant time. More formally, the loop runs at most around times, so the complexity is where is the maximum color value bound.
#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;
set<int> colors;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
colors.insert(x);
}
int distinct = (int)colors.size();
while (!colors.count(distinct)) {
distinct++;
}
cout << distinct << '\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;
set<int> colors;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
colors.insert(x);
}
int distinct = (int)colors.size();
while (!colors.count(distinct)) {
distinct++;
}
cout << distinct << '\n';
}
return 0;
}