And Matching Solution|Codeforces round #768 (div 2)

                                                            C. And Matching

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a set of n$n$ (n$n$ is always a power of 2$2$) elements containing all integers 0,1,2,…,n−1$0,1,2,\dots ,n-1$ exactly once.

Find n2$\frac{n}{2}$ pairs of elements such that:

• Each element in the set is in exactly one pair.
• The sum over all pairs of the bitwise AND of its elements must be exactly equal to k$k$. Formally, if ai$a_i$ and bi$b_i$ are the elements of the i$i$-th pair, then the following must hold:
  ∑i=1n/2ai&bi=k,$$\sum _{i=1}^{n/2}{a}_i\mathrm{\&}{b}_i=k,$$
  where &$\mathrm{\&}$ denotes the bitwise AND operation.

If there are many solutions, print any of them, if there is no solution, print −1$-1$ instead.

Input

The input consists of multiple test cases. The first line contains a single integer t$t$ (1≤t≤400$1\le t\le 400$) — the number of test cases. Description of the test cases follows.

Each test case consists of a single line with two integers n$n$ and k$k$ (4≤n≤216$4\le n\le 2^{16}$, n$n$ is a power of 2$2$, 0≤k≤n−1$0\le k\le n-1$).

The sum of n$n$ over all test cases does not exceed 216$2^{16}$. All test cases in each individual input will be pairwise different.

Output

For each test case, if there is no solution, print a single line with the integer −1$-1$.

Otherwise, print n2$\frac{n}{2}$ lines, the i$i$-th of them must contain ai$a_i$ and bi$b_i$, the elements in the i$i$-th pair.

If there are many solutions, print any of them. Print the pairs and the elements in the pairs in any order.

Note

In the first test, (0&3)+(1&2)=0$(0\mathrm{\&}3)+(1\mathrm{\&}2)=0$.

In the second test, (0&2)+(1&3)=1$(0\mathrm{\&}2)+(1\mathrm{\&}3)=1$.

In the third test, (0&1)+(2&3)=2$(0\mathrm{\&}1)+(2\mathrm{\&}3)=2$.

In the fourth test, there is no solution.

Solution:

1. #include<bits/stdc++.h>
2. using namespace std;
3. #define int long long
4. #define fi first
5. #define se second
6. #define pii pair<long long,long long>
7. #define mp make_pair
8. #define pb push_back
9. const int mod=998244353;
10. const int inf=0x3f3f3f3f;
11. const int INF=1e18;
12. int fpow(int x,int b){
13. if(x==0) return 0;
14. if(b==0) return 1;
15. int res=1;
16. while(b>0){
17. if(b&1) res=res*x%mod;
18. x=x*x%mod;
19. b>>=1;
20. }
21. return res;
22. }
23. int fac[300005];
24. int C(int x,int y)
25. {
26. return fac[y]*fpow(fac[y-x],mod-2)%mod*fpow(fac[x],mod-2)%mod;
27. }
28. int n;
29. int a[200005];
30. int t[800005];
31. void update(int id,int l,int r,int x,int d)
32. {
33. if(l==r)
34. {
35. t[id]=d;
36. return;
37. }
38. int mid=(l+r)>>1;
39. if(x<=mid) update(id<<1,l,mid,x,d);
40. else update(id<<1|1,mid+1,r,x,d);
41. t[id]=min(t[id<<1],t[id<<1|1]);
42. }
43. int query(int id,int l,int r,int x,int y)
44. {
45. if(x>y) return INF;
46. if(x<=l&&r<=y) return t[id];
47. int mid=(l+r)>>1;
48. int res=INF;
49. if(x<=mid) res=min(res,query(id<<1,l,mid,x,y));
50. if(y>mid) res=min(res,query(id<<1|1,mid+1,r,x,y));
51. return res;
52. }
53. int dp[200005];
54. vector <pii > vec;
55. int l[200005],r[200005];
56. bool cmp(pii x,pii y)
57. {
58. if(x.se==y.se) return x.fi<y.fi;
59. else return x.se<y.se;
60. }
61. void solve()
62. {
63. memset(t,0x3f,sizeof(t));
64. memset(dp,0x3f,sizeof(dp));
65. memset(l,0x3f,sizeof(l));
66. memset(r,-0x3f,sizeof(r));
67. scanf("%lld",&n);
68. for(int i=1;i<=n;i++) scanf("%lld",&a[i]),l[a[i]]=min(l[a[i]],i),r[a[i]]=max(r[a[i]],i);
69. for(int i=1;i<=n;i++) if(l[i]<=r[i]) vec.pb(mp(l[i],r[i]));
70. sort(vec.begin(),vec.end(),cmp);
71. dp[0]=0;
72. for(int i=1;i<=n;i++) dp[i]=i,update(1,1,n,i,i);
73. for(int i=0;i<vec.size();i++)
74. {
75. if(vec[i].fi==vec[i].se) dp[vec[i].se]=min(dp[vec[i].se],dp[vec[i].fi-1]+1);
76. else dp[vec[i].se]=min(dp[vec[i].se],dp[vec[i].fi-1]+2);
77. dp[vec[i].se]=min(dp[vec[i].se],query(1,1,n,vec[i].fi+1,vec[i].se-1)+1);
78. update(1,1,n,vec[i].se,dp[vec[i].se]);
79. }
80. cout<<n-dp[n];
81. }
82. signed main()
83. {
84. int _=1;
85. //cin>>_;
86. while(_--) solve();
87. return 0;
88. }
89.