QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#567097#1817. AND PermutationBakry#TL 0ms0kbC++141.9kb2024-09-16 06:57:212024-09-16 06:57:21

Judging History

你现在查看的是最新测评结果

  • [2024-09-16 06:57:21]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-09-16 06:57:21]
  • 提交

answer

#include <iostream>
#include <vector> 
#include <unordered_map>
#include <set>
using namespace std;
#define int long long
std::pair<std::vector<int>, std::vector<int>>  solve(vector<int>& arr, int x) {
    if (x < 0) {
        return { vector<int>(arr.size(), 0), vector<int>(arr.size(), 0) };
    }
    // find the values which have bit x set

    vector<int> A, B;
    unordered_map<int, int> posB;
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] & (1 << x)) {
            A.push_back(arr[i] ^ (1 << x));
        }
        else {
            B.push_back(arr[i]);
            posB[arr[i] & ((1 << x) - 1)] = i;
        }
    }
    // return { {}, {} };
    // set<int> all;
    auto [A1, A2] = solve(A, x - 1);
    auto [B1, B2] = solve(B, x - 1);
    set<int> all;
    for (auto t : A1) {
        // all[t & ((1 << x) - 1)] = 0;
        all.insert(t);
    }

    // for (auto& t : A1) {
    //     t ^= (1 << x);
    // }
    for (auto& t : B1) {
        if (all.count(t)) {
            t ^= (1 << x);
        }
    }
    // now for every B1 
    vector<int> res1(A1), res2(A2);
    for (int& t : res2)
        t ^= (1 << x);

    for (int i = 0; i < B1.size(); i++) {
        res1.push_back(B1[i]);
        res2.push_back(B2[i]);
    }

    return { res1, res2 };
}

main() {
    int n;
    cin >> n;

    vector<int> arr;
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        arr.push_back(x);
        mp[x] = i;

        // sort(arr.bsegin(), arr.end());
    }
    auto [A, B] = solve(arr, 59);
    // return 0;
    vector<int> E(n);
    // cout << A.size() << ' ' << B.size() << ' ';
    for (int i = 0; i < arr.size(); i++) {

        E[mp[A[i]]] = B[i];
        // cout << mp[arr[i]];
    }
    for (int i = 0; i < n; i++) {
        cout << E[mp[arr[i]]] << '\n';
    }
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

6
0
1
4
5
2
6

output:


result: