Advertisement
Guest User

Untitled

a guest
Feb 11th, 2022
296
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.57 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n, testCase, target, d, cur, change;
  4. int nums[10], dbg[10], has[300];
  5. bool used[10];
  6. class IO {
  7. private:
  8. // string inFile, outFile;
  9. // ifstream in;
  10. // ofstream out;
  11. public:
  12. IO () {}
  13. void print() {
  14. for (int i = 1; i < 10; i++) {
  15. cout << nums[i] << " \n"[i==9];
  16. has[nums[i]]++;
  17. }
  18. }
  19. void print1() {
  20. for (int i = 1; i < 10; i++) dbg[i] = nums[i];
  21. // sort(dbg+1, dbg+9);
  22. for (int i = 1; i < 10; i++)
  23. cout << dbg[i] << " \n"[i==9];
  24. }
  25. void start() {
  26. cin >> testCase >> n;
  27. for (int i = 0; i < 300; i++) has[i] = 0;
  28. cout << "FILE reverse " << testCase << '\n';
  29. }
  30. void show(int pos) {
  31. assert(nums[pos] == target);
  32. used[pos] = 1;
  33. cout << "P " << pos << '\n';
  34. target--;
  35. }
  36. void assign(int a, int b) {
  37. assert(a * b != 0);
  38. cout << "S " << a << ' ' << b << '\n';
  39. has[nums[b]]--;
  40. nums[b] = nums[a] + 1;
  41. has[nums[b]]++;
  42. }
  43. } io;
  44.  
  45. void solve() {
  46. io.start();
  47. nums[0] = -100;
  48. target = n;
  49. // the answer is within range 0...4
  50. if (n <= 8) {
  51. for (int i = 1; i < 10; i++)
  52. nums[i] = i - 1;
  53. } else if (n <= 44) {
  54. d = 1;
  55. nums[9] = n;
  56. for (int i = 1; i < 9; i++)
  57. nums[9-i] = max(0, nums[9-i+1] - (1+d*i));
  58. } else if (n <= 101) {
  59. d = 2;
  60. nums[9] = n;
  61. nums[8] = nums[9]-d-1;
  62. nums[7] = nums[8]-2*d-1;
  63. int D = 3, X = 2;
  64. for (int i = 6; i > 0; i--) {
  65. nums[i] = max(0, nums[i+1]-d*D-X);
  66. D++, X++;
  67. }
  68. } else if (n <= 130) { // actually n <= 173 but because of bad testcase and wrong answer it has to be between 112 and 139
  69. d = 3;
  70. nums[9] = n;
  71. nums[8] = nums[9]-d-1;
  72. nums[7] = nums[8]-2*d-1;
  73. int D = 12;
  74. for (int i = 6; i > 0; i--) {
  75. nums[i] = max(0, nums[i+1]-D);
  76. D += 6;
  77. }
  78. } else { // limit 257
  79. d = 4;
  80. nums[9] = n;
  81. nums[8] = nums[9]-d-1;
  82. nums[7] = nums[8]-2*d-1;
  83. int D = 18;
  84. for (int i = 6; i > 0; i--) {
  85. nums[i] = max(0, nums[i+1]-D);
  86. D += 9;
  87. }
  88. }
  89. io.print();
  90. while (1) {
  91. cur = 0;
  92. while(cur < 10 && nums[cur] != target) cur++;
  93. io.show(cur);
  94. if (target < 0) break;
  95. int need = 0, ext;
  96. while(need <= target &&!has[target-need]) need++;
  97. change = 0;
  98. for (int i = 1; i < 10; i++)
  99. if (nums[i] == target-need) change = i;
  100. if (change && need > 0) {
  101. io.assign(change, cur);
  102. for (int j = 1; j < need; j++)
  103. io.assign(cur, cur);
  104. }
  105. ext = d - need;
  106. change = 0;
  107. if (ext == d) {
  108. // don't need to find cur
  109. for (int i = 1; i < 10; i++) {
  110. bool x = 1;
  111. for (int j = 1; j <= d; j++) {
  112. if (has[nums[i]+j]) x = 0;
  113. }
  114. if (nums[i] >= nums[change] &&
  115. nums[i]+d < target &&
  116. !has[nums[i]+d] &&
  117. !has[nums[i]+d+1] &&
  118. x) change = i;
  119. }
  120. } else {
  121. // find cur
  122. for (int i = 1; i < 10; i++) {
  123. bool x = 1;
  124. for (int j = 1; j <= d; j++) {
  125. if (has[nums[i]+j]) x = 0;
  126. }
  127. if (nums[i]+d < target &&
  128. nums[i] > nums[change] &&
  129. !has[nums[i]+d] &&
  130. used[i] &&
  131. x) change = i;
  132. }
  133. cur = change;
  134. }
  135. if (change && ext > 0) {
  136. io.assign(change, cur);
  137. for (int j = 1; j < ext; j++) io.assign(cur, cur);
  138. }
  139. }
  140.  
  141. }
  142. signed main() {
  143. ios::sync_with_stdio();
  144. cin.tie(0);
  145. cout.tie(0);
  146. int st = 0, ed = 15;
  147. // for all testcases:
  148. // for (int i = st; i <= ed; i++) {
  149. // string c = "inputs/reverse."+to_string(i)+".in";
  150. // freopen(c.c_str(), "r", stdin);
  151. // string d = "outputs/reverse."+to_string(i)+".out";
  152. // freopen(d.c_str(), "w", stdout);
  153. // solve();
  154. // }
  155. solve();
  156. }
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement