NC19827. 排序
描述
输入描述
第一行一个整数2k（1≤ k≤ 10）。
第二行两个不同的整数a和b（0≤ a,b≤ 2k-1）。
第三行2k个整数，为一个0,1, ..., 2k-1的排列。
输出描述
如果无法将石板整理成升序，只需输出一行-1。
否则在第一行输出一个整数表示整理所使用的魔法的总数。
接下来每行一个魔法，如果使用交换魔法，则输出0；如果使用异或魔法，则输出1 x，其中x为你指定的数字；如果使用加魔法，则输出2 x，其中x为你制定的数字。
使用的魔法数量必须为0到32768之间的整数，且按顺序使用过所有魔法后，石板必须被整理成升序。
示例1
输入:
2 0 1 1 0
输出:
5 2 1 2 1 0 2 1 2 1
C++(g++ 7.5.0) 解法, 执行用时: 52ms, 内存消耗: 1500K, 提交时间: 2022-10-25 15:42:25
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ins insert
#define pb push_back
typedef long long LL;
typedef complex<double> Complex;
#define fi first
#define se second
#define ins insert
#define pb push_back
inline char g_c() {
const int maxn = 131072;
static char buf[maxn], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, maxn, stdin), p1 == p2) ? EOF : *p1++;
}
inline int g_i() {
int res(0);
char c = getchar();
while (c < '0') c = getchar();
while (c >= '0') {
res = res * 10 + (c - '0');
c = getchar();
}
return res;
}
inline int f_p(int x, int n, int mod) {
int res(1);
while (n) {
if (n & 1) {
res = res * (LL)x % mod;
}
x = x * (LL) x % mod;
n /= 2;
}
return res;
}
const int N = 1024;
const int LOG = 20;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<int> ans;
int o[N], posi[N];
int a, b, l;
int n;
void rf() {
for (int i(0); i < n; i++)
posi[o[i]] = i;
}
void doMagic() {
ans.push_back(0);
for (int i(0); i < n; i++) {
if (o[i] == a) o[i] = b;
else if (o[i] == b) o[i] = a;
}
rf();
}
void doAdd(int x) {
if (x == 0) return;
ans.push_back(x);
for (int i(0); i < n; i++)
o[i] = (o[i] + x) % n;
rf();
}
void doXor(int x) {
if (x == 0) return;
ans.push_back(-x);
for (int i(0); i < n; i++)
o[i] = (o[i] ^ x);
rf();
}
void calc(int a, int b, int & pa, int & pb) {
int delta = (b - a + n - l + n) % n;
pa = pb = 0;
for (int stp = n / 2; stp >= 2 * l; stp /= 2) {
if (delta >= stp) {
delta -= stp;
pb += stp / 2;
} else pa += stp / 2;
}
pa += n / 2;
pa += (a & (l - 1));
pb += (a & (l - 1));
}
void doSwap(int c, int d) {
if (c / l % 2 == d / l % 2) {
int p;
if (c / l % 2 == 0)
p = (c & (l - 1)) + l;
else p = (c & (l - 1));
doSwap(c, p);
doSwap(d, p);
doSwap(c, p);
} else {
int pa, pb;
calc(a, b, pa, pb);
int pc, pd;
calc(c, d, pc, pd);
doAdd((pc - c + n) % n);
doXor((pc ^ pa));
doAdd((a - pa + n) % n);
doMagic();
doAdd((pa - a + n) % n);
doXor((pc ^ pa));
doAdd((c - pc + n) % n);
}
}
struct Perm {
int a[N];
int n;
vector<int> vec;
bool operator < (const Perm & b) const {
for (int i(0); i < n; i++) if (a[i] != b.a[i]) return a[i] < b.a[i];
return false;
}
void print() const {
for (int i(0); i < n; i++) printf("%d%c", (int)a[i], i == n - 1 ? '\n' : ' ');
}
Perm inv() const {
Perm res;
for (int i(0); i < n; i++) res.a[a[i]] = i;
return res;
}
bool sorted() const {
for (int i(0); i + 1 < n; i++) if (a[i] > a[i + 1]) return false;
return true;
}
bool calc() {
//printf("calc:");
//for(int i(0); i < n; i++) printf(" %d", a[i]);
//printf("\n");
bool f[100005] = {};
for (int i(0); i < n; i++) f[i] = 1;
for (int i(0); i < n; i++) if (!f[i]) return false;
if (n == 1) return true;
Perm b, c;
for (int i(0); i < n / 2; i++) {
b.a[i] = a[i * 2] / 2;
c.a[i] = a[i * 2 + 1] / 2;
}
b.n = n / 2;
c.n = n / 2;
if (!b.calc() || !c.calc()) return false;
if (a[0] % 2) vec.push_back(n == 2 ? 1 : -1);
int tb = 0;
for (int i : b.vec) {
if (i > 0) {
vec.push_back(-1);
vec.push_back(1);
} else {
vec.push_back(i * 2);
tb ^= -i * 2;
}
}
if (tb) vec.push_back(-tb);
int tc = 0;
for (int i : c.vec) {
if (i > 0) {
vec.push_back(1);
vec.push_back(-1);
} else {
vec.push_back(i * 2);
tc ^= -i * 2;
}
}
if ((tc & (n / 2)) != (tb & (n / 2))) {
assert(false);
for (int i(0); i < n / 4; i++) {
vec.push_back(-1);
vec.push_back(1);
}
}
if (tb >= (n / 2)) tb -= n / 2;
if (tc >= (n / 2)) tc -= n / 2;
if (tb != tc) return false;
vector<int> tmp;
for (int i : vec) {
if (tmp.empty()) tmp.push_back(i);
else {
if ((i < 0) && (tmp.back() < 0)) {
tmp.back() = - ((-tmp.back()) ^ (-i));
if (tmp.back() == 0) tmp.pop_back();
} else {
tmp.push_back(i);
}
}
}
swap(tmp, vec);
return true;
}
};
int oo[N];
int main() {
n = g_i();
a = g_i();
b = g_i();
for (int i(0); i < n; i++) {
o[i] = g_i();
}
rf();
l = (a - b + n) % n;
l = l & -l;
if (l == 0) l = n;
if (l > 1) {
Perm a;
a.n = l;
for (int i(0); i < n; i++) a.a[i] = o[i] & (l - 1);
if (!a.calc()) {
printf("-1\n");
exit(0);
}
for (auto i = a.vec.begin(); i != a.vec.end(); i++) {
if (*i > 0) doAdd(*i);
else doXor(-*i);
}
}
for (int i(0); i < l; i++) {
vector<int> vec;
for (int j(i); j < n; j += l) {
vec.push_back(o[j]);
}
int c = 0, flag = 1;
sort(vec.begin(), vec.end());
for (int j(i); j < n; j += l) {
if (vec[c] != j) {
flag = 0;
break;
}
c++;
}
if (!flag) {
printf("-1\n");
exit(0);
}
for (int j(i); j < n; j += l) {
if (o[j] != j) {
doSwap(j, o[j]);
}
}
}
for (int i(0); i < n; i++)
assert(o[i] == i);
printf("%d\n", (int)ans.size());
for (int i : ans) {
if (i == 0) {
printf("0\n");
} else if (i < 0) {
printf("1 %d\n", -i);//xor
} else {
printf("2 %d\n", i);//+
}
}
}
C++(clang++ 11.0.1) 解法, 执行用时: 43ms, 内存消耗: 1544K, 提交时间: 2022-10-25 15:41:53
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ins insert
#define pb push_back
typedef long long LL;
typedef complex<double> Complex;
#define fi first
#define se second
#define ins insert
#define pb push_back
inline char g_c() {
const int maxn = 131072;
static char buf[maxn], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, maxn, stdin), p1 == p2) ? EOF : *p1++;
}
inline int g_i() {
int res(0);
char c = getchar();
while (c < '0') c = getchar();
while (c >= '0') {
res = res * 10 + (c - '0');
c = getchar();
}
return res;
}
inline int f_p(int x, int n, int mod) {
int res(1);
while (n) {
if (n & 1) {
res = res * (LL)x % mod;
}
x = x * (LL) x % mod;
n /= 2;
}
return res;
}
const int N = 1024;
const int LOG = 20;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<int> ans;
int o[N], posi[N];
int a, b, l;
int n;
void rf() {
for (int i(0); i < n; i++)
posi[o[i]] = i;
}
void doMagic() {
ans.push_back(0);
for (int i(0); i < n; i++) {
if (o[i] == a) o[i] = b;
else if (o[i] == b) o[i] = a;
}
rf();
}
void doAdd(int x) {
if (x == 0) return;
ans.push_back(x);
for (int i(0); i < n; i++)
o[i] = (o[i] + x) % n;
rf();
}
void doXor(int x) {
if (x == 0) return;
ans.push_back(-x);
for (int i(0); i < n; i++)
o[i] = (o[i] ^ x);
rf();
}
void calc(int a, int b, int & pa, int & pb) {
int delta = (b - a + n - l + n) % n;
pa = pb = 0;
for (int stp = n / 2; stp >= 2 * l; stp /= 2) {
if (delta >= stp) {
delta -= stp;
pb += stp / 2;
} else pa += stp / 2;
}
pa += n / 2;
pa += (a & (l - 1));
pb += (a & (l - 1));
}
void doSwap(int c, int d) {
if (c / l % 2 == d / l % 2) {
int p;
if (c / l % 2 == 0)
p = (c & (l - 1)) + l;
else p = (c & (l - 1));
doSwap(c, p);
doSwap(d, p);
doSwap(c, p);
} else {
int pa, pb;
calc(a, b, pa, pb);
int pc, pd;
calc(c, d, pc, pd);
doAdd((pc - c + n) % n);
doXor((pc ^ pa));
doAdd((a - pa + n) % n);
doMagic();
doAdd((pa - a + n) % n);
doXor((pc ^ pa));
doAdd((c - pc + n) % n);
}
}
struct Perm {
int a[N];
int n;
vector<int> vec;
bool operator < (const Perm & b) const {
for (int i(0); i < n; i++) if (a[i] != b.a[i]) return a[i] < b.a[i];
return false;
}
void print() const {
for (int i(0); i < n; i++) printf("%d%c", (int)a[i], i == n - 1 ? '\n' : ' ');
}
Perm inv() const {
Perm res;
for (int i(0); i < n; i++) res.a[a[i]] = i;
return res;
}
bool sorted() const {
for (int i(0); i + 1 < n; i++) if (a[i] > a[i + 1]) return false;
return true;
}
bool calc() {
//printf("calc:");
//for(int i(0); i < n; i++) printf(" %d", a[i]);
//printf("\n");
bool f[100005] = {};
for (int i(0); i < n; i++) f[i] = 1;
for (int i(0); i < n; i++) if (!f[i]) return false;
if (n == 1) return true;
Perm b, c;
for (int i(0); i < n / 2; i++) {
b.a[i] = a[i * 2] / 2;
c.a[i] = a[i * 2 + 1] / 2;
}
b.n = n / 2;
c.n = n / 2;
if (!b.calc() || !c.calc()) return false;
if (a[0] % 2) vec.push_back(n == 2 ? 1 : -1);
int tb = 0;
for (int i : b.vec) {
if (i > 0) {
vec.push_back(-1);
vec.push_back(1);
} else {
vec.push_back(i * 2);
tb ^= -i * 2;
}
}
if (tb) vec.push_back(-tb);
int tc = 0;
for (int i : c.vec) {
if (i > 0) {
vec.push_back(1);
vec.push_back(-1);
} else {
vec.push_back(i * 2);
tc ^= -i * 2;
}
}
if ((tc & (n / 2)) != (tb & (n / 2))) {
assert(false);
for (int i(0); i < n / 4; i++) {
vec.push_back(-1);
vec.push_back(1);
}
}
if (tb >= (n / 2)) tb -= n / 2;
if (tc >= (n / 2)) tc -= n / 2;
if (tb != tc) return false;
vector<int> tmp;
for (int i : vec) {
if (tmp.empty()) tmp.push_back(i);
else {
if ((i < 0) && (tmp.back() < 0)) {
tmp.back() = - ((-tmp.back()) ^ (-i));
if (tmp.back() == 0) tmp.pop_back();
} else {
tmp.push_back(i);
}
}
}
swap(tmp, vec);
return true;
}
};
int oo[N];
int main() {
n = g_i();
a = g_i();
b = g_i();
for (int i(0); i < n; i++) {
o[i] = g_i();
}
rf();
l = (a - b + n) % n;
l = l & -l;
if (l == 0) l = n;
if (l > 1) {
Perm a;
a.n = l;
for (int i(0); i < n; i++) a.a[i] = o[i] & (l - 1);
if (!a.calc()) {
printf("-1\n");
exit(0);
}
for (auto i = a.vec.begin(); i != a.vec.end(); i++) {
if (*i > 0) doAdd(*i);
else doXor(-*i);
}
}
for (int i(0); i < l; i++) {
vector<int> vec;
for (int j(i); j < n; j += l) {
vec.push_back(o[j]);
}
int c = 0, flag = 1;
sort(vec.begin(), vec.end());
for (int j(i); j < n; j += l) {
if (vec[c] != j) {
flag = 0;
break;
}
c++;
}
if (!flag) {
printf("-1\n");
exit(0);
}
for (int j(i); j < n; j += l) {
if (o[j] != j) {
doSwap(j, o[j]);
}
}
}
for (int i(0); i < n; i++)
assert(o[i] == i);
printf("%d\n", (int)ans.size());
for (int i : ans) {
if (i == 0) {
printf("0\n");
} else if (i < 0) {
printf("1 %d\n", -i);
} else {
printf("2 %d\n", i);
}
}
}