# D. Replace with Occurrences [문제 링크](https://codeforces.com/contest/2137/problem/D) ## Problem Statement Given an array $a$, let $f(x)$ be the number of occurrences of $x$ in the array $a$. For example, when $a=[1,2,3,1,4]$, then $f(1)=2$ and $f(3)=1$. You are given an array $b$ of size $n$. Determine whether there exists an array $a$ of size $n$ such that $f(a_i)=b_i \quad \text{for all } 1\le i\le n.$ If there is one, construct it. ## Input Each test contains multiple test cases. The first line contains the number of test cases $t$ $(1 \le t \le 10^{4})$. The description of the test cases follows. The first line contains an integer $n$ $(1 \le n \le 2\cdot10^{5})$. The second line contains $n$ integers $b_1,b_2,\ldots,b_n$ $(1 \le b_i \le n)$. It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^{5}$. ## Output For each test case, output `-1` if there is no valid array $a$. Otherwise, print an array $a$ of $n$ integers on a new line such that $1 \le a_i \le n$. ## 풀이 먼저 각 숫자의 등장 횟수를 구해 총 필요한 수가 n개인지 확인한다. 이때 총 필요한 수가 n이 아니거나 각 숫자의 등장횟수가 그 수의 배수가 아닌 경우 배열 a를 만드는 것이 불가능하다. 배열 a를 만들 수 있는 경우, 숫자 i가 등장하는 경우 i개씩 묶어 같은 수를 할당한다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; ll need=0; vector<int> b(n), cnt(n+1); for(int i=0;i<n;i++) { cin >> b[i]; cnt[b[i]]++; } for(int i=1;i<=n;i++) { if(cnt[i]%i==0) need += cnt[i]; else need += n+1; } if(need!=n) cout << "-1\n"; else { int cur=1; vector<int> last(n+1); for(int i=0;i<n;i++) { if(cnt[b[i]]/b[i] != (--cnt[b[i]])/b[i]) last[b[i]]=cur++; cout << last[b[i]] << ' '; } cout << '\n'; } } } ```