【題解】Codeforces 1631C. Johnny and Megan’s Necklace

【題目敘述】http://codeforces.com/contest/1361/problem/C

#include <iostream>
#include <vector>
using namespace std;
 
int n, a[500005], b[500005], vis[1000005];
vector <pair<int, pair<int, int> > > v[1048576];
vector <int> ans;
 
void dfs(int x){
    while (v[x].size()){
        auto i = v[x].back();
        v[x].pop_back();
        if (vis[i.second.first]) continue;
        else {
            vis[i.second.first] = 1;
            vis[i.second.second] = 1;
            dfs(i.first);
            ans.push_back(i.second.second);
            ans.push_back(i.second.first);
        }
    }
}
 
bool solve(int x){
    for (int i = 1; i <= n*2; i++){
        vis[i] = 0;
    }
    ans.clear();
    for (int i = 0; i < (1<<x); i++){
        v[i].clear();
    }
    for (int i = 0; i < n; i++){
        int y = (a[i]&((1<<x)-1)), z = (b[i]&((1<<x)-1));
        v[y].push_back({z, {i*2+1, i*2+2}});
        v[z].push_back({y, {i*2+2, i*2+1}});
    }
    for (int i = 0; i < (1<<x); i++){
        if (v[i].size() % 2 == 1) return false;
    }
    for (int i = 0; i < (1<<x); i++){
        if (v[i].size()){
            dfs(i);
            break;
        }
    }
    if (ans.size() == n*2) return true;
    else return false;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i] >> b[i];
    }
    for (int i = 20; i >= 0; i--){
        if (solve(i)){
            cout << i << "\n";
            break;
        }
    }
    for (int i:ans){
        cout << i << " ";
    }
}
分享本文 Share with friends