GerONSo

Untitled

Jun 1st, 2019
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.39 KB | None | 0 0
  1. #define pragma
  2.  
  3. #ifdef pragma
  4. #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
  5. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  6. #endif // pragma
  7.  
  8. #include<bits/stdc++.h>
  9. #include <ext/pb_ds/assoc_container.hpp>
  10. #include <ext/pb_ds/tree_policy.hpp>
  11.  
  12. #define ll long long
  13. #define all(x) begin(x), end(x)
  14. #define pb push_back
  15. #define x first
  16. #define y second
  17. #define int long long
  18. #define zero(two) memset(two, 0, sizeof(two))
  19.  
  20. using namespace std;
  21. using namespace __gnu_pbds;
  22.  
  23.  
  24. typedef vector<int> vi;
  25. typedef vector<bool> vb;
  26. typedef pair<int, int> pii;
  27. typedef long double ld;
  28. typedef vector<vi> matrix;
  29. template<typename T>
  30. using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  31.  
  32. const ld PI = atan2(0, -1);
  33.  
  34. void seriy() {
  35. ios::sync_with_stdio(0);
  36. cin.tie(0);
  37. cout.tie(0);
  38. cout << fixed << setprecision(10);
  39. #if _offline
  40. freopen("input.txt", "r", stdin);
  41. freopen("output.txt", "w", stdout);
  42. #endif
  43. }
  44.  
  45. const int MAXN = 1e5 + 10;
  46. const int INF = 1e18 + 7;
  47. const int MAXLOG = 20;
  48. const int MOD = 998244353;
  49. const int BASE = 47;
  50.  
  51. struct p {
  52. int x, y, n;
  53. };
  54.  
  55. bool cmp(p a, p b) {
  56. return a.y > b.x && a.y > b.y;
  57. }
  58.  
  59. bool cmp2(p a, p b) {
  60. return a.y < b.x && a.y < b.y;
  61. }
  62.  
  63. signed main() {
  64. seriy();
  65. int n;
  66. cin >> n;
  67. vector<p> a(n), f, s;
  68. for(int i = 0; i < n; i++) {
  69. cin >> a[i].x >> a[i].y;
  70. if(a[i].x < a[i].y) f.pb({a[i].x, a[i].y, i});
  71. else s.pb({a[i].x, a[i].y, i});
  72. }
  73. vi ans1, ans2;
  74. sort(all(f), cmp);
  75. sort(all(s), cmp2);
  76. int cur = 0;
  77. while(cur < f.size()) {
  78. if(cur + 1 == f.size()) {
  79. ans1.pb(f[cur].n);
  80. break;
  81. }
  82. if(f[cur].y > f[cur + 1].x) ans1.pb(f[cur].n);
  83. cur++;
  84. }
  85. cur = 0;
  86. while(cur < s.size()) {
  87. if(cur + 1 == s.size()) {
  88. ans2.pb(s[cur].n);
  89. break;
  90. }
  91. if(s[cur].y < s[cur + 1].x) ans2.pb(s[cur].n);
  92. cur++;
  93. }
  94. if(ans1.size() < ans2.size()) {
  95. cout << ans2.size() << '\n';
  96. for(auto i : ans2) {
  97. cout << i + 1 << " ";
  98. }
  99. }
  100. else {
  101. cout << ans1.size() << '\n';
  102. for(auto i : ans1) {
  103. cout << i + 1 << " ";
  104. }
  105. }
  106. return 0;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment