Advertisement
Guest User

Untitled

a guest
Feb 21st, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.21 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. #include <iostream>
  3. #include <stdio.h>
  4. #include <vector>
  5. #include <set>
  6. #include <unordered_set>
  7. #include <map>
  8. #include <unordered_map>
  9. #include <deque>
  10. #include <algorithm>
  11. #include <math.h>
  12. #include <random>
  13. #define ff first
  14. #define ss second
  15. #define pb push_back
  16. #define mp make_pair
  17. #define int long long
  18. #define double long double
  19. #define Matrix vector<vector<int> >
  20. #define kektor vector
  21. #define pii pair<int, int>
  22. #define all(x) x.begin(), x.end()
  23.  
  24. using namespace std;
  25.  
  26. typedef long long ll;
  27.  
  28. int RandInt(int min, int max) {
  29. if (max < min) {
  30. swap(min, max);
  31. }
  32. random_device rd;
  33. mt19937 mt(rd());
  34. uniform_int_distribution<int> dist(min, max);
  35. return dist(mt);
  36. }
  37.  
  38. const int maxn = 3e5 + 1, mod = 1e9 + 7;
  39. bool debug = false;
  40. int n, k;
  41. pii cnt[maxn];
  42.  
  43. vector<int> ans(int el1) {
  44. set<pii> dd1;
  45. set<pii> dd2;
  46. set<pii> dd3;
  47. vector<int> ans;
  48. for (int i = 0; i < n; ++i) {
  49. if (cnt[i].ff < el1) {
  50. dd1.insert({cnt[i].ff, cnt[i].ss});
  51. } else if (cnt[i].ff == el1) {
  52. dd2.insert({cnt[i].ff, cnt[i].ss});
  53. } else {
  54. dd3.insert({cnt[i].ff, cnt[i].ss});
  55. }
  56. }
  57. int left1 = dd1.size();
  58. int mid = dd2.size() - 1;
  59. int right1 = dd3.size();
  60. int kk = min(left1, right1);
  61. left1 -= kk;
  62. right1 -= kk;
  63. if (right1 != 0) {
  64. int tt = min(mid, right1);
  65. right1 -= tt;
  66. } else {
  67. int tt = min(mid, left1);
  68. left1 -= tt;
  69. }
  70. int siz1 = dd1.size() - left1;
  71. int siz2 = dd3.size() - right1;
  72. for (int i = 0; i < siz1; ++i) {
  73. ans.pb((*(dd1.begin())).ss + 1);
  74. dd1.erase(dd1.begin());
  75. }
  76. for (int i = 0; i < siz2; ++i) {
  77. ans.pb((*dd3.begin()).ss + 1);
  78. dd3.erase(dd3.begin());
  79. }
  80. for (auto i : dd2) {
  81. ans.pb(i.ss + 1);
  82. }
  83. return ans;
  84. }
  85.  
  86. void solve() {
  87. cin >> n >> k;
  88. for (int i = 0; i < n; ++i) {
  89. cin >> cnt[i].ff;
  90. cnt[i].ss = i;
  91. }
  92. sort(cnt, cnt + n);
  93. int el1 = -1;
  94. int el2 = -1;
  95. for (int i = 0; i < n; ++i) {
  96. if (cnt[i].ff >= k) {
  97. el2 = cnt[i].ff;
  98. break;
  99. } else {
  100. el1 = cnt[i].ff;
  101. }
  102. }
  103. vector<int> ans1, ans2;
  104. if (el1 != -1) {
  105. ans1 = ans(el1);
  106. }
  107. if (el2 != -1) {
  108. ans2 = ans(el2);
  109. }
  110. if (el1 == -1) {
  111. cout << ans2.size() << '\n';
  112. for (auto i : ans2) {
  113. cout << i << " ";
  114. }
  115. return;
  116. } else if (el2 == -1) {
  117. cout << ans1.size() << '\n';
  118. for (auto i : ans1) {
  119. cout << i << " ";
  120. }
  121. return;
  122. } else if (abs(k - el1) < abs(k - el2)) {
  123. cout << ans1.size() << '\n';
  124. for (auto i : ans1) {
  125. cout << i << " ";
  126. }
  127. return;
  128. } else if (abs(k - el1) > abs(k - el2)) {
  129. cout << ans2.size() << '\n';
  130. for (auto i : ans2) {
  131. cout << i << " ";
  132. }
  133. return;
  134. } else if (ans1.size() > ans2.size()) {
  135. cout << ans1.size() << '\n';
  136. for (auto i : ans1) {
  137. cout << i << " ";
  138. }
  139. return;
  140. } else {
  141. cout << ans2.size() << '\n';
  142. for (auto i : ans2) {
  143. cout << i << " ";
  144. }
  145. return;
  146. }
  147. }
  148.  
  149.  
  150.  
  151. signed main() {
  152. /*!
  153.  
  154. !*/
  155. cout.precision(10);
  156. cout << fixed;
  157. if (!debug) {
  158. ios_base::sync_with_stdio(false);
  159. cin.tie(0);
  160. cout.tie(0);
  161. }
  162. //freopen("TASK.in", "r", stdin);
  163. //freopen("TASK.out", "w", stdout);
  164. solve();
  165. return 0;
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement