Submission #991536

#TimeUsernameProblemLanguageResultExecution timeMemory
991536SharkyBroken Device (JOI17_broken_device)C++17
41 / 100
42 ms2908 KiB
#include "Annalib.h" #include <bits/stdc++.h> using namespace std; namespace anna { const long long purple = 694202512019219198LL; const int amogus = 696969; mt19937 rng(amogus); vector<int> p(151), inv(151); int rnd(int u, int v) { return uniform_int_distribution<int> (u, v) (rng); } void gen_perm() { for (int i = 0; i < 150; i++) p[i] = i; for (int i = 0; i < 150; i++) swap(p[rnd(0, 149)], p[rnd(0, 149)]); for (int i = 0; i < 150; i++) inv[p[i]] = i; } } using namespace anna; // p = 3 1 2 4 0 // inv[3] = 0; // inv[1] = 1; // inv[2] = 2; // inv[4] = 3; // inv[0] = 4; // inv = {4, 1, 2, 0, 3}; // say P = {4} // new P = {0} // 0: 1 // 1: 2 // 01: 3 // 11: 4 void Anna(int N, long long _X, int K, int P[]){ long long X = _X; gen_perm(); X ^= purple; // cout << X << '\n'; vector<int> bit, seq(N, 0), li; for (int i = 59; i >= 0; i--) bit.push_back((X & (1LL << i)) ? 1 : 0); // for (int i = 0; i < 60; i++) cout << bit[i]; // cout << '\n'; li.push_back(-1); vector<int> pp(K, 0); for (int i = 0; i < K; i++) { pp[i] = p[P[i]]; li.push_back(pp[i]); }; li.push_back(N); sort(li.begin(), li.end()); int cur = 0; int ptr = 0; for (int i = 1; i < li.size(); i++) { int l = li[i - 1] + 1, r = li[i] - 1; if (l > r) continue; // cout << l << ' ' << r << '\n'; ptr = l; int dist = r - l + 1; while (true) { if (cur < 59 && bit[cur] == 1 && bit[cur + 1] == 1 && dist >= 2) { dist -= 2; cur += 2; seq[ptr] = seq[ptr + 1] = 1; ptr += 2; } else if (cur < 59 && bit[cur] == 0 && bit[cur + 1] == 1 && dist >= 1) { dist -= 1; cur += 2; seq[ptr] = 1; ptr += 1; } else if (cur < 59 && bit[cur] == 1 && bit[cur + 1] == 0 && dist >= 3) { dist -= 3; cur += 2; seq[ptr] = seq[ptr + 1] = seq[ptr + 2] = 1; ptr += 3; } else if (cur < 59 && bit[cur] == 0 && bit[cur + 1] == 0 && dist >= 4) { dist -= 4; cur += 2; seq[ptr] = seq[ptr + 1] = seq[ptr + 2] = seq[ptr + 3] = 1; ptr += 4; } else break; if (ptr <= r) seq[ptr++] = 0, dist--; } while (ptr <= r) seq[ptr++] = 0; } // for (int i = 0; i < N; i++) cout << seq[i] << ' '; // cout << '\n'; vector<int> vt; for (int i = 0; i < N; i++) { // if (seq[i]) cout << inv[i] << ' '; Set(inv[i], seq[i]); } // cout << '\n'; }
#include "Brunolib.h" #include <bits/stdc++.h> using namespace std; namespace bruno { const long long purple = 694202512019219198LL; const int amogus = 696969; mt19937 rng(amogus); vector<int> p(151), inv(151); int rnd(int u, int v) { return uniform_int_distribution<int> (u, v) (rng); } void gen_perm() { for (int i = 0; i < 150; i++) p[i] = i; for (int i = 0; i < 150; i++) swap(p[rnd(0, 149)], p[rnd(0, 149)]); for (int i = 0; i < 150; i++) inv[p[i]] = i; } } using namespace bruno; // 0: 1 // 1: 2 // 01: 3 // 11: 4 long long Bruno(int N, int A[]) { gen_perm(); vector<int> bits; long long X = 0; vector<int> a(N), z, g; for (int i = 0; i < N; i++) { a[i] = A[inv[i]]; // if (a[i]) cout << inv[i] << ' '; } // cout << '\n'; // for (int i = 0; i < N; i++) cout << a[i] << ' '; // cout << '\n'; z.push_back(-1); for (int i = 0; i < N; i++) if (!a[i]) z.push_back(i); z.push_back(N); for (int i = 1; i < z.size(); i++) g.push_back(z[i] - z[i - 1] - 1); for (int i = 0; i < g.size(); i++) { if (g[i] == 4) { bits.push_back(0); bits.push_back(0); } else if (g[i] == 3) { bits.push_back(1); bits.push_back(0); } else if (g[i] == 2) { bits.push_back(1); bits.push_back(1); } else if (g[i] == 1) { bits.push_back(0); bits.push_back(1); } } for (int i = 0; i < bits.size(); i++) { X *= 2LL; X += bits[i]; // cout << bits[i]; } // cout << '\n'; // cout << X << '\n'; X ^= purple; return X; }

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int, long long int, int, int*)':
Anna.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 1; i < li.size(); i++) {
      |                     ~~^~~~~~~~~~~

Bruno.cpp: In function 'long long int Bruno(int, int*)':
Bruno.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 1; i < z.size(); i++) g.push_back(z[i] - z[i - 1] - 1);
      |                     ~~^~~~~~~~~~
Bruno.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 0; i < g.size(); i++) {
      |                     ~~^~~~~~~~~~
Bruno.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 0; i < bits.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...