QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#525193 | #1817. AND Permutation | RngBased# | WA | 1ms | 3596kb | C++20 | 1.6kb | 2024-08-20 14:23:52 | 2024-08-20 14:23:53 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
int n, arr[300015];
set<int> s[65];
map<int, int> ans;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++){
cin >> arr[i];
if (n % 2 == 1 && arr[i] == 0)
continue;
for (int j = 0; j < 60; j++){
if (arr[i] & (1LL << j))
s[j].insert(arr[i]);
}
}
int zero = 0;
for (int _ = 0; _ < n / 2; _++){
vector<int> ori;
for (int j = 0; j < 60; j++)
if (!s[j].empty())
ori.emplace_back(*(--s[j].end()));
int mx = 0, val = 0, test = 0, res = 0;
for (auto i : ori){
if (__builtin_popcountll(i) > mx)
mx = __builtin_popcountll(i), val = i;
}
test = ((1LL << 60) - 1) - val;
mx = 0;
for (int i : ori){
int tmp = (test & i);
if (__builtin_popcountll(tmp) > mx)
mx = __builtin_popcountll(tmp), res = tmp;
}
ans[val] = res;
ans[res] = val;
zero += (res == 0);
for (int j = 0; j < 60; j++){
if (val & (1LL << j))
s[j].erase(val);
if (res & (1LL << j))
s[j].erase(res);
}
}
assert(zero <= 1);
for (int i = 1; i <= n; i++)
cout << ans[arr[i]] << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
input:
6 0 1 4 5 2 6
output:
4 6 0 2 5 1
result:
ok OK!
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3552kb
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:
132 68 0 0 65 130 0 130 0 0 0 34 82 66 0 0 390 0 0 160 1 80 0 337 5 132 0 0 0 202 0 0 190 80 0 0 0 0 0 0 0 1 0 130 17 0 1 80 134 0 162 0 0 130 1 1 81 34 250 164 0 160 130 130 1 17 130 0 1 132 1 80 132 130 142 48 40 0 136 0 222 0 72 68 0 0 1 0 0 0 132 193 2 80 66 160 288 0 40 0 0 320 68 0 261 133 0 1...
result:
wrong answer Output value not an unused input value.