题意

个二元组 ,二元组可以翻转。现在要将这些二元组接成一个环。连接部分的漂亮度是 时漂亮度为 )。环的漂亮度为连接部分的最小漂亮度,现在要最大化漂亮度,并输出连接顺序。(第 个二元组的编号为
其中

分析

先考虑答案大于等于 时的性质:
也就是任意一个连接处, 的倍数。
因此答案具有单调性。
考虑怎么检验答案。 能作为连接处,意味着 在模 意义下相同,也就是
那么,能否连成一个环,其实等价于是否存在欧拉回路(这个可能需要思考一下)。判断欧拉回路存不存在很好判断。
然后找到答案之后再求一边欧拉回路就可以了。
复杂度

代码如下

#include <bits/stdc++.h>
using namespace std;

int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}

const int N = 2000005;
int n, A[N], B[N], ans[N], m, h[N], f[N], du[N], vis[N * 2], cnt = 1;

struct node{
    int a, b, x, y, n;
}d[N * 2];

void cr(int a, int b, int x, int y){
    d[++cnt].a = a; d[cnt].b = b; d[cnt].x = x; d[cnt].y = y; d[cnt].n = h[a]; h[a] = cnt;
}

int find(int x){
    return x == f[x]? x: f[x] = find(f[x]);
}

int chk(int x){
    int i, j, a, b, tot = 0;
    for(i = 0; i <= (1 << 20); i++) du[i] = 0, f[i] = i;
    for(i = 1; i <= n; i++){
        a = A[i] & x; b = B[i] & x;
        du[a]++; du[b]++;
        if(find(a) != find(b)) f[f[b]] = f[a];
    }
    for(i = 0; i <= (1 << 20); i++){
        if(!du[i]) continue;
        if(du[i] % 2) return 0;
        if(find(i) == i) tot++;
    }
    return tot == 1;
}

void dfs(int a, int id){
    for(int &i = h[a]; i; i = d[i].n){//此处不加引用会使复杂度高达 n^2,加了引用类似于网络流中的当前弧优化,也就是实时改变 h 指针 
        if(vis[i]) continue;
        vis[i] = vis[i ^ 1] = 1;
        int b = d[i].b;
        dfs(b, i);
    }
    ans[++m] = id;
}

void work(int x){
    int i, j, a, b;
    for(i = 1; i <= n; i++){
        a = A[i] & x; b = B[i] & x;
        cr(a, b, 2 * i - 1, 2 * i);
        cr(b, a, 2 * i, 2 * i - 1);
    }
    dfs(a, 1);
}

int main(){
    int i, j, k, a, b, l = 0, r = 20;
    n = read();
    for(i = 1; i <= n; i++) A[i] = read(), B[i] = read();
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(chk((1 << mid) - 1)) l = mid;
        else r = mid - 1;
    }
    printf("%d\n", l);
    work((1 << l) - 1);
    for(i = m - 1; i >= 1; i--){
        j = ans[i];
        printf("%d %d ", d[j].x, d[j].y);
    }
    return 0;
}