ProgMe

Untitled

Feb 7th, 2021
179
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.91 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. string comp(string one, string other)
  6. {
  7. bitset <1000> used{};
  8. sort(other.begin(), other.end(), greater<>());
  9. if(one >= other)
  10. return "-1";
  11. string ret = other, pref;
  12. reverse(other.begin(), other.end());
  13. int idx = 0;
  14. while(one.size() - idx)
  15. {
  16. int idx_eq = -1, idx_gr = -1;
  17. for(int i = 0; i < other.size(); i++)
  18. {
  19. if(!used[i])
  20. {
  21. if(other[i] == one[idx] && idx_eq == -1)
  22. idx_eq = i;
  23. if(other[i] > one[idx] && idx_gr == -1)
  24. idx_gr = i;
  25. }
  26. if(idx_eq != -1 && idx_gr != -1)
  27. break;
  28. }
  29. if(idx_gr != -1)
  30. {
  31. string chg = pref;
  32. chg += other[idx_gr];
  33. for(int i = 0; i < other.size(); i++)
  34. if(!used[i] && i != idx_gr)
  35. chg += other[i];
  36. ret = min(ret, chg);
  37. }
  38. if(idx_eq != -1)
  39. {
  40. pref += one[idx];
  41. idx ++;
  42. used[idx_eq] = true;
  43. }
  44. else
  45. break;
  46. }
  47. if(!(one.size() - idx))
  48. {
  49. for(int i = 0; i < other.size(); i++)
  50. if(!used[i])
  51. pref += other[i];
  52. return pref;
  53. }
  54. else
  55. return ret;
  56. }
  57.  
  58. int32_t main() {
  59. int q;
  60. cin >> q;
  61. while(q--)
  62. {
  63. int n;
  64. cin >> n;
  65. string prev;
  66. cin >> prev;
  67. sort(prev.begin(), prev.end());
  68. bool ok = true;
  69. while(n-- > 1)
  70. {
  71. string now;
  72. cin >> now;
  73. now = comp(prev, now);
  74. if(now == "-1")
  75. {
  76. ok = false;
  77. break;
  78. }
  79. prev = now;
  80. }
  81. cout << (ok ? "YES\n" : "NO\n");
  82. }
  83. }
Advertisement
Add Comment
Please, Sign In to add comment