Continuing the discussion from ENGXOR - Editorial:
Why am I getting tle in subtask 2??
https://www.codechef.com/viewsolution/30429316
Continuing the discussion from ENGXOR - Editorial:
Why am I getting tle in subtask 2??
https://www.codechef.com/viewsolution/30429316
You are getting a TLE because your method for checking number of 1’s in query is O(n) you try using this method instead because it operates in O(1) time.
private static int meth(int a)
{
a^=a>>16;
a^=a>>8;
a^=a>>4;
a&=0xf;
return (0x6996 >> a) & 1;
}
It returns 1 for odd no of 1s and 0 for even
This property might come in hand(this is similar to XOR but kinda extended):
XOR of two numbers where both have even/odd set bit count => Output has even set bits.
Example:
x = 3 (011) [HAS 2 SET BITS]
y = 15 (1111) [HAS 4 SET BITS]
Both have even SET bits.
Their XOR is 12 (1100). It have even bits.
XOR of two numbers where both have different number of set bit(one has even bit and another has odd bits) => Output has odd set bits.
Yeah I have done the same
Checked for number of elements with even number of 1s(C1) and odd number of 1s(n-c1).
Then for each query if the query contains even number of 1s then print c1,n-c1 else n-c1,C1.
But Integer.bitCount uses O(1) time
The input/output is quite large, please use fast reading and writing methods.
yeah but i have used the fastest i/o method using datastream .
I don’t use Java so I can’t say.
You didn’t. For fast output you need to use PrintWriter.
In your code:
On line 142, I added: PrintWriter out = new PrintWriter(System.out);
On line 156&158 I replaced: System.out.println
with out.println
On line 160, I added: out.flush();