fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define repp(it, a) for(auto it = a.begin(); it != a.end(); ++it)
  4.  
  5. map<int, int> color;
  6. map<int, vector<int>> idxs;
  7. int arr[100005];
  8. int n;
  9.  
  10. bool is_possible(){
  11. for(int i = 0; i < n; ++i){
  12. if(n - color[arr[i]] < color[arr[i]]) return false;
  13. }
  14. return true;
  15. }
  16.  
  17. int main(){
  18. ios_base::sync_with_stdio(false);
  19. cin.tie(NULL), cout.tie(NULL);
  20.  
  21. int t;
  22. cin>>t;
  23. while(t--){
  24. cin>>n;
  25. color = map<int, int>();
  26. idxs = map<int, vector<int>>();
  27.  
  28. for(int i = 0; i < n; ++i)
  29. cin>>arr[i],
  30. color[arr[i]]++,
  31. idxs[arr[i]].push_back(i);
  32.  
  33. bool possible = is_possible();
  34. if(!possible){
  35. cout<<"No"<<endl;
  36. continue;
  37. }
  38.  
  39. cout<<"Yes"<<endl;
  40. repp(i, idxs){
  41. i++;
  42. auto j = i==idxs.end() ? idxs.begin() : i;
  43. i--;
  44. auto & temp = (*i).second;
  45. int l = temp.size();
  46. for(int k = 0; k < l; ++k){
  47. while(color[(*j).first] <= 0 || j == i) {
  48. j++;
  49. if(j == idxs.end()) j = idxs.begin();
  50. }
  51. arr[temp[k]] = (*j).first;
  52. color[(*j).first]--;
  53. }
  54. }
  55. for(int i = 0; i < n; ++i) cout<<arr[i]<<" ";
  56. cout<<endl;
  57. }
  58.  
  59.  
  60. return 0;
  61. }
  62.  
Success #stdin #stdout 0s 15632KB
stdin
5
10
1 1 1 2 2 2 3 3 3 4
2
1 1
5
1 1 1 2 2
7
1 2 3 4 1 2 3
14
1 1 1 1 1 1 1 2 3 2 3 4 4 5
stdout
Yes
2 2 2 3 3 3 4 1 1 1 
No
No
Yes
2 3 4 1 2 3 1 
Yes
2 2 3 3 4 4 5 1 1 1 1 1 1 1