help plz - Parity Again
I have got partial in this question. I m getting tle in 2nd subtask.But I have no idea how to get ac.
plz help me. Tried a lot.
https://www.codechef.com/JULY19B/problems/PRTAGN
queries. Initially, S is empty. In each query:
You are given a positive integer X.
You should insert X into S.
For each y∈S before this query such that y≠X, you should also insert y⊕X into S (⊕ denotes the XOR operation).
Then, you should find two values E and O: the number of elements of S with an even number of 1-s and with an odd number of 1-s in the binary representation, respectively.
Note that a set cannot have duplicate elements, so if you try to insert into S an element that is already present in S, then nothing happens.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer Q.
Each of the next Q lines contains a single integer X describing a query.
Output
For each query, print a single line containing two space-separated integers E and O.
Constraints
1≤T≤5
1≤Q,X≤105
Subtasks
Subtask #1 (30 points):
1≤Q≤1,000
1≤X≤128
Subtask #2 (70 points): original constraints
Example Input
1
3
4
2
7
Example Output
0 1
1 2
3 4
Explanation
Example case 1:
Initially, the set is empty: S={}.
After the first query, S={4}, so there is only one element with an odd number of 1-s in the binary representation ("100").
After the second query, S={4,2,6}, there is one element with an even number of 1-s in the binary representation (6 is "110") and the other two elements have an odd number of 1-s.
After the third query, S={4,2,6,7,3,5,1}
Plz help me in optimising the code.any small hint will be appreciated.
plz help me. Tried a lot.
https://www.codechef.com/JULY19B/problems/PRTAGN
queries. Initially, S is empty. In each query:
You are given a positive integer X.
You should insert X into S.
For each y∈S before this query such that y≠X, you should also insert y⊕X into S (⊕ denotes the XOR operation).
Then, you should find two values E and O: the number of elements of S with an even number of 1-s and with an odd number of 1-s in the binary representation, respectively.
Note that a set cannot have duplicate elements, so if you try to insert into S an element that is already present in S, then nothing happens.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer Q.
Each of the next Q lines contains a single integer X describing a query.
Output
For each query, print a single line containing two space-separated integers E and O.
Constraints
1≤T≤5
1≤Q,X≤105
Subtasks
Subtask #1 (30 points):
1≤Q≤1,000
1≤X≤128
Subtask #2 (70 points): original constraints
Example Input
1
3
4
2
7
Example Output
0 1
1 2
3 4
Explanation
Example case 1:
Initially, the set is empty: S={}.
After the first query, S={4}, so there is only one element with an odd number of 1-s in the binary representation ("100").
After the second query, S={4,2,6}, there is one element with an even number of 1-s in the binary representation (6 is "110") and the other two elements have an odd number of 1-s.
After the third query, S={4,2,6,7,3,5,1}
Plz help me in optimising the code.any small hint will be appreciated.
Last edited on
Topic archived. No new replies allowed.