#include "shuffle.h"
#include <bits/stdc++.h>
using namespace std;
const int NN = 1e3 + 10;
int n, b, k;
int g1[NN], g2[NN], g3[NN], match1[NN], match2[NN];
int lab[NN], group[NN], g_val[NN], g_pos[NN], cnt[NN];
vector<int> arr_pos[NN];
vector<int> arr_val[NN];
void reset (vector<vector<int> > &arr) {
for(int i = 0; i < arr.size(); i++) arr[i].clear();
}
int id (int x) {
return (x + k - 1) / k;
}
vector<int> solve_2 () {
int cnt = 0;
vector<vector<int> > ask(b);
vector<int> ret, unique1, unique2;
for(int i = 1; i <= n; i++) ask[id(i) - 1].push_back(i);
vector<vector<int> > tmp1 = shuffle(ask);
for(auto &arr: tmp1) {
++cnt;
for(auto &j : arr) g1[j] = cnt;
match1[arr[0]] = arr[1];
match1[arr[1]] = arr[0];
} cnt = 0;
for(int i = 1; i + 1 < b; i++) swap(ask[i].back(), ask[i + 1].back());
vector<vector<int> > tmp3 = shuffle(ask);for(auto &arr : tmp3) {
bool ok = 1;
int group = g1[arr[0]];
for(auto &j : arr) ok &= g1[j] == group;
if (ok) unique1 = arr;
}
reset(ask);
for(int i = 2; i <= n; i++) ask[id(i - 1) - 1].push_back(i);
ask[b - 1].push_back(1);
vector<vector<int> > tmp2 = shuffle(ask);
for(auto &arr : tmp2) {
++cnt;
for(auto &j : arr) g2[j] = cnt;
match2[arr[0]] = arr[1];
match2[arr[1]] = arr[0];
} cnt = 0;
for(int i = 0; i + 2 < b; i++) swap(ask[i].back(), ask[i + 1].back());
vector<vector<int> > tmp4 = shuffle(ask);
for(auto &arr : tmp4) {
bool ok = 1;
int group = g2[arr[0]];
for(auto &j : arr) ok &= g2[j] == group;
if (ok) unique2 = arr;
}
reset(ask);
assert(!unique1.empty());
assert(!unique2.empty());
for(int &j : unique1) for(int &k : unique2) if (j == k) lab[1] = j;
assert(lab[1]);
for(int i = 1; i < n; i++) {
if (i % 2) lab[i + 1] = match1[lab[i]];
else lab[i + 1] = match2[lab[i]];
}
#ifdef ngu
for(int i = 1; i <= n; i++) cout << lab[i] << " "; cout << endl;
#endif // ngu
for(int i = 1; i <= n; i++) ret.push_back(lab[i]);
return ret;
}
vector<int> solve_3 () {
vector<vector<int> > ask(b);
for(int i = 1; i <= n; i++) ask[id(i) - 1].push_back(i);
vector<vector<int> > get1 = shuffle(ask);
for(int i = 0; i < b; i++) {
for(auto &j : get1[i]) g1[j] = i;
}
ask.clear();
ask.resize(b);
for(int i = 2; i <= n; i++) ask[id(i - 1) - 1].push_back(i);
ask[b - 1].push_back(1);
vector<vector<int> > get2 = shuffle(ask);
for(int i = 0; i < b; i++) {
for(auto &j : get2[i]) g2[j] = i;
}
ask.clear();
ask.resize(b);
for(int i = 1; i <= n; i++) ask[id(i) - 1].push_back(i);
for(int j = 1; j < k; j++) swap(ask[0][j], ask[1][j - 1]);
vector<vector<int> > get3 = shuffle(ask);
for(int i = 0; i < b; i++) {
for(auto &j : get3[i]) g3[j] = i;
}
ask.clear();
for(int val = 1; val <= n; val++) {
bool ok = 1;
for(int _val = 1; _val <= n; _val++) if (val != _val) {
if (g1[val] == g1[_val]) {
ok &= g2[val] != g2[_val];
ok &= g3[val] != g3[_val];
}
}
if (ok) {
assert(lab[1] == 0);
lab[1] = val;
}
}
for(int loop = 1, x = 1; loop < b; loop++) {
int old = x;
for(int i = 0; i < b; i++) {
int diff = 0, val = 0;
for(auto &j : get2[i]) if (g1[j] != g1[lab[x]]) {
diff++;
val = j;
}
if (diff == 1) {
x += k;
lab[x] = val;
assert(lab[x]);
break;
}
}
assert(x > old);
}
// for(int i = 1; i <= n; i++) cout << g1[i] << " "; cout << endl;
// for(int i = 1; i <= n; i++) cout << g2[i] << " "; cout << endl;
// for(int x = 1; x <= n; x += k) {
// cout << lab[x] << endl;
// }
//
// exit(0);
vector<vector<int> > pos, val;
for(int x = 1; x <= n; x += k) {
vector<int> tmp_pos, tmp_val;
for(int i = x + 1; i <= x + k - 1; i++) {
tmp_pos.push_back(i);
}
for(int i = 1; i <= n; i++) if (g1[lab[x]] == g1[i] && i != lab[x]) {
tmp_val.push_back(i);
}
pos.push_back(tmp_pos);
val.push_back(tmp_val);
}
for(int x = 1; x <= n; x += k) {
group[lab[x]] = id(x);
}
for(int loop = 1; loop <= 6; loop++) {
ask.clear();
ask.resize(b);
bool stop = 1;
// for(int i = 0; i < pos.size(); i++) {
// for(auto &j : pos[i]) cout << j << " "; cout << endl;
// for(auto &j : val[i]) cout << j << " "; cout << endl;
// cout << endl;
// }
for(int i = 0; i < pos.size(); i++) stop &= pos[i].size() == 1;
if (stop) break;
vector<vector<int> > _pos, _val;
for(int x = 1; x <= n; x += k) ask[id(x) - 1].push_back(x);
assert(pos.size() == val.size());
for(int i = 0; i < pos.size(); i++) {
assert(pos[i].size() == val[i].size());
int max_cnt = (pos[i].size() + b - 1) / b;
for(auto &j : pos[i]) {
int nxt = -1;
for(int y = 0; y < b; y++) if (cnt[y] < max_cnt) {
if (nxt == -1 || ask[nxt].size() > ask[y].size()) nxt = y;
}
assert(nxt >= 0);
assert(ask[nxt].size() < k);
ask[nxt].push_back(j);
cnt[nxt]++;
g_pos[j] = nxt;
// cout << j << " " << g_pos[j] << endl;
}
for(int j = 0; j < b; j++) cnt[j] = 0;
}
// cout << endl;
for(int i = 0; i < b; i++) assert(ask[i].size() == k);
vector<vector<int> > get = shuffle(ask);
for(auto &arr : get) {
int root = -1;
for(auto &j : arr) {
if (group[j]) {
assert(root == -1);
root = group[j] - 1;
}
}
for(auto &j : arr) if (!group[j]) {
g_val[j] = root;
// cout << j << " " << root << endl;
}
}
for(int i = 0; i < pos.size(); i++) {
for(auto &j : pos[i]) arr_pos[g_pos[j]].push_back(j);
for(auto &j : val[i]) arr_val[g_val[j]].push_back(j);
for(int j = 0; j < b; j++) if (!arr_pos[j].empty()) {
// for(auto &l : arr_pos[j]) cout << l << " " ; cout << endl;
// for(auto &l : arr_val[j]) cout << l << " " ; cout << endl;
// cout << endl;
_pos.push_back(arr_pos[j]);
_val.push_back(arr_val[j]);
arr_pos[j].clear();
arr_val[j].clear();
}
}
pos = move(_pos);
val = move(_val);
}
for(int i = 0; i < pos.size(); i++) {
assert(pos[i].size() == 1);
lab[pos[i][0]] = val[i][0];
}
#ifdef ngu
for(int i = 1; i <= n; i++) cout << lab[i] << " ";
cout << endl;
#endif // ngu
// exit(0);
vector<int> ret;
for(int i = 1; i <= n; i++) ret.push_back(lab[i]);
return ret;
}
vector<int> solve(int N, int B, int K, int Q, int ST) {
n = N;
b = B;
k = K;
if (k == 2) return solve_2();
return solve_3();
}
Compilation message
shuffle.cpp: In function 'void reset(std::vector<std::vector<int> >&)':
shuffle.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i = 0; i < arr.size(); i++) arr[i].clear();
| ~~^~~~~~~~~~~~
shuffle.cpp: In function 'std::vector<int> solve_3()':
shuffle.cpp:182:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
182 | for(int i = 0; i < pos.size(); i++) stop &= pos[i].size() == 1;
| ~~^~~~~~~~~~~~
shuffle.cpp:187:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
187 | for(int i = 0; i < pos.size(); i++) {
| ~~^~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from shuffle.cpp:2:
shuffle.cpp:196:32: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
196 | assert(ask[nxt].size() < k);
| ~~~~~~~~~~~~~~~~^~~
shuffle.cpp:206:53: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
206 | for(int i = 0; i < b; i++) assert(ask[i].size() == k);
| ~~~~~~~~~~~~~~^~~~
shuffle.cpp:223:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
223 | for(int i = 0; i < pos.size(); i++) {
| ~~^~~~~~~~~~~~
shuffle.cpp:241:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
241 | for(int i = 0; i < pos.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
496 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
508 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
756 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
600 KB |
Output is correct |
| 5 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
860 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Correct |
3 ms |
600 KB |
Output is correct |
| 5 |
Correct |
3 ms |
604 KB |
Output is correct |
| 6 |
Correct |
3 ms |
604 KB |
Output is correct |
| 7 |
Correct |
2 ms |
496 KB |
Output is correct |
| 8 |
Correct |
1 ms |
544 KB |
Output is correct |
| 9 |
Correct |
2 ms |
496 KB |
Output is correct |
| 10 |
Correct |
2 ms |
764 KB |
Output is correct |
| 11 |
Correct |
3 ms |
756 KB |
Output is correct |
| 12 |
Correct |
4 ms |
752 KB |
Output is correct |
| 13 |
Correct |
6 ms |
604 KB |
Output is correct |
| 14 |
Correct |
2 ms |
604 KB |
Output is correct |
| 15 |
Correct |
1 ms |
604 KB |
Output is correct |
| 16 |
Correct |
4 ms |
860 KB |
Output is correct |
| 17 |
Correct |
1 ms |
504 KB |
Output is correct |
| 18 |
Correct |
3 ms |
604 KB |
Output is correct |
| 19 |
Correct |
1 ms |
604 KB |
Output is correct |
| 20 |
Correct |
4 ms |
492 KB |
Output is correct |
