QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#525197 | #1817. AND Permutation | RngBased# | WA | 1ms | 3884kb | C++20 | 1.7kb | 2024-08-20 14:28:36 | 2024-08-20 14:28:36 |
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 x first
#define y second
#define all(x) x.begin(), x.end()
using namespace std;
int n, arr[300015];
set<pii> 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(pii(__builtin_popcountll(arr[i]), 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())->y);
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(pii(__builtin_popcountll(val), val));
if (res & (1LL << j))
s[j].erase(pii(__builtin_popcountll(res), res));
}
}
assert(zero <= 1);
for (int i = 1; i <= n; i++)
cout << ans[arr[i]] << "\n";
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3776kb
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: 3884kb
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:
196 309 257 0 53 82 0 206 170 54 212 290 51 120 0 145 142 416 168 166 67 337 114 269 257 192 0 323 386 0 192 306 0 43 0 258 304 47 0 0 416 27 129 140 273 39 259 65 0 228 174 257 257 192 15 268 81 290 184 188 386 226 208 138 259 273 178 386 257 0 0 23 164 134 0 273 296 0 202 0 0 148 336 321 392 0 257...
result:
wrong answer Output value not an unused input value.