解題區/解題區 - Zerojudge

b278. 说话不算话的区间求和

Problem

一个长度为n的数组a[1..n]，初始值为0,。要求你维护三种操作：

1 x v ：把数组的第x个元素改为v；(1≤x≤n,1≤v≤100,000,000)

2 x y ：询问数组元素a[x],a[x+1],…,a[y]之和；(1≤x≤y≤n)

0 k ：撤销最近的k次操作(注意，撤销操作本身也是操作，询问也算一次操作)。(1≤k≤当前操作次数)

Sample Input

1
2
3
4
5
6
2 5
1 1 1
1 2 2
2 1 2
0 2
2 1 2

Sample Output

1
2
3
1

Solution

現在學到了一種可持久化的數據精神，有一種為函數式線段樹，最簡單理解的就是採用修改不改值，而是增加新的節點，而每一次修改最多增加 O(n log n) (延著線段樹走訪路徑增加節點)

也就是說，每一次修改會根據前一次的 root 增加一個新的 root’，這是一個相當重要的一環，每一次修改會產生新的一棵線段樹，而這個新線段樹大部分節點會使用前一個線段樹的節點，因此只要針對走訪不影響的情況下，我們仍然會經過舊有的節點。

這一題最麻煩的是對於版本回溯，對於撤銷操作而言，撤銷操作可以撤銷 “撤銷操作”，因此會不斷地展開原本被撤銷的相關操作，然後又將部分操作撤銷 … 反反覆覆，後來發現只要根據當前的版本號減去要撤銷操作的總數即可返回，因此必須記錄每一次操作的線段樹結果。

套用函數式線段樹就相當簡單了！

感謝 liouzhou_101 的題意指導

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
#define MAXBUF 8388608
struct Node {
    int lson, rson;
    long long sum;
} node[MAXBUF + 50];
int nodesize = 0;
int root[524288];
int build(int l, int r) {
    if (l > r)  return 0;
    int k = nodesize++;
    node[k].sum = 0;
    node[k].lson = node[k].rson = 0;
    if (l == r) return k;
    int m = (l + r)/2;
    node[k].lson = build(l, m);
    node[k].rson = build(m+1, r);
    return k;
}
int change(int p, int l, int r, int x, int val) {
    int k = nodesize++;
    node[k] = node[p];
    if (l == r) {
        node[k].sum = val;
        return k;
    }
    int m = (l + r)/2;
    if (x <= m)
        node[k].lson = change(node[p].lson, l, m, x, val);
    else
        node[k].rson = change(node[p].rson, m+1, r, x, val);
    node[k].sum = node[node[k].lson].sum + node[node[k].rson].sum;
    return k;
}
long long query(int k, int l, int r, int x, int y) {
    if (x <= l && r <= y)
        return node[k].sum;
    int m = (l + r)/2;
    long long sum = 0;
    if (x <= m) {
        sum += query(node[k].lson, l, m, x, y);
    }
    if (y > m) {
        sum += query(node[k].rson, m+1, r, x, y);
    }
    return sum;
}
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        
        root[0] = build(1, n);
        
        int pre_ver = 0, cmd, x = 0, y = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d %d", &cmd, &x);
            if (cmd == 0) {
                y = 0;
                root[i] = root[i - x - 1];
                pre_ver = i;
            } else if (cmd == 1) {
                scanf("%d", &y);
                root[i] = change(root[pre_ver], 1, n, x, y);
                pre_ver = i;
            } else if (cmd == 2){
                scanf("%d", &y);
//                printf("query root = %d\n", root[pre_ver]);
                printf("%lld\n", query(root[pre_ver], 1, n, x, y));
                root[i] = root[pre_ver];
                pre_ver = i;
            }
            if (nodesize > MAXBUF) {
                return 0;
            }
        }
    }
    return 0;
}
/*
 2 5
 1 1 1
 1 2 2
 2 1 2
 0 2
 2 1 2
 */
Read More +
解題區/解題區 - Zerojudge

a331. K-th Number

Problem

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array a[1…n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: “What would be the k-th number in a[i…j] segment, if this segment was sorted?”
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2…5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

Sample Input

1
2
3
4
5
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

Sample Output

1
2
3
5
6
3

Solution

之前使用過塊狀鏈表、歸併樹來完成這一題，其中速度快 歸併樹 > 函數式線段樹 > 塊狀鏈表，空間消耗大小 函數式線段樹 > 歸併樹 > 塊狀鏈表。

現在學到了一種可持久化的數據精神，有一種為函數式線段樹，最簡單理解的就是採用修改不改值，而是增加新的節點，而每一次修改最多增加 O(n log n) (延著線段樹走訪路徑增加節點)

也就是說，每一次修改會根據前一次的 root 增加一個新的 root’，這是一個相當重要的一環，每一次修改會產生新的一棵線段樹，而這個新線段樹大部分節點會使用前一個線段樹的節點，因此只要針對走訪不影響的情況下，我們仍然會經過舊有的節點。

為了找到區間 K 大，使用函數式線段樹有點類似於掃描線算法，對於某個時間點依序將數字放進去，然後對於區間查詢 K 大的時候，相當於對某個時間點之間作減法運算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
struct Node {
    int l, r, lson, rson;
    int sum;
} node[2097152];
int nodesize = 0;
int A[131072], B[131072], root[131072];
int build(int l, int r) {
    if (l > r)  return 0;
    int k = nodesize++;
    node[k].l = l, node[k].r = r, node[k].sum = 0;
    node[k].lson = node[k].rson = 0;
    if (l == r) return k;
    int m = (l + r)/2;
    node[k].lson = build(l, m);
    node[k].rson = build(m+1, r);
    return k;
}
int change(int p, int x, int val) {
    int k = nodesize++;
    node[k] = node[p];
    node[k].sum += val;
    if (node[k].l == node[k].r) return k;
    int m = (node[k].l + node[k].r)/2;
    if (x <= m)
        node[k].lson = change(node[p].lson, x, val);
    else
        node[k].rson = change(node[p].rson, x, val);
    return k;
}
int query(int tp, int tq, int k) {
    if (node[tp].l == node[tp].r)
        return node[tp].l;
    int t = node[node[tp].lson].sum - node[node[tq].lson].sum;
    if (k <= t)
        return query(node[tp].lson, node[tq].lson, k);
    else
        return query(node[tp].rson, node[tq].rson, k - t);
}
int main() {
    int n, m, x, y, k;
    while (scanf("%d %d", &n, &m) == 2) {
        map<int, int> R;
        for (int i = 1; i <= n; i++)
            scanf("%d", &A[i]), R[A[i]] = 0;
        
        int size = 0;
        for (map<int, int>::iterator it = R.begin(); it != R.end(); it++) {
            it->second = ++size;
            B[it->second] = it->first;        
        }
        
        nodesize = 1;
        root[0] = build(1, size);
        
        for (int i = 1; i <= n; i++) {
            A[i] = R[A[i]];
            root[i] = change(root[i-1], A[i], 1);
        }
        
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d", &x, &y, &k);
            printf("%d\n", B[query(root[y], root[x-1], k)]);
        }
    }
    return 0;
}
/*
 7 3
 1 5 2 6 3 7 4
 2 5 3
 4 4 1
 1 7 3
 */
Read More +
解題區/解題區 - Zerojudge

a007. 判斷質數

題目

內容：

請判斷某數是否為質數

輸入說明：

輸入有多組測試資料（以EOF結尾），每組測試資料占一行，只包含一個整數x, 2 ≦ x ≦ 2147483647。

輸出說明：

對於每組測試資料，如果輸入的x為質數，則輸出一行「質數」（不含引號）；否則輸出一行「非質數」（不含引號）。詳見範例測試資料。

範例輸入：

13
14

範例輸出：

質數
非質數

解法

  • 作法：
    Miller-Rabin Algorithm
a007.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**********************************************************************************/
/*  Problem: a007 "判斷質數"                                                  */
/*  Language: CPP (715 Bytes)                                                     */
/*  Result: AC(0.2s, 224KB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2014-04-18 20:25:42                                     */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
int Pow(long long x, int n, long long mod) {
    long long Ans = 1, t = x;
    while(n) {
        if(n&1)
            Ans *= t, Ans %= mod;
        t *= t, t %= mod, n >>= 1;
    }
    return (int)Ans;
}
int JudgePrime(int n) {
    if(n == 2 || n == 3)    return 1;
    if(n == 1)    return 0;
    if(!(n&1))    return 0;
    int a, x, flag = 1, t;
    for(a = 0; a < 2; a++) {
        x = rand()%(n-4)+2;
        t = Pow(x, n-1, n);
        if(t != 1)    return 0;
    }
    return 1;
}
int main() {
    int n;
    while(scanf("%d", &n) == 1) {
        if(JudgePrime(n))    puts("質數");
        else    puts("非質數");
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

a576. No Cheating

題目

內容：

有個學校想辦一場考試，提供了 T 間教室。每間教室的座位都是 M×N 的矩陣(不同教室的 M, N 可以不一樣)，而有的座位壞掉了不能坐。此外，為了避免學生作弊，如下圖，對任何一個學生而言，他的左方、左前方、右方、右前方都不可以有人坐。請問每間教室所能容納的學生數最多為何？

輸入說明：

第一行有一個數字 T，代表學校有 T 間教室。接下來會有每個教室的資料，每筆資料會有在同一行兩個正整數 M, N，代表座位的配置是 M×N。接下來的 M 行，每行有 N 個字元，’.’代表那個座位是好的，而’x’則代表那個座位壞了。

輸出說明：

對於每間教室，輸出”Case #X: Y”, 其中 X 代表這是第幾間教室，而 Y 則代表這間教室能容納的學生數最大值。

範例輸入：

4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....

範例輸出：

Case #1: 4
Case #2: 1
Case #3: 2
Case #4: 46

解法

  • 作法：
    按列黑白染色，會發現不能連的位置恰好可以化成二分圖，求最大獨立集即可。
    最大獨立集 = 點個數 - 最大匹配數
a576.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/**********************************************************************************/
/*  Problem: a576 "No Cheating" from GCJ 2008 Round 3 C                           */
/*  Language: CPP (3826 Bytes)                                                    */
/*  Result: AC(0.1s, 1.2MB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2014-04-18 18:09:46                                     */
/**********************************************************************************/
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
using namespace std;
struct Node {
    int x, y, v;// x->y, v
    int next;
} edge[65536];
int e, head[6500], prev[6500], record[6500];
int level[6500], visited[6500];
void addEdge(int x, int y, int v) {
    edge[e].x = x, edge[e].y = y, edge[e].v = v;
    edge[e].next = head[x], head[x] = e++;
    edge[e].x = y, edge[e].y = x, edge[e].v = 0;
    edge[e].next = head[y], head[y] = e++;
}
bool buildLevelGraph(int s, int t) {
    memset(level, 0, sizeof(level));
    queue<int> Q;
    Q.push(s), level[s] = 1;
    while(!Q.empty()) {
        int tn = Q.front();
        Q.pop();
        for(int i = head[tn]; i != -1; i = edge[i].next) {
            int y = edge[i].y;
            if(edge[i].v > 0 && level[y] == 0) {
                level[y] = level[tn] + 1;
                Q.push(y);
            }
        }
    }
    return level[t] > 0;
}
int constructBlockingFlow(int s, int t) {
    int ret = 0;
    stack<int> stk;
    memset(visited, 0, sizeof(visited));
    stk.push(s);
    while(!stk.empty()) {
        int now = stk.top();
        if(now != t) {
            for(int i = head[now]; i != -1; i = edge[i].next) {
                int y = edge[i].y;
                if(visited[y] || level[y] != level[now] + 1)
                    continue;
                if(edge[i].v > 0) {
                    stk.push(y), prev[y] = now, record[y] = i;
                    break;
                }
            }
            if(stk.top() == now)
                stk.pop(), visited[now] = 1;
        } else {
            int flow = 1e+9, bottleneck;
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                flow = min(flow, edge[ri].v);
            }
            for(int i = t; i != s; i = prev[i]) {
                int ri = record[i];
                edge[ri].v -= flow;
                edge[ri^1].v += flow;
                if(edge[ri].v == 0)
                    bottleneck = prev[i];
            }
            while(!stk.empty() && stk.top() != bottleneck)
                stk.pop();
            ret += flow;
        }
    }
    return ret;
}
int maxflowDinic(int s, int t) {
    int flow = 0;
    while(buildLevelGraph(s, t))
        flow += constructBlockingFlow(s, t);
    return flow;
}
int main() {
    int n, m;
    int testcase, cases = 0;
    int i, j, k, x, y;
    char g[128][128];
    int id[128][128];
    scanf("%d", &testcase);
    while(testcase--) {
        e = 0;
        memset(head, -1, sizeof(head));
        scanf("%d %d", &n, &m);
        for(int i = 0; i < n; i++)
            scanf("%s", g[i]);
        int ST[2] = {0, 0};
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(g[i][j] == '.') {
                    id[i][j] = ST[j&1]++;
                } else {
                    id[i][j] = -1;
                }
            }
        } 
        int source = ST[0] + ST[1];
        int sink = source + 1;
        for(int i = 0; i < ST[0]; i++)
            addEdge(source, i, 1);
        for(int i = 0; i < ST[1]; i++)
            addEdge(i + ST[0], sink, 1);
        int dx[] = {-1, -1, 0, 0, 1, 1};
        int dy[] = {-1, 1, -1, 1, 1, -1};
        int tx, ty, u, v;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j += 2) {
                if(id[i][j] == -1)  
                    continue;
                v = id[i][j];
                for(int k = 0; k < 6; k++) {
                    tx = i + dx[k];
                    ty = j + dy[k];
                    if(tx < 0 || ty < 0 || tx >= n || ty >= m)
                        continue;
                    u = id[tx][ty];
                    if(u == -1)
                        continue;
                    addEdge(v, u + ST[0], 1);
                }
            }
        }
        int ret = maxflowDinic(source, sink);
        printf("Case #%d: %d\n", ++cases, ST[0] + ST[1] - ret);
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

a858. 數三角形

題目

內容：

你有一個大小為N的完全圖，這N(N-1)/2條邊可能是紅色或黑色。任三個不同的點都形成一個三角形，請問三邊同色的三角形有幾個？

輸入說明：

第一行輸入一個正整數N，其中N<=1,000。接下來的N行，每行有N個數字，其中第i行的第j個數字代表邊(i,j)的顏色，紅色用1表示，黑色用2表示，i=j時則用0表示。

輸出說明：

請輸出同色三角形的數目。

範例輸入：

4
0 1 2 1
1 0 1 1
2 1 0 2
1 1 2 0

範例輸出：

1

解法

  • 作法：
    分治，將輸入 n 個劃分成兩堆，分別窮舉所有可能，採用合併的方式去運算。
a858.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**********************************************************************************/
/*  Problem: a858 "數三角形" from                                             */
/*  Language: CPP (462 Bytes)                                                     */
/*  Result: AC(0.1s, 264KB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2014-04-17 11:06:20                                     */
/**********************************************************************************/
#include <stdio.h>
int main() {
    int n, x;
    while (scanf("%d", &n) == 1) {
        int p = (n) * (n-1) * (n-2) / 6;
        int s = 0;
        for (int i = 0; i < n; i++) {
            int b = 0, r = 0;
            for(int j = 0; j < n; j++) {
                scanf("%d", &x);
                r += x == 1;
                b += x == 2;
            }
            s += r * b;
        }
        printf("%d\n", p - s/2);
    }
    return 0;
}
Read More +
解題區/解題區 - Zerojudge

a962. 新專輯

題目

內容：

給定正整數N，請求出(N除以1的餘數)+(N除以2的餘數)+(N除以3的餘數)+…+(N除以N的餘數)。

輸入說明：

輸入只有一個正整數N，其中1<=N<=1014。

輸出說明：

為了避免要寫大數，你只要輸出這個奇怪的和除以1000000009的餘數就好了。

範例輸入：

10

範例輸出：

13

解法

  • 作法：
    各種方式要避免 mod 運算。
a962.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**********************************************************************************/
/*  Problem: a962 "新專輯" from TIOJ 1674                                      */
/*  Language: CPP (1612 Bytes)                                                    */
/*  Result: AC(0.8s, 272KB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2014-04-18 20:11:19                                     */
/**********************************************************************************/
#include <stdio.h>
#include <math.h>
#define MOD 1000000009LL
long long inv(long long n, long long m) { // get n*? = 1 (mod m)
    long long la = 1, lb = 0, ra = 0, rb = 1;
    long long i = 0, t, mod = m;
    while(n%m) {
        if(!i) {
            la -= n/m*ra;
            lb -= n/m*rb;
        } else {
            ra -= n/m*la;
            rb -= n/m*lb;
        }
        i = !i;
        t = n, n = m, m = t%m;
    }
    if(i)
        return (la%mod+mod)%mod;
    return (ra%mod+mod)%mod;
}
int main() {
    long long inv2 = inv(2, MOD);
    long long n;
    while(scanf("%lld", &n) == 1) {
        long long ret = 0, hret = 0;
        long long half = (long long)sqrt(n)/5;
        long long u = -1, v = 0;
        for(half = 1; u != v; half++, u = v, v = n/half) {
            hret += n%half;
        }
        hret -= n%(half - 1);
        hret %= MOD;
        long long l = half - 1, r, div;
        long long a0, d, tn, buff;
        while(l <= n) {
            div = n / l;
            r = n / div;
            a0 = n % l, d = -div, tn = r - l + 1;
            if(tn >= MOD)   tn %= MOD;
            if(d >= MOD)    d %= MOD;
            if(a0 >= MOD)   a0 %= MOD;
            buff = (a0 * 2 + (tn - 1)*d);
            if(buff < 0 || buff >= MOD) buff %= MOD;
            buff *= tn;
            if(buff < 0 || buff >= MOD) buff %= MOD;
            ret += buff;
            l = r + 1;
        }
        ret %= MOD;
        ret = (ret * inv2)%MOD;
        ret = (ret + hret + MOD)%MOD;
        printf("%lld\n", ret);
    }
    return 0;
}
/*
100000000000000
*/
Read More +
解題區/解題區 - Zerojudge

a981. 求和問題

題目

內容：

給你N個正整數, 試求哪幾個之和剛好為M, 印出所有合條件的解, 如有多組解, 請按由小到大的順序印出(格式可參考樣例輸出)

輸入說明：

n m (1<=n<=30, 1<=m<=100000000) n個正整數, 全部以空格分開

輸出說明：

  • 其和剛好等於m的數, 如果有多組解則按由小到大全部印出, 如果無解則印出 -1

範例輸入：

10 100
10 20 40 30 50 80 60 70 5 15

範例輸出：

5 10 15 20 50
5 10 15 30 40
5 10 15 70
5 15 20 60
5 15 30 50
5 15 80
10 20 30 40
10 20 70
10 30 60
10 40 50
20 30 50
20 80
30 70
40 60

解法

  • 作法：
    分治，將輸入 n 個劃分成兩堆，分別窮舉所有可能，採用合併的方式去運算。
a981.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
int main() {
    int n, m;
    int A[35];
    while(scanf("%d %d", &n, &m) == 2) {
        for(int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        sort(A, A + n, greater<int>());
        int h1Cnt = n / 2, h2Cnt = n - h1Cnt;
        map<long long, vector<int> > h1, h2;
        for(int i = (1<<h1Cnt)-1; i >= 0; i--) {
            long long sum = 0;
            for(int j = 0; j < h1Cnt; j++) {
                if((i>>j)&1)	sum += A[j];
            }
            h1[sum].push_back(i);
        }
        for(int i = (1<<h2Cnt)-1; i >= 0; i--) {
            long long sum = 0;
            for(int j = 0; j < h2Cnt; j++) {
                if((i>>j)&1)	sum += A[j + h1Cnt];
            }
            h2[sum].push_back(i<<h1Cnt);
        }
        set<int> ret;
        for(map<long long, vector<int> >::iterator it = h1.begin();
            it != h1.end(); it++) {
            long long f = (long long)m - it->first;
            map<long long, vector<int> >::iterator jt = h2.find(f);
            if(jt != h2.end()) {
                for(vector<int>::iterator iv = it->second.begin();
                    iv != it->second.end(); iv++) {
                    for(vector<int>::iterator jv = jt->second.begin();
                        jv != jt->second.end(); jv++) {
                        ret.insert(*iv| *jv);
                    }
                }
            }
        }
        if(ret.size() == 0)
            puts("-1");
        for(set<int>::reverse_iterator it = ret.rbegin();
            it != ret.rend(); it++) {
            for(int i = n-1; i >= 0; i--) {
                if(((*it)>>i)&1) {
                    printf("%d ", A[i]);
                }
            }
            puts("");
        }
    }
    return 0;
}
Read More +