QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#223587#1968. Science FictionBUET_Twilight#WA 0ms3908kbC++232.0kb2023-10-22 13:40:392023-10-22 13:40:40

Judging History

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

  • [2023-10-22 13:40:40]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3908kb
  • [2023-10-22 13:40:39]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0) 
#define setbit0(n, i) ((n) & (~(1LL << (i)))) 
#define setbit1(n, i) ((n) | (1LL << (i))) 
#define togglebit(n, i) ((n) ^ (1LL << (i))) 
#define lastone(n) ((n) & (-(n))) 
char gap = 32;
#define int long long
#define ll long long 
#define lll __int128_t
#define pb push_back
#define pii pair<int,int>
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll hashPrime = 1610612741;

const int N = 1120;
int ara[N];
pii target[N];
int cur[N];
void solve(){
    int n;
    cin >> n;
    n = 1<<n;
    for (int i=0; i<n; i++) cin >> ara[i];
    for(int i=0;i<n;i++)    target[i] = {ara[i], i};
    sort(target, target+n);
    for(int i=0;i<n;i++)    cur[i] = target[i].second;
    vector<pii> res;
    for (int i=n-1; i>=0; i--) {
        //if (ara[i] == target[i].first) continue;
        int pos = cur[i];
        int mul = 1;
        for(int b=0;b<10;b++){
            if( mul & pos ){
                res.pb({pos, pos^mul});
                //cout<<pos<<" "<<(pos^mul)<<endl;
                swap(cur[pos], cur[pos^mul]);
                
                pos ^= mul;
            }
            mul = mul<<1;
        }
        pos = 0;
        mul = 1;
        for(int b=0;b<10;b++){
            if( mul & i ){
                res.pb({pos, pos^mul});
               // cout<<pos<<" "<<(pos^mul)<<endl;
                swap(cur[pos], cur[pos^mul]);
                pos ^= mul;
            }
            mul <<= 1;
        }


    }
    cout<<res.size()<<endl;
    for(auto p: res) cout << p.first << " " << p.second << endl;

}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
     solve();
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3900kb

input:

2
3 2 10 4

output:

6
2 0
0 1
1 3
1 0
0 2
0 1

result:

ok nice! 6 moves

Test #2:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

1
10 100

output:

2
1 0
0 1

result:

ok nice! 2 moves

Test #3:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

1
824838 992401

output:

2
1 0
0 1

result:

ok nice! 2 moves

Test #4:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

2
208395 17211 250690 874014

output:

7
3 2
2 0
0 1
1 3
1 0
0 2
0 1

result:

ok nice! 7 moves

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3740kb

input:

8
991318 655714 983340 496226 752852 888298 572661 729100 426124 437775 8096 28612 303846 295897 970760 179029 702449 407420 945406 352294 960516 484993 724888 495235 156841 451864 95506 869159 61631 296168 279240 260130 901551 726353 298872 221580 982372 394731 720187 656498 595457 381795 759187 36...

output:

1994
0 1
1 3
3 7
7 15
15 31
31 63
63 127
127 255
164 160
160 128
128 0
0 2
2 6
6 14
14 30
30 62
62 126
126 254
224 192
192 128
128 0
0 1
1 5
5 13
13 29
29 61
61 125
125 253
2 0
0 4
4 12
12 28
28 60
60 124
124 252
36 32
32 0
0 1
1 3
3 11
11 27
27 59
59 123
123 251
169 168
168 160
160 128
128 0
0 2
2 ...

result:

wrong answer array is not sorted