I followed a seemingly different approach for the problem.
a) The basic idea used if we take bitwise xor of four numbers of the type 4N , 4N+1,4N+2,4N+3 it will always turn out to be zero.
b) we can represent a set of four elements by a number i as 4i, 4i+1, 4i+2,4i+3
c) for any number a , floor(a/4 )(conventional division in c++) is bound to form that 4 element set which contains the number a. We will not take this number in our set of i’s as we simply have sufficiently possible i’s to sufficiently fill the array.
So one can look at the array of size N in the following way:
if N%4==1 , we simply fill the first element of the array with X and for starting from i =0 we store all possible i’s 0,1,2… b such that size of this set is n/4 (not including X/4);
if N%4==2 then always 0,X is the possible pair to include . form a n/4 sized set of i’s which do not include 0,X/4;
Now the tricky part of N%4==3 and ==0 comes.
find the binary representation of X. All possible values of X can be represented in 19 bit size.
if N%4 == 3
we need to find three numbers a,b,c such that a^b^c = X.
3 cases arise:
i) 3 or more set bits:
a = 2**(i1) , b = 2**(i2) , c = X-a-b where i1,i2 are the 1st and 2nd bit position which are set.
ii) 2 bits are set:
a = 0 , b = 2**(i1) , c = 2**(i2) where i1,i2 are 1st,2nd set bits.
iii) only 1 bit is set:
if we take a = 0, b =0 , c = 2**(i1) duplicity arises. Two remove this we simply find j1 and j2 which are the 1st and 2nd bit positions not being set. we can modify a,b,c as:
a = 2**(j1) , b = 2**(j2) , c = 2**(i1)+a+b , j1 and j2 bit positions appear 2 times there contribution during bitwise xor becomes 0.
now simply omit a/4 , b/4 , and c/4 from the set of i’s of size N/4.
finally N%4==0 :
we need a,b,c,d 4 numbers gosh! but still it isn’t tough if properly thought of.
cases:
i) if X has 4 or more set bits:
simply a,b,c become 2 to powers i1,i2,i3 ; d = X-a-b-c
ii) 3 set bits:
a = 0, b,c,d are 2 raised to powes i1,i2,i3 respectively.
iii) 2 set bits:
we find j1,j2 as described in case N%4==3 and a = 2**(j1), b = 2**(j2) , c= a+2**(i1), d = b+2**(i2)
iv) only 1 set bit:
find j1,j2,j3 3 non-set bit positions and now a,b,c,d become:
a= 2**(j1) , b = 2**(j2) , c = 2**(j3) , d = 2**(i1) +a+b+c;
in this case we need i’s set of size N/4 -1 with no i equal to a/4,b/4,c/4 or d/4.
Finally for all possible values of i include the four element set in the array and you have your answer
In your code if X is less than n then X is surely repeated in your array. First find the elements of n%4 which xor to X and then sets of four which do not include the elements calculated for n%4;
#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);} #define rep(n) for(int i = 0;i<n;i++) #define rep1(a,b) for(int i = a;i<b;i++) #define int long long int #define mod 1000000007
int n, x;
void solve()
{
cin>>n>>x;
if(n==1){
cout<<x;
return;
}
int y = 0;
int ans[n];
for(int i = 0; i<n-1; i++){
ans[i] = i;
y ^= i;
}
int z = y^x;
int temp = 1<<18;
if(z>=n-1 && z<=500000){
ans[n-1] = z;
}
else{
ans[n-1] = z^temp;
if((ans[n-2] ^ temp) == ans[n-1]){
ans[0] ^= temp;
}
else{
ans[n-2] ^= temp;
}
}
for(int i = 0; i<n; i++){
cout<<ans[i]<<' ';
}
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
sync;
int t = 1;
cin>>t;
while(t--){
solve();
cout<<"\n";
}
return 0;
Thanks for updating the editorial. However, there is one more point. Z will still be less than 219, since the maximum number we can get with 19 bits is 219 - 1. @notsoloud
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define IOS ios::sync_with_stdio(0); cin.tie(0);
signed main() {
IOS;
int t; cin >> t;
const int M = 32;
int even = 4e5, odd = 4e5+1, zero = 0;
int even_two = 400000, odd_two = 400002;
int inf = 5e5+1;
while(t--) {
int n, x; cin >> n >> x;
cout << n << " " << x << "\n";
if(n == 1) {
cout << x << "\n";
} else if(n == 2) {
cout << 0 << " " << x << "\n";
} else {
set<int> ans;
int till = 0;
for(int i=1;i<=n-1;i++) {
// ans.insert(i);
till = till ^ i;
}
// n - 1 elements filled till here [1, 2, 3, ... n - 1]
int last = x ^ till;
// last ^ till = x; last = x ^ till;
// if last belongs to [1, 2, 3, ... n - 1]
if((last > 0) && (last < n)) {
auto it = ans.find(last);
if(last == 1) {
// don't want 1 in the array as [2 ^ 3 ^ ... ^ n - 1] = X
// erase 1 and 2
ans.erase(it);
// till = till ^ 1;
// till = till ^ 2;
// add three unique elements such that
ans.insert(even_two);
ans.insert(odd_two);
ans.insert(zero);
// till = till ^ even_two;
// till = till ^ odd_two;
// till = till ^ zero;
} else {
// don't want some number which is greater than one
ans.erase(it);
ans.erase(ans.begin());
// till = till ^ last;
// till = till ^ 1;
ans.insert(even);
ans.insert(odd);
ans.insert(zero);
// till = till ^ even;
// till = till ^ odd;
// till = till ^ zero;
}
} else {
if(last < inf) {
ans.insert(last);
till = till ^ last;
} else {
auto it = ans.upper_bound(last);
}
}
// int i = 0;
// cout << "SIZE: " << ans.size() << "\n";
// for(auto num : ans) {
// cout << i + 1 << " " << num << "\n";
// i += 1;
// }
// till = 0;
// for(auto num : ans) {
// till = till ^ num;
// }
cout << "XOR: " << till << "\n";
// assert(ans.size() == n);
assert(till == x);
// for(auto num : ans) {
// cout << num << " ";
// }
// cout << "\n";
}
}
}
It passes all the test cases for the first subtask but fails on every test case of the second subtask. I tried to debug for a very long time but couldn’t figure out the problem. What am i missing here?
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define IOS ios::sync_with_stdio(0); cin.tie(0);
signed main() {
IOS;
int t; cin >> t;
const int M = 32;
int even = 4e5, odd = 4e5+1, zero = 0;
int even_two = 400000, odd_two = 400002;
while(t--) {
int n, x; cin >> n >> x;
if(n == 1) {
cout << x << "\n";
} else if(n == 2) {
cout << 0 << " " << x << "\n";
} else {
set<int> ans;
// ans[0] = even, ans[1] = odd;
int till = 0;
for(int i=1;i<=n-1;i++) {
ans.insert(i);
till = till ^ i;
}
// n - 1 elements filled till here [1, 2, 3, ... n - 1]
int last = x ^ till;
// last ^ till = x; last = x ^ till;
// if last belongs to [1, 2, 3, ... n - 1]
if((last > 0) && (last < n)) {
auto it = ans.find(last);
if(it == ans.begin()) {
// don't want 1 in the array as [2 ^ 3 ^ ... ^ n - 1] = X
// erase 1 and 2
ans.erase(it);
ans.erase(2);
// add three unique elements such that
ans.insert(even_two);
ans.insert(odd_two);
ans.insert(zero);
} else {
// don't want some number except one
ans.erase(it);
ans.erase(ans.begin());
ans.insert(even);
ans.insert(odd);
ans.insert(zero);
}
} else {
ans.insert(last);
}
int i = 0;
// cout << "SIZE: " << ans.size() << "\n";
// for(auto num : ans) {
// cout << i + 1 << " " << num << "\n";
// i += 1;
// }
till = 0;
for(auto num : ans) {
till = till ^ num;
}
// cout << "XOR: " << till << "\n";
// assert(ans.size() == n);
// assert(till == x);
for(auto num : ans) {
cout << num << " ";
}
cout << "\n";
}
}
}
This is the code that passes the first subtask. What’s going wrong here?
