QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#27078 | #1817. AND Permutation | Hakujitsu | WA | 3ms | 3964kb | C++ | 1.7kb | 2022-04-09 11:54:19 | 2022-04-29 05:12:46 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr << endl;}
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T)
{
cerr << " " << H;
debug_out(T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
int n;
using ll = long long;
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n;
vector<ll> a(n);
map<ll, int> mp;
for (auto &x : a) {
cin >> x;
}
for (int i = 0; i < n; i += 1) {
mp[a[i]] = i;
}
vector<int> match(n);
for (int i = 0; i < n; i += 2) {
match[i] = i + 1;
match[i + 1] = i;
}
match.back() = 0;
for (int d = 62; d >= 0; d -= 1) {
function<void(int, vector<int> &) > dfs = [&](int id, vector<int> &lst) {
// vis[id] = vis[match[id]] = 1;
if(!(a[id] >> d & 1)) {
lst.emplace_back(id);
return;
}
int go = mp[a[id] - (1ll << d)];
lst.emplace_back(go);
lst.emplace_back(id);
dfs(match[go], lst);
};
for (int i = 0; i < n; i += 1) {
if(!(a[match[i]] >> d & 1) || !(a[i] >> d & 1)) {
continue;
}
vector<int> lst = {i};
dfs(match[i], lst);
for (int j = 0; j < lst.size(); j += 2) {
match[lst[j]] = lst[j + 1];
match[lst[j + 1]] = lst[j];
}
}
}
for (int i = 0; i < n; i += 1) {
cout << a[match[i]] << "\n";
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3536kb
input:
6 0 1 4 5 2 6
output:
5 6 2 0 4 1
result:
ok OK!
Test #2:
score: 0
Accepted
time: 3ms
memory: 3600kb
input:
272 315 138 126 6 394 297 44 273 84 200 9 197 396 133 16 46 65 87 86 336 316 174 140 162 250 306 52 188 57 36 63 192 320 388 10 156 15 208 38 32 31 228 30 305 234 384 220 142 72 27 337 110 94 317 304 242 398 209 5 323 29 284 301 309 244 230 261 61 254 266 194 296 275 313 80 206 214 88 308 18 288 106...
output:
68 309 384 232 5 150 211 102 42 54 38 314 51 122 238 337 286 392 168 142 3 81 339 88 261 141 74 259 70 323 192 63 55 27 308 290 80 303 9 90 288 26 160 78 277 126 35 336 311 388 46 145 416 66 134 13 33 270 394 36 194 226 210 138 266 281 250 130 0 244 29 151 236 198 15 48 41 162 10 108 31 148 280 260 ...
result:
ok OK!
Test #3:
score: 0
Accepted
time: 3ms
memory: 3964kb
input:
5134 36416 73248 85220 2072 16524 36385 101507 91137 17604 22 640 70530 66850 107792 81952 163 84260 46246 45090 101411 18824 66360 116881 400 50338 109824 17508 122881 98691 99843 36481 1696 102658 27008 2566 4 32900 103171 1153 104706 69923 82280 19616 66849 17540 36870 8352 117777 82156 6785 6780...
output:
82305 24706 4354 37892 68960 20614 24608 39810 67880 93569 36129 1068 51345 2148 44416 69184 1112 84224 69505 4236 33825 3201 13856 106017 69704 4265 75905 3712 3616 16780 69890 34880 19628 103458 5248 72995 15968 27792 68386 25617 34432 36480 66328 39554 105251 85280 117777 8352 44048 82976 17668 1...
result:
ok OK!
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3512kb
input:
15 10 0 11 13 2 14 4 1 5 6 8 12 3 7 9
output:
5 11 0 2 13 1 10 14 10 9 7 3 12 8 6
result:
wrong answer Output value not an unused input value.