Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- #define F first
- #define S second
- long long s = 1234;
- long long get(long long x) {
- const long long a = 134775813;
- const long long c = 1;
- long long sn = (a * s + c) % (1ll << 32);
- s = sn;
- return (sn * x) >> 32;
- }
- namespace gen{
- vector<pair<long long, long long>> gen(int n, bool shuffled) {
- vector<long long> a;
- for (int i = 0; i < 2 * n; i++) {
- a.push_back(get(100000000));
- if (a.back() < 0)
- cerr << "kek" << endl;
- }
- if (shuffled) {
- for (int i = 1; i <= 2 * n; i++) {
- swap(a[i - 1], a[get(i)]);
- }
- }
- vector<pair<ll, ll>> ans;
- for (int i = 0; i < n; i++) {
- ans.push_back({a[i << 1], a[i << 1 | 1]});
- }
- return ans;
- }
- }
- mt19937_64 rnd;
- bool is_shuffled(vector<pair<ll, ll>> vv) {
- ll n = vv.size() * 2;
- vector<ll> v(n);
- for (int i = 0, j = 0; i < n; i += 2, j++) {
- v[i] = vv[j].first;
- v[i + 1] = vv[j].second;
- }
- ll x = 100000000;
- ll a = 134775813;
- ll c = 1;
- ll pt = 1ll << 32;
- while (1.0 * clock() / CLOCKS_PER_SEC <= 2.9) {
- ll s = abs(rand()) % pt;
- ll curs = s;
- ll first = curs * x / pt;
- vector<int> p;
- for (int i = 0; i < n - 100; ++i) {
- if (v[i] == first) {
- p.push_back(i);
- }
- }
- if (p.size() != 0)
- cerr << "!\n";
- for (int j = 0; j < p.size(); ++j) {
- bool f = 1;
- curs = s;
- for (int i = p[j] + 1; i < p[j] + 100; ++i) {
- curs = (a * curs + c) % pt;
- ll cur = curs * x / pt;
- if (cur != v[i]) {
- cerr << s << " " << curs << endl;
- cerr << cur << " " << v[i] << " " << v[p[j]] << " " << i - p[j] << endl;
- f = 0;
- break;
- }
- }
- if (f) {
- return 0;
- }
- }
- }
- return 1;
- }
- void out(vector<pair<ll, ll>> a) {
- for (int i = 0; i < a.size(); i++) {
- cout << "{" << a[i].F << ", " << a[i].S << "} ";
- }
- }
- bool test() {
- for (int i = 0; i < 10; i++) {
- int n = rand() % 90000 + 10000;
- auto cur = gen::gen(n, 0);
- auto cur1 = gen::gen(n, 1);
- if (is_shuffled(cur) != 0) {
- cout << "kek0" << endl;
- break;
- }
- if (is_shuffled(cur1) != 1) {
- cout << "kek1" << endl;
- break;
- }
- cerr << i << endl;
- }
- }
- int main() {
- ios_base::sync_with_stdio(0);
- test();
- return 0;
- int n;
- cin >> n;
- vector<pair<ll, ll>> a(n);
- for (int i = 0; i < n; i++) cin >> a[i].F >> a[i].S;
- if (is_shuffled(a)) {
- cout << "SHUFFLED" << endl;
- } else {
- cout << "RAW" << endl;
- }
- #ifdef LOCAL
- // cerr << fixed << 1.0 * clock()
- #endif // LOCAL
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement