QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#567097 | #1817. AND Permutation | Bakry# | TL | 0ms | 0kb | C++14 | 1.9kb | 2024-09-16 06:57:21 | 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