kostes

Untitled

Oct 21st, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.45 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define FI(_n) for(int i = 0;i<(_n);i++)
  3. #define FJ(_n) for(int j = 0;j<(_n);j++)
  4. using namespace std;
  5. typedef long long ll;
  6. int main()
  7. {
  8. ios_base::sync_with_stdio(0);
  9. // ifstream cin("input.txt");
  10. // ofstream cout("output.txt");
  11. cin.tie(0);cout.tie(0);
  12.  
  13. ll a,b;
  14. cin>>a>>b;
  15.  
  16. ll l = 0, r = sqrtl(1ll*2*(a+b));
  17. while(l+1<r)
  18. {
  19. ll med = (l + r)>>1;
  20. ll i = med;
  21. ll bufa = a,bufb = b;
  22. while(1)
  23. {
  24. if(i==0) break;
  25. if(bufa<=bufb&&bufa>=i)
  26. {
  27. bufa-=i;
  28. i--;
  29. }
  30. else if(bufb>=i)
  31. {
  32. bufb-=i;
  33. i--;
  34. }
  35. else if(bufa>=i)
  36. {
  37. bufa-=i;
  38. i--;
  39. }
  40. else break;
  41. }
  42. if(i==0)
  43. {
  44. l = med;
  45. }
  46. else if(i<0) l = med + 1;
  47. else r = med - 1;
  48. }
  49. // check r
  50. ll i = r;
  51. vector<ll> ansa,ansb;
  52. ll bufa = a,bufb = b;
  53. while(1)
  54. {
  55. if(i==0) break;
  56. if(bufa<=bufb&&bufa>=i)
  57. {
  58. bufa-=i;
  59. ansa.push_back(i);
  60. i--;
  61. }
  62. else if(bufb>=i)
  63. {
  64. bufb-=i;
  65. ansb.push_back(i);
  66. i--;
  67. }
  68. else if(bufa>=i)
  69. {
  70. bufa-=i;
  71. ansa.push_back(i);
  72. i--;
  73. }
  74. else break;
  75. }
  76. if(i<=0)
  77. {
  78. cout<<ansa.size()<<"\n";
  79. FI(ansa.size()) cout<<ansa[i]<<" ";
  80. cout<<"\n"<<ansb.size()<<"\n";
  81. FI(ansb.size()) cout<<ansb[i]<<" ";
  82. return 0;
  83. }
  84. i = l;
  85. ansa.clear();
  86. ansb.clear();
  87. bufa = a;
  88. bufb = b;
  89. while(1)
  90. {
  91. if(i==0) break;
  92. if(bufa<=bufb&&bufa>=i)
  93. {
  94. bufa-=i;
  95. ansa.push_back(i);
  96. i--;
  97. }
  98. else if(bufb>=i)
  99. {
  100. bufb-=i;
  101. ansb.push_back(i);
  102. i--;
  103. }
  104. else if(bufa>=i)
  105. {
  106. bufa-=i;
  107. ansa.push_back(i);
  108. i--;
  109. }
  110. else break;
  111. }
  112. cout<<ansa.size()<<"\n";
  113. FI(ansa.size()) cout<<ansa[i]<<" ";
  114. cout<<"\n"<<ansb.size()<<"\n";
  115. FI(ansb.size()) cout<<ansb[i]<<" ";
  116.  
  117.  
  118.  
  119.  
  120. // cin.close();
  121. // cout.close();
  122. return 0;
  123. }
Add Comment
Please, Sign In to add comment