QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#525197#1817. AND PermutationRngBased#WA 1ms3884kbC++201.7kb2024-08-20 14:28:362024-08-20 14:28:36

Judging History

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

  • [2024-08-20 14:28:36]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3884kb
  • [2024-08-20 14:28:36]
  • 提交

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.