Advertisement
trungore10

ranking

Aug 28th, 2018
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.03 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. typedef pair<int, int> ii;
  6.  
  7. const int N = 1004, oo = 1e8;
  8. int n, orgN;
  9. ii a[N], orgArr[N];
  10.  
  11. vector<ii> vec;
  12.  
  13. void compress() {
  14. for (int i = 1; i <= n; ++i) {
  15. orgArr[i] = a[i];
  16. vec.push_back(a[i]);
  17. } orgN = n;
  18.  
  19. sort(vec.begin(), vec.end());
  20. vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
  21.  
  22. n = vec.size();
  23. for (int i = 1; i <= n; ++i) a[i] = vec[i-1];
  24. }
  25.  
  26. bool cmp(ii a, ii b) { return a.first * b.second < a.second * b.first; }
  27.  
  28. ii ans[N];
  29. vector<ii> More, Less;
  30. vector<int> Equal;
  31.  
  32. void getRes(int id, int mul) {
  33. sort(More.begin(), More.end(), cmp);
  34. sort(Less.begin(), Less.end(), cmp); reverse(Less.begin(), Less.end());
  35. sort(Equal.begin(), Equal.end());
  36.  
  37. int minVal = oo, maxVal = -oo;
  38. for (int i = 0; i < (int) More.size(); ++i) {
  39. int A = More[i].first, B = More[i].second;
  40. int l = 0, r = Less.size()-1, save = -1;
  41. while (l <= r) {
  42. int mid = (l + r) / 2;
  43. if (A * Less[mid].second < B * Less[mid].first) {
  44. save = mid; l = mid + 1;
  45. }
  46. else r = mid - 1;
  47. }
  48. minVal = min(minVal, i+1 + save+1);
  49. maxVal = max(maxVal, i+1 + save+1);
  50. }
  51.  
  52. if (More.empty()) {
  53. minVal = 0;
  54. for (int i = 0; i < (int) Less.size(); ++i) {
  55. int A = Less[i].first, B = Less[i].second;
  56. if ( (A > 0 && B < 0) || (A < 0 && B > 0) ) break;
  57. maxVal++;
  58. }
  59. }
  60.  
  61. for (int i = 0; i < (int) Equal.size(); ++i) {
  62. if (Equal[i] * mul < 0) minVal++, maxVal++;
  63. }
  64.  
  65. ans[id].first = min(ans[id].first, minVal);
  66. ans[id].second = max(ans[id].second, maxVal);
  67. }
  68.  
  69. void Process(int id, int mul) {
  70. More.clear(); Less.clear(); Equal.clear();
  71.  
  72. for (int i = 1; i <= n; ++i) {
  73. if (id == i) continue;
  74. if (a[id].first > a[i].first) {
  75. if (mul == 1) More.push_back(ii(a[id].second - a[i].second, a[id].first - a[i].first));
  76. else Less.push_back(ii(a[id].second - a[i].second, a[id].first - a[i].first));
  77. }
  78. else if (a[id].first < a[i].first) {
  79. if (mul == 1) Less.push_back(ii(a[id].second - a[i].second, a[id].first - a[i].first));
  80. else More.push_back(ii(a[id].second - a[i].second, a[id].first - a[i].first));
  81. }
  82. else {
  83. Equal.push_back(a[id].second - a[i].second);
  84. }
  85. }
  86.  
  87. getRes(id, mul);
  88. }
  89.  
  90. void sol() {
  91. compress();
  92.  
  93. for (int id = 1; id <= n; ++id) {
  94. ans[id] = ii(orgN-1, 1);
  95. Process(id, 1);
  96.  
  97. cerr << "# ";
  98. cerr << n - ans[id].first << " " << n - ans[id].second << '\n';
  99. exit(0);
  100. }
  101.  
  102. for (int id = 1; id <= orgN; ++id) {
  103. for (int i = 1; i <= n; ++i) if (orgArr[i] == a[i]) {
  104. cout << orgN - ans[i].first << " " << orgN - ans[i].second << '\n';
  105. break;
  106. }
  107. }
  108.  
  109.  
  110. /// a == 0 or b == 0 ??
  111. }
  112.  
  113. #undef int
  114. int main() {
  115. #define int long long
  116. ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  117. //freopen("ranking.inp", "r", stdin);
  118. //freopen("ranking.out", "w", stdout);
  119. freopen("input.txt", "r", stdin);
  120.  
  121. cin >> n;
  122. for (int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second;
  123.  
  124. sol();
  125.  
  126. return 0;
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement