Advertisement
cyberjab

Untitled

Sep 7th, 2024
14
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.68 KB | None | 0 0
  1. //#pragma GCC optimize("03")
  2. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <cstdlib>
  6. #include <cstdio>
  7. #include <string>
  8. #include <vector>
  9. #include <map>
  10. #include <set>
  11. #include <unordered_map>
  12. #include <unordered_set>
  13. #include <queue>
  14. #include <deque>
  15. #include <cmath>
  16. #include <numeric>
  17. #include <algorithm>
  18. #include <ctime>
  19. #include <chrono>
  20. #include <random>
  21. #include <functional>
  22. #include <stack>
  23. //#include <windows.h>
  24. //void* operator new(size_t size) {
  25. // if (void* ptr = HeapAlloc(GetProcessHeap(), 0, size ? size : 1)) return ptr;
  26. // throw std::bad_alloc{};
  27. //}
  28. //void operator delete(void* ptr) {
  29. // HeapFree(GetProcessHeap(), 0, ptr);
  30. //}
  31.  
  32. using namespace std;
  33. using ll = long long;
  34. using db = double;
  35. using ldb = long double;
  36. using pii = pair<int, int>;
  37. using pll = pair<ll, ll>;
  38. using vint = vector<int>;
  39. using vll = vector<ll>;
  40. using vst = vector<string>;
  41. #define all(x) x.begin(), x.end()
  42. #define size(x) int(x.size())
  43. #define rep(x) for(int rep_i = 0; rep_i < x; ++rep_i)
  44. #define forp(i, s, f) for(int i = s; i < f; ++i)
  45. #define form(i, s, f) for(int i = s; i > f; --i)
  46. #define PB push_back
  47. #define MP make_pair
  48. #define F first
  49. #define S second
  50. #define elif else if
  51. #define dprint(x) for (auto now: x) cout << now << " "
  52.  
  53. const int MOD = 1e9 + 7;
  54. const int MOD2 = 998244353;
  55. const int INF = 2e9 + 7;
  56. const ll LINF = 1e18 + 7;
  57. const double EPS = 1e-9;
  58. const long double PI = acosl(-1.0);
  59.  
  60. void solve() {
  61. int n, k;
  62. cin >> n >> k;
  63. vector<vll> sp(n, vll(3));
  64. forp(i, 0, n) cin >> sp[i][0];
  65. forp(i, 0, n) cin >> sp[i][1];
  66. forp(i, 0, n) sp[i][2] = (ll)i + 1;
  67. ldb l = 0, r = INF;
  68. vector<pair<ldb, int>> spp(n), ans;
  69. forp(j, 0, 100) {
  70. ldb m = l + (r - l) / 2;
  71. forp(i, 0, n) {
  72. spp[i].first = sp[i][0] - sp[i][1] * m;
  73. spp[i].second = sp[i][2];
  74. }
  75. sort(all(spp));
  76. reverse(all(spp));
  77. ldb sm = 0;
  78. forp(i, 0, k) {
  79. sm += spp[i].first;
  80. }
  81. if (sm <= 0) {
  82. l = m;
  83. }
  84. else {
  85. r = m;
  86. }
  87. }
  88. ldb c = r;
  89. forp(i, 0, n) {
  90. spp[i].first = sp[i][0] - sp[i][1] * c;
  91. spp[i].second = sp[i][2];
  92. }
  93. sort(all(spp));
  94. reverse(all(spp));
  95. cout << l << ' ' << r << '\n';
  96. forp(i, 0, k) {
  97. cout << spp[i].second << '\n';
  98. }
  99. }
  100.  
  101. int main() {
  102. ios_base::sync_with_stdio(0);
  103. cin.tie(0);
  104. /*cout << setprecision(x)*/
  105. cout << fixed;
  106. int t;
  107. t = 1;
  108. while (t > 0) {
  109. solve();
  110. t--;
  111. }
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement