QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#27066#1817. AND PermutationHakujitsuML 3ms3720kbC++1.7kb2022-04-09 11:46:112022-04-29 05:11:46

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:11:46]
  • 评测
  • 测评结果:ML
  • 用时:3ms
  • 内存:3720kb
  • [2022-04-09 11:46:11]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 3720kb

input:

6
0
1
4
5
2
6

output:

5
6
2
0
4
1

result:

ok OK!

Test #2:

score: -100
Memory Limit Exceeded

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:


result: