#include "shuffle.h"
#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#ifdef ONLINE_JUDGE
#define cout cerr
#endif
using namespace std;
using v2d = vector<vector<int>>;
using v1d = vector<int>;
int N, B, K;
v2d self_shuffle(v2d query){
for(auto& q : query){
for(auto& i : q){
i = (i % N + N) % N + 1;
}
}
return shuffle(query);
}
void norm(v2d& v2){
for(auto& v : v2){
sort(v.begin(), v.end());
}
sort(v2.begin(), v2.end());
}
const int MAXN = 1e3 + 11;
vector<int> G[MAXN];
deque<int> val;
bool vis[MAXN];
int c[MAXN], sp[MAXN];
void dfs(int v, int pa = -1){
vis[v] = true; val.push_back(v);
for(auto i : G[v]){
if(i != pa && !vis[i]) c[i] = c[v] ^ 1, dfs(i, v);
}
}
bool is_adj(int u, int v){
for(auto i : G[u]){
if(i == v) return true;
}
return false;
}
int adj_exc(int u, int v){
for(auto i : G[u]){
if(i != v) return i;
}
return -1;
}
ostream& operator<< (ostream& out, v2d v){
out << "Vec2d: " << endl;
for(auto i : v){
for(auto ii : i){
out << ii << ' ';
}
out << endl;
}
return out << endl;
}
ostream& operator<< (ostream& out, v1d v){
out << "Vec1d: " << endl;
for(auto i : v){
out << i << ' ';
}
return out << endl;
}
void find_diff(vector<int> v1, vector<int> v2, vector<int>& d1, vector<int> d2){
sort(all(v1)); sort(all(v2)); int l = 0, r = 0;
while(l != v1.size() && r != v2.size()){
if(v1[l] < v2[r]) d1.pb(v1[l]), l++;
else if(v1[l] > v2[r]) d2.pb(v2[r]), r++;
else l++, r++;
}
while(l != v1.size()) d1.pb(v1[l]), l++;
while(r != v2.size()) d2.pb(v2[r]), r++;
}
int pw(int a, int b){
int ret = 1;
for(int j = 0; j < b; j++){
ret *= a;
}
return ret;
}
struct DSU{
int dsu[MAXN], sz[MAXN];
void init(int n){
for(int i = 0; i <= n; i++){
dsu[i] = i, sz[i] = 1;
}
}
bool irt(int x){
return x == dsu[x];
}
int f(int x){
return x == dsu[x] ? x : dsu[x] = f(dsu[x]);
}
int s(int x){
return sz[f(x)];
}
void g(int x, int y){
x = f(x), y = f(y);
if(x != y){
dsu[x] = y; sz[y] += x;
}
}
} dsu;
vector<int> solve(int N, int B, int K, int Q, int ST) {
::N = N, ::B = B, ::K = K;
vector<int> ans(N);
if(K == 2){
v2d query, res;
for(int i = 0; i < B; i++){
query.push_back({i * 2, i * 2 + 1});
}
res = self_shuffle(query);
for(auto p : res){
G[p[0]].push_back(p[1]);
G[p[1]].push_back(p[0]);
}
query.clear();
for(int i = 0; i < B; i++){
query.push_back({i * 2, i * 2 - 1});
}
res = self_shuffle(query);
for(auto p : res){
G[p[0]].push_back(p[1]);
G[p[1]].push_back(p[0]);
}
dfs(1);
query.clear();
query.push_back({0, 2});
query.push_back({1, 3});
for(int i = 2; i < B; i++){
query.push_back({i * 2, i * 2 + 1});
}
v2d v1 = self_shuffle(query);
query.clear();
query.push_back({0, 2});
query.push_back({3, 5});
query.push_back({1, 4});
for(int i = 3; i < B; i++){
query.push_back({i * 2, i * 2 + 1});
}
v2d v2 = self_shuffle(query);
norm(v1), norm(v2);
v2d s1, s2;
for(int i = 0; i < B; i++){
if(c[v1[i][0]] == c[v1[i][1]]) s1.push_back(v1[i]);
if(c[v2[i][0]] == c[v2[i][1]]) s2.push_back(v2[i]);
}
v1d a02;
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
if(s1[i] == s2[j]){
a02 = s1[i];
if(s1[!i][0] == s2[!j][0] || s1[!i][1] == s2[!j][0]) ans[3] = s2[!j][0];
else ans[3] = s2[!j][1];
}
}
}
if(is_adj(a02[0], ans[3])) ans[2] = a02[0], ans[0] = a02[1];
else ans[2] = a02[1], ans[0] = a02[0];
ans[1] = adj_exc(ans[2], ans[3]);
for(int i = 4; i < N; i++){
ans[i] = adj_exc(ans[i - 1], ans[i - 2]);
}
return ans;
}
if(B == 2){
v2d query, res;
v2d r1, r2, r3;
{
v1d v1, v2;
for(int i = 0; i < K; i++){
v1.push_back(i);
v2.push_back(i + K);
}
query = {v1, v2};
r1 = self_shuffle(query);
}
{
v1d v1, v2;
v1.push_back(0); v2.push_back(K);
for(int i = 1; i < K; i++){
v1.push_back(i + K);
v2.push_back(i);
}
query = {v1, v2};
r2 = self_shuffle(query);
}
{
v1d v1, v2;
v1.push_back(0); v1.push_back(K);
for(int i = 1; i < K - 1; i++){
v1.push_back(i);
}
v2.push_back(K - 1);
for(int i = 1; i < K; i++){
v2.push_back(i + K);
}
query = {v1, v2};
r3 = self_shuffle(query);
}
for(int i = 0; i < B; i++){
for(int j = 0; j < K; j++){
c[r1[i][j]] = i;
}
}
v1d a03;
for(int i = 0; i < B; i++){
int cnt[2] = {0, 0};
for(int j = 0; j < K; j++){
cnt[c[r2[i][j]]]++;
}
int eq1 = cnt[0] == 1 ? 0 : 1;
for(int j = 0; j < K; j++){
if(c[r2[i][j]] == eq1){
a03.push_back(r2[i][j]);
}
}
}
for(int i = 0; i < B; i++){
bool ex = false, colour = false;
for(int j = 0; j < K; j++){
if(r3[i][j] == a03[0] || r3[i][j] == a03[1]) ex = true;
else colour = c[r3[i][j]];
}
if(ex){
if(colour == c[a03[0]]) ans[0] = a03[0], ans[K] = a03[1];
else ans[0] = a03[1], ans[K] = a03[0];
}
}
v1d id(N + 1);
for(int b = 0; b < 9; b++){
v1d v[2]; v[0].pb(0); v[1].pb(K);
for(int j = 1; j < K; j++){
bool ok = j & (1 << b);
v[0].push_back(j + ok * K);
v[1].push_back(j + (!ok) * K);
}
v2d query = {v[0], v[1]};
v2d res = self_shuffle(query);
bool in_0 = false; for(auto i : res[0]) if(i == ans[0]) in_0 = true;
if(!in_0) swap(res[0], res[1]);
for(auto i : res[1]) id[i] |= (1 << b);
}
for(int i = 1; i <= N; i++){
if(c[i] == c[ans[0]]){
ans[id[i]] = i;
}else{
ans[K + (id[i] ^ 511)] = i;
}
}
return ans;
}
v2d r1, r2, r3, r4;
{
v2d query;
for(int i = 0; i < B; i++){
v1d v;
for(int j = 0; j < K; j++){
v.pb(i * K + j);
}
query.pb(v);
}
r1 = self_shuffle(query);
for(int i = 0; i < B; i++){
for(int j = 0; j < K; j++){
c[r1[i][j]] = i;
}
}
}
{
v2d query;
for(int i = 0; i < B; i++){
v1d v;
v.push_back((i + 1) % B * K);
for(int j = 1; j < K; j++){
v.pb(i * K + j);
}
query.pb(v);
}
r2 = self_shuffle(query);
}
{
v2d query;
{
v1d v;
v.pb(0); v.pb(K);
for(int i = 1; i < K - 1; i++){
v.pb(i);
}
query.pb(v);
v.clear();
v.pb(K - 1);
for(int i = K + 1; i < K * 2; i++){
v.pb(i);
}
query.pb(v);
}
for(int i = 2; i < B; i++){
v1d v;
for(int j = 0; j < K; j++){
v.pb(i * K + j);
}
query.pb(v);
}
r3 = self_shuffle(query);
}
norm(r1), norm(r2), norm(r3);
map<pair<int, int>, int> M;
for(int i = 0; i < B; i++){
for(int j = 0; j < K; j++){
for(int k = j + 1; k < K; k++){
int u = r1[i][j], v = r1[i][k];
if(u > v) swap(u, v);
M[{u, v}]++;
}
}
for(int j = 0; j < K; j++){
for(int k = j + 1; k < K; k++){
int u = r2[i][j], v = r2[i][k];
if(u > v) swap(u, v);
M[{u, v}]++;
}
}
}
dsu.init(N);
for(auto i : M){
if(i.se == 2){
dsu.g(i.fi.fi, i.fi.se);
}
}
for(auto i : M){
if(i.se == 1){
if(dsu.irt(i.fi.fi) && dsu.irt(i.fi.se))
G[i.fi.fi].pb(i.fi.se),
G[i.fi.se].pb(i.fi.fi);
}
}
v1d sp1, sp2;
for(int i = 1; i <= N; i++){
if(dsu.f(i) == i && dsu.s(i) == 1) sp1.push_back(i), sp[i] = true;
if(dsu.f(i) == i && dsu.s(i) == K - 1) sp2.push_back(i), sp[i] = false;
}
for(int i = 0; i < B; i++){
int cnt = 0, colour = 0;
for(int j = 0; j < K; j++){
if(sp[r3[i][j]]) cnt++;
else colour = c[r3[i][j]];
}
if(cnt == 2){
for(int j = 0; j < K; j++){
if(sp[r3[i][j]]){
if(c[r3[i][j]] == colour) ans[0] = r3[i][j];
else ans[K] = r3[i][j];
}
}
}
}
v1d path;
path.pb(ans[0]);
path.pb(0);
path.pb(ans[K]);
for(auto i : G[ans[K]]){
for(auto j : G[i]){
if(j == ans[0]){
path[1] = i;
}
}
}
for(int i = 3; i < B * 2; i++){
path.pb(adj_exc(path[path.size() - 1], path[path.size() - 2]));
}
for(int i = 1; i <= N; i++){
for(int j = 0; j < B; j++){
if(dsu.f(i) == dsu.f(path[j * 2]) || dsu.f(i) == dsu.f(path[j * 2 + 1])){
c[i] = j;
}
}
}
for(int i = 2; i < B; i++){
ans[i * K] = path[i * 2];
}
v1d id(N + 1);
int b = 0;
for(; pw(B, b + 1) < N; b++){
v1d v[B];
for(int i = 0; i < B; i++){
v[i].pb(K * i);
}
for(int j = 1; j < K; j++){
int ok = j / pw(B, b) % B;
for(int k = 0; k < B; k++){
v[k].pb(j + ((k - ok + B) % B) * K);
}
}
v2d query;
for(int i = 0; i < B; i++){
query.pb(v[i]);
}
v2d res = self_shuffle(query);
v2d nres;
for(int k = 0; k < B; k++){
int to_swap = k;
for(int i = 0; i < B; i++){
for(auto j : res[i]){
if(j == ans[k * K]) to_swap = i;
}
}
nres.pb(res[to_swap]);
}
for(int i = 0; i < B; i++){
for(auto j : nres[i]){
id[j] += (i + B - c[j]) % B * pw(B, b);
}
}
}
for(int i = 1; i <= N; i++){
ans[K * c[i] + id[i]] = i;
}
return ans;
}
Compilation message
shuffle.cpp: In function 'void find_diff(std::vector<int>, std::vector<int>, std::vector<int>&, std::vector<int>)':
shuffle.cpp:79:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | while(l != v1.size() && r != v2.size()){
| ~~^~~~~~~~~~~~
shuffle.cpp:79:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | while(l != v1.size() && r != v2.size()){
| ~~^~~~~~~~~~~~
shuffle.cpp:84:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | while(l != v1.size()) d1.pb(v1[l]), l++;
| ~~^~~~~~~~~~~~
shuffle.cpp:85:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | while(r != v2.size()) d2.pb(v2[r]), r++;
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
224 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
10752 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
11 ms |
2260 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
2 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
432 KB |
Output is correct |
| 2 |
Correct |
2 ms |
596 KB |
Output is correct |
| 3 |
Correct |
13 ms |
2900 KB |
Output is correct |
| 4 |
Correct |
71 ms |
10800 KB |
Output is correct |
| 5 |
Correct |
3 ms |
596 KB |
Output is correct |
| 6 |
Correct |
72 ms |
10804 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1108 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1236 KB |
Output is correct |
| 9 |
Correct |
4 ms |
724 KB |
Output is correct |
| 10 |
Correct |
2 ms |
468 KB |
Output is correct |
| 11 |
Correct |
4 ms |
596 KB |
Output is correct |
| 12 |
Correct |
69 ms |
10768 KB |
Output is correct |
| 13 |
Correct |
4 ms |
596 KB |
Output is correct |
| 14 |
Correct |
5 ms |
1108 KB |
Output is correct |
| 15 |
Correct |
7 ms |
1752 KB |
Output is correct |
| 16 |
Correct |
67 ms |
10772 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
50 ms |
8392 KB |
Output is correct |
| 19 |
Correct |
7 ms |
1672 KB |
Output is correct |
| 20 |
Correct |
3 ms |
596 KB |
Output is correct |
