QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#27313#1817. AND PermutationHakujitsuWA 8ms3952kbC++1.9kb2022-04-09 14:23:322022-04-29 05:38:28

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 05:38:28]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:3952kb
  • [2022-04-09 14:23:32]
  • 提交

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;
    }
    if(n & 1) {
        for (int i = 0; i < n; i += 1) {
            if(a[i] == 0) {
                match.back() = match[i];
                match[match[i]] = n - 1;
                match[i] = i;
                break;
            }
        }
    }


    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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3632kb

input:

6
0
1
4
5
2
6

output:

5
6
2
0
4
1

result:

ok OK!

Test #2:

score: 0
Accepted
time: 1ms
memory: 3608kb

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: 8ms
memory: 3952kb

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: 3708kb

input:

15
10
0
11
13
2
14
4
1
5
6
8
12
3
7
9

output:

5
7
4
2
13
1
11
14
10
9
3
0
8
0
6

result:

wrong answer Output value not an unused input value.