Advertisement
Guest User

Untitled

a guest
Dec 18th, 2018
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.07 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7.  
  8. #define F first
  9. #define S second
  10.  
  11. long long s = 1234;
  12. long long get(long long x) {
  13. const long long a = 134775813;
  14. const long long c = 1;
  15. long long sn = (a * s + c) % (1ll << 32);
  16. s = sn;
  17. return (sn * x) >> 32;
  18. }
  19.  
  20. namespace gen{
  21.  
  22.  
  23.  
  24. vector<pair<long long, long long>> gen(int n, bool shuffled) {
  25. vector<long long> a;
  26. for (int i = 0; i < 2 * n; i++) {
  27. a.push_back(get(100000000));
  28. if (a.back() < 0)
  29. cerr << "kek" << endl;
  30. }
  31. if (shuffled) {
  32. for (int i = 1; i <= 2 * n; i++) {
  33. swap(a[i - 1], a[get(i)]);
  34. }
  35. }
  36. vector<pair<ll, ll>> ans;
  37. for (int i = 0; i < n; i++) {
  38. ans.push_back({a[i << 1], a[i << 1 | 1]});
  39. }
  40. return ans;
  41. }
  42.  
  43. }
  44. mt19937_64 rnd;
  45.  
  46. bool is_shuffled(vector<pair<ll, ll>> vv) {
  47. ll n = vv.size() * 2;
  48. vector<ll> v(n);
  49. for (int i = 0, j = 0; i < n; i += 2, j++) {
  50. v[i] = vv[j].first;
  51. v[i + 1] = vv[j].second;
  52. }
  53. ll x = 100000000;
  54. ll a = 134775813;
  55. ll c = 1;
  56. ll pt = 1ll << 32;
  57. while (1.0 * clock() / CLOCKS_PER_SEC <= 2.9) {
  58. ll s = abs(rand()) % pt;
  59. ll curs = s;
  60. ll first = curs * x / pt;
  61. vector<int> p;
  62. for (int i = 0; i < n - 100; ++i) {
  63. if (v[i] == first) {
  64. p.push_back(i);
  65. }
  66. }
  67. if (p.size() != 0)
  68. cerr << "!\n";
  69. for (int j = 0; j < p.size(); ++j) {
  70. bool f = 1;
  71. curs = s;
  72. for (int i = p[j] + 1; i < p[j] + 100; ++i) {
  73. curs = (a * curs + c) % pt;
  74. ll cur = curs * x / pt;
  75. if (cur != v[i]) {
  76. cerr << s << " " << curs << endl;
  77. cerr << cur << " " << v[i] << " " << v[p[j]] << " " << i - p[j] << endl;
  78. f = 0;
  79. break;
  80. }
  81. }
  82. if (f) {
  83. return 0;
  84. }
  85. }
  86. }
  87. return 1;
  88. }
  89.  
  90. void out(vector<pair<ll, ll>> a) {
  91. for (int i = 0; i < a.size(); i++) {
  92. cout << "{" << a[i].F << ", " << a[i].S << "} ";
  93. }
  94. }
  95.  
  96. bool test() {
  97. for (int i = 0; i < 10; i++) {
  98. int n = rand() % 90000 + 10000;
  99. auto cur = gen::gen(n, 0);
  100. auto cur1 = gen::gen(n, 1);
  101. if (is_shuffled(cur) != 0) {
  102. cout << "kek0" << endl;
  103. break;
  104. }
  105. if (is_shuffled(cur1) != 1) {
  106. cout << "kek1" << endl;
  107. break;
  108. }
  109. cerr << i << endl;
  110. }
  111. }
  112.  
  113. int main() {
  114. ios_base::sync_with_stdio(0);
  115. test();
  116. return 0;
  117. int n;
  118. cin >> n;
  119. vector<pair<ll, ll>> a(n);
  120. for (int i = 0; i < n; i++) cin >> a[i].F >> a[i].S;
  121. if (is_shuffled(a)) {
  122. cout << "SHUFFLED" << endl;
  123. } else {
  124. cout << "RAW" << endl;
  125. }
  126. #ifdef LOCAL
  127. // cerr << fixed << 1.0 * clock()
  128. #endif // LOCAL
  129. return 0;
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement