Advertisement
Guest User

Untitled

a guest
Dec 7th, 2019
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.24 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define F first
  4. #define S second
  5. #define endl '\n'
  6. #define pb push_back
  7. #define ll long long
  8.  
  9. using namespace std;
  10.  
  11. vector < int > g[5];
  12.  
  13. int main() {
  14. ios_base::sync_with_stdio(0);
  15. cin.tie(0);
  16. cout.tie(0);
  17. freopen("input.txt", "r", stdin);
  18. freopen("output.txt", "w", stdout);
  19. int n;
  20. int m[3];
  21. cin >> n >> m[0] >> m[1] >> m[2];
  22. // if(n != 3 && n != 5 && n != 7) {
  23. // while(1) {
  24. //
  25. // }
  26. // }
  27. int l = 1, r = 1;
  28. for(int i = 0; i < 3; ++i) {
  29. for(int j = 0; j < m[i]; ++j) {
  30. int x;
  31. cin >> x;
  32. x += 2;
  33. g[i].pb(x);
  34. }
  35. r = max(r, int32_t(g[i].size()));
  36. }
  37. vector < int > used(n + 5);
  38. int cnt[5];
  39. int ans = 1;
  40. // cout << l << " " << r << endl;
  41. // for(int i = 0; i < 3; ++i) {
  42. // cout << i << ": ";
  43. // for(auto to : g[i])
  44. // cout << to << " ";
  45. // cout << endl;
  46. // }
  47. // return 0;
  48. while(l <= r) {
  49. int mid = (l + r) / 2;
  50. // cerr << l << " " << r << " " << mid << endl;
  51. if(mid * 3 > n) {
  52. // cerr << "lol " << endl;
  53. r = mid - 1;
  54. continue;
  55. }
  56. // if(mid == 3) cerr << "kek " << endl;
  57. // cerr << mid << endl;
  58. bool f = 1;
  59. for(int i = 0; i < n + 5; ++i) used[i] = -1;
  60. cnt[0] = 0;
  61. cnt[1] = 0;
  62. cnt[2] = 0;
  63. for(int i = 0; i < 3; ++i) {
  64. for(auto to : g[i]) {
  65. if(used[to] == -1) {
  66. cnt[i]++;
  67. used[to] = i;
  68. continue;
  69. }
  70. int x = used[to];
  71. if(cnt[x] - 1 >= mid) {
  72. cnt[x]--;
  73. cnt[i]++;
  74. used[to] = i;
  75. }
  76. }
  77. }
  78. for(int i = 0; i < 3; ++i) {
  79. if(cnt[i] < mid)
  80. f = 0;
  81. }
  82. if(f) {
  83. l = mid + 1;
  84. ans = mid;
  85. } else
  86. r = mid - 1;
  87. }
  88. used.assign(n + 5, -1);
  89. cnt[0] = 0;
  90. cnt[1] = 0;
  91. cnt[2] = 0;
  92. for(int i = 0; i < 3; ++i) {
  93. for(auto to : g[i]) {
  94. if(used[to] == -1) {
  95. cnt[i]++;
  96. used[to] = i;
  97. continue;
  98. }
  99. int x = used[to];
  100. if(cnt[x] - 1 >= ans) {
  101. cnt[x]--;
  102. cnt[i]++;
  103. used[to] = i;
  104. }
  105. }
  106. }
  107. for(int i = 3; i < n + 3; ++i) {
  108. cout << used[i] + 1 << " ";
  109. }
  110. // cout << endl;
  111.  
  112. return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement