QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55693#1968. Science FictionAs3b_team_f_masr#WA 2ms3876kbC++1.7kb2022-10-14 22:34:192022-10-14 22:34:20

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-14 22:34:20]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3876kb
  • [2022-10-14 22:34:19]
  • 提交

answer

#include <bits/stdc++.h>

typedef long double ld;
typedef long long ll;
using namespace std;
int di[] = {1, 0, -1, -1, 0, 1, -1, 1};
int dj[] = {1, 1, 0, -1, -1, 0, 1, -1};
const ll oo = 1e18, MOD = 998244353;
const int N = 1005, M = 105;
const ld PI = acos(-1.0), EPS = 1e-9;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


int n;
bool yes[N][N];
pair<int, int> a[N];
vector<pair<int, int>> ans;


//#define endl '\n'
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    //freopen("farm.in", "r", stdin);
    //memset(dp, -1, sizeof dp);
    cin >> n;
    int m = 1 << n;
    for (int i = 0; i < m; i++) cin >> a[i].first, a[i].second = i;
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            int num = 0;
            for (int k = 0; k < n; k++) {
                int num1 = min(1, i & (1 << k));
                int num2 = min(1, j & (1 << k));
                if (num1 ^ num2) num++;
            }
            if (num == 1) yes[i][j] = yes[j][i] = 1;
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = i + 1; j < m; j++) {
            if (a[i].first > a[j].first && yes[a[i].second][a[j].second] == 1) {
                int tmp = a[i].first;
                a[i].first = a[j].first;
                a[j].first = tmp;
                ans.push_back({a[i].second, a[j].second});
            }
        }
    }
    cout << ans.size() << '\n';
    for (auto x:ans) cout << x.first << " " << x.second << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3756kb

input:

2
3 2 10 4

output:

2
0 1
2 3

result:

ok nice! 2 moves

Test #2:

score: 0
Accepted
time: 2ms
memory: 3592kb

input:

1
10 100

output:

0

result:

ok nice! 0 moves

Test #3:

score: 0
Accepted
time: 2ms
memory: 3472kb

input:

1
824838 992401

output:

0

result:

ok nice! 0 moves

Test #4:

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

input:

2
208395 17211 250690 874014

output:

1
0 1

result:

ok nice! 1 moves

Test #5:

score: -100
Wrong Answer
time: 2ms
memory: 3876kb

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:

297
0 1
0 8
1 3
1 9
1 17
1 65
2 6
2 10
3 7
3 11
4 12
5 13
5 69
6 14
6 22
6 38
6 134
7 15
8 9
8 24
9 25
9 41
9 73
9 137
10 26
10 138
11 43
12 28
12 44
13 29
13 77
14 30
15 31
16 17
16 144
17 19
17 49
18 19
18 26
18 50
19 23
20 21
20 52
20 148
21 23
21 29
21 85
21 149
22 23
22 54
23 55
23 87
24 56
24 ...

result:

wrong answer array is not sorted