fork download
copy 
  1.  
  2. #include<iostream>
  3. using namespace std;
  4. #include<set>
  5. #include<map>
  6.  
  7. string str = "";
  8.  
  9. string vasya_and_multisets(multiset<int> total){
  10. 	map<int, int> count;
  11.  
  12. 	for(auto x: total)
  13. 		count[x]++;
  14.  
  15. 	multiset<int> A, B;
  16. 	int cnt = 0;
  17. 	int prev = -1;
  18. 	for(auto x: total){
  19. 		if(count[x] % 2 != 0 && x != prev){
  20. 			cnt++;
  21. 		}
  22. 		prev = x;
  23. 	}
  24. 	//cout<<"\n\ncnt = "<<cnt;
  25. 	if(cnt % 2 != 0)
  26. 		return "NO";
  27.  
  28. 	for(auto x: total){
  29. 		if(count[x] % 2 != 0 && count[x] != 1){
  30. 			B.insert(x);
  31. 			count[x]--;
  32. 			str += 'B';
  33. 		}
  34. 		else if(count[x] % 2 != 0 && count[x] == 1){
  35. 			B.insert(x);
  36. 			str += 'B';
  37. 		}
  38. 		else{
  39. 			A.insert(x);
  40. 			str += 'A';
  41. 		}
  42. 	}
  43. 	int i = 1;
  44.  
  45. 	int it = 0;
  46. 	for(auto x: B){
  47. 		if(i > cnt/ 2)
  48. 			break;
  49. 		if(count[x] == 1){
  50. 			A.insert(x);
  51. 			B.erase(x);
  52. 			i++;
  53. 			str[it] = 'A';
  54. 		}
  55. 		it++;
  56. 	}
  57.  
  58. 	return "YES";
  59. }
  60.  
  61. int main(){
  62.  
  63. 	int n;
  64.  
  65. 	cin>>n;
  66.  
  67. 	multiset<int> total;
  68. 	int x;
  69.  
  70. 	for(int i=0; i<n; i++){
  71. 		cin>>x;
  72. 		total.insert(x);
  73. 	}
  74. 	string ans = vasya_and_multisets(total);
  75. 	if(ans == "NO")
  76. 		cout<<"NO\n";
  77. 	else {
  78. 		cout<<"YES\n"<<str<<"\n";
  79. 	}
  80.  
  81. 	return 0;
  82. }
  83.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
https://ideone.com/Qtv1Pm
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!