| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 873342 |
2023-11-14T21:17:12 Z |
rainboy |
Shuffle (NOI19_shuffle) |
C++17 |
|
2 ms |
2652 KB |
#include "shuffle.h"
#include <cstring>
#include <vector>
using namespace std;
const int N = 1000, L = 11; /* L = ceil(log2(N)) + 1 */
typedef vector<int> vi;
typedef vector<vi> vvi;
int n, m, k, l;
int pp[L], xx[N], idx[N * N], uu[N], vv[N], cc[N], yy[N], kk[N][N], zz[N];
vvi iii, aaa, aaa_; vi aa;
void shuffle_(vvi iii, vvi &aaa) {
aaa = shuffle(iii);
for (int d = 0; d < m; d++)
for (int g = 0; g < k; g++)
aaa[d][g]--;
}
void init(int n, int m) {
l = 1, pp[0] = 1;
while (pp[l - 1] < n)
pp[l] = pp[l - 1] * m, l++;
for (int i = 0; i < n; i++) {
int x = i + 1 < n ? i : pp[l - 1];
idx[xx[i] = x] = i;
}
if (m == 3 && l == 7)
l--, idx[xx[k - 1] = 486] = k - 1;
}
void solvep() {
for (int d = 0; d < n / 2; d++)
iii[d].clear();
for (int d = 0; d < n / 2; d++)
iii[d] = { d * 2 + 1, d * 2 + 2 };
shuffle_(iii, aaa);
for (int d = 0; d < n / 2; d++) {
int a = aaa[d][0], b = aaa[d][1];
uu[a] = b, uu[b] = a;
}
for (int d = 0; d + 1 < n / 2; d++)
iii[d] = { d * 2 + 2, d * 2 + 3 };
iii[n / 2 - 1] = { n, 1 };
shuffle_(iii, aaa);
for (int d = 0; d < n / 2; d++) {
int a = aaa[d][0], b = aaa[d][1];
vv[a] = b, vv[b] = a;
}
for (int i = 2, j = n - 1; j - i > 3; i++, j--)
iii[i - 2] = { i + 1, j + 1 };
iii[n / 2 - 3] = { n / 2, n / 2 + 2 };
iii[n / 2 - 2] = { n / 2 + 1, n / 2 + 3 };
iii[n / 2 - 1] = { 1, 2 };
shuffle_(iii, aaa);
int a_ = -1, b_ = -1;
for (int d = 0; d < n / 2; d++) {
int a = aaa[d][0], b = aaa[d][1];
if (uu[a] == b) {
a_ = a, b_ = b;
break;
}
}
for (int i = 1, j = n - 2; j - i > 3; i++, j--)
iii[i - 1] = { i + 1, j + 1 };
iii[n / 2 - 3] = { n / 2 - 1, n / 2 + 1 };
iii[n / 2 - 2] = { n / 2, n / 2 + 2 };
iii[n / 2 - 1] = { n, 1 };
shuffle_(iii, aaa);
for (int d = 0; d < n / 2; d++) {
int a = aaa[d][0], b = aaa[d][1];
if (vv[a] == b) {
if (b_ == a || b_ == b)
a_ = b_;
break;
}
}
for (int i = 0, a = a_; i < n; i++) {
aa[i] = a + 1;
a = i % 2 == 0 ? uu[a] : vv[a];
}
}
void solvek() {
for (int d = 0; d < m; d++)
iii[d].clear();
for (int i = 0; i < n; i++)
iii[i / k].push_back(i + 1);
shuffle_(iii, aaa_);
for (int c = 0; c < m; c++)
for (int g = 0; g < k; g++)
cc[aaa_[c][g]] = c;
init(k, 2);
memset(yy, 0, n * sizeof *yy);
for (int h = 0; h < l; h++) {
for (int d = 0; d < m; d++)
iii[d].clear();
for (int i = 0; i < n; i++)
iii[(i / k + (xx[i % k] >> h & 1)) % m].push_back(i + 1);
shuffle_(iii, aaa);
for (int d = 0; d < m; d++) {
int u = -1, v = -1, diff = 0;
for (int g = 0; g < k; g++) {
int c = cc[aaa[d][g]];
if (u == -1 || c == u)
u = c, diff++;
else
v = c, diff--;
}
if (diff > 0) {
int tmp;
tmp = u, u = v, v = tmp;
}
if (u != -1)
vv[u] = v;
for (int g = 0; g < k; g++) {
int a = aaa[d][g], c = cc[a];
if (c == u)
yy[a] |= 1 << h;
}
}
}
for (int d = 0; d < m; d++)
iii[d].clear();
for (int i = 0; i < k; i++)
iii[0].push_back(i + 1);
for (int i = k; i < n; i++)
iii[i / k].push_back((i - k + 1) % (n - k) + k + 1);
shuffle_(iii, aaa);
for (int d = 0; d < m; d++) {
int c_ = -1;
for (int g = 0; g < k; g++) {
int c = cc[aaa[d][g]];
if (c_ == -1 || c == c_)
c_ = c;
else {
c_ = -1;
break;
}
}
if (c_ != -1) {
for (int d = 0, c = c_; d < m; d++, c = vv[c])
for (int g = 0; g < k; g++) {
int a = aaa_[c][g];
aa[d * k + idx[yy[a]]] = a + 1;
}
break;
}
}
}
void solvem() {
init(k, m);
for (int g = k - 1; g >= 0; g--) {
int x = xx[g];
for (int d = 0; d < m; d++) {
int x_ = 0;
for (int h = 0; h < l; h++)
x_ += (x / pp[h] + d) % m * pp[h];
x_ = x_ * m + d;
idx[xx[g * m + d] = x_] = g * m + d;
}
}
pp[l] = pp[l - 1] * m, l++;
memset(yy, 0, n * sizeof *yy);
for (int h = 0; h < l; h++) {
for (int d = 0; d < m; d++)
iii[d].clear();
for (int i = 0; i < n; i++)
iii[xx[i] / pp[h] % m].push_back(i + 1);
shuffle_(iii, aaa);
for (int d = 0; d < m; d++)
for (int g = 0; g < k; g++)
yy[aaa[d][g]] += d * pp[h];
}
for (int h = 1; h < l; h++) {
for (int c = 0; c < m; c++)
memset(kk[c], 0, m * sizeof *kk[c]);
for (int a = 0; a < n; a++) {
int c = yy[a] % m, d = yy[a] / pp[h] % m;
kk[c][d]++;
}
for (int c = 0; c < m; c++) {
int d_ = -1;
for (int d = 0; d < m; d++)
if (d_ == -1 || kk[c][d_] < kk[c][d])
d_ = d;
cc[d_] = c;
}
for (int a = 0; a < n; a++) {
int d = yy[a] / pp[h] % m;
yy[a] = yy[a] + (cc[d] - d) * pp[h];
}
}
if (m == 2) {
for (int d = 0; d < 2; d++)
iii[d].clear();
iii[0].push_back(1);
for (int i = 2; i <= n / 2; i++)
iii[0].push_back(i + 1);
iii[1].push_back(2);
for (int i = n / 2 + 1; i < n; i++)
iii[1].push_back(i + 1);
shuffle_(iii, aaa);
for (int d = 0; d < 2; d++)
for (int g = 0; g < n / 2; g++)
if (yy[aaa[d][g]] == 0) {
int flip = 1;
for (g = 0; g < n / 2; g++)
if (yy[aaa[d][g]] == 2) {
flip = 0;
break;
}
if (flip)
for (int a = 0; a < n; a++)
yy[a] ^= (1 << l) - 1;
goto out;
}
out:;
} else {
for (int a = 0; a < n; a++)
cc[a] = yy[a] % m;
memset(zz, 0, m * sizeof *zz);
for (int h = 0; 1 << h < m; h++) {
for (int d = 0; d < m; d++)
iii[d].clear();
for (int i = 0; i < n; i++)
iii[i % m].push_back(i + 1);
for (int c = 0, c_ = -1; c < m; c++)
if ((c & 1 << h) == 0) {
if (c_ != -1) {
int tmp;
tmp = iii[c][0], iii[c][0] = iii[c_][0], iii[c_][0] = tmp;
}
c_ = c;
}
shuffle_(iii, aaa);
for (int d = 0; d < m; d++) {
int c_ = -1;
for (int g = 0; g < k; g++) {
int c = cc[aaa[d][g]];
if (c_ == -1 || c == c_)
c_ = c;
else {
c_ = -1;
break;
}
}
if (c_ != -1)
zz[c_] |= 1 << h;
}
}
for (int a = 0; a < n; a++) {
int y = 0;
for (int h = 0; h < l; h++)
y += zz[yy[a] / pp[h] % m] * pp[h];
yy[a] = y;
}
}
for (int a = 0; a < n; a++)
aa[idx[yy[a]]] = a + 1;
}
vi solve(int n_, int m_, int k_, int q, int s) {
n = n_, m = m_, k = k_;
iii.resize(m), aa.resize(n);
if (k == 2)
solvep();
else if (k <= 64 && m != 2)
solvek();
else
solvem();
return aa;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2500 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 4 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 12 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 13 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 14 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 15 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 16 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 17 |
Correct |
1 ms |
2500 KB |
Output is correct |
| 18 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2396 KB |
Output is correct |
