SLIMSHADYNICK's blog

Solution getting TLE in java
By SLIMSHADYNICK, history, 4 years ago, In English

Problem Link ~~~~~ import java.io.*; import java.util.Arrays; import java.util.StringTokenizer;

public class Present { static class Reader { final private int BUFFER_SIZE = 1 << 16; private DataInputStream din; private byte[] buffer; private int bufferPointer, bytesRead;

public Reader()
    {
        din = new DataInputStream(System.in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public Reader(String file_name) throws IOException
    {
        din = new DataInputStream(new FileInputStream(file_name));
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public String readLine() throws IOException
    {
        byte[] buf = new byte[64]; // line length
        int cnt = 0, c;
        while ((c = read()) != -1)
        {
            if (c == '\n')
                break;
            buf[cnt++] = (byte) c;
        }
        return new String(buf, 0, cnt);
    }

    public int nextInt() throws IOException
    {
        int ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do
        {
            ret = ret * 10 + c - '0';
        }  while ((c = read()) >= '0' && c <= '9');

        if (neg)
            return -ret;
        return ret;
    }

    public long nextLong() throws IOException
    {
        long ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');
        if (neg)
            return -ret;
        return ret;
    }

    public double nextDouble() throws IOException
    {
        double ret = 0, div = 1;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();

        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');

        if (c == '.')
        {
            while ((c = read()) >= '0' && c <= '9')
            {
                ret += (c - '0') / (div *= 10);
            }
        }

        if (neg)
            return -ret;
        return ret;
    }

    private void fillBuffer() throws IOException
    {
        bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
        if (bytesRead == -1)
            buffer[0] = -1;
    }

    private byte read() throws IOException
    {
        if (bufferPointer == bytesRead)
            fillBuffer();
        return buffer[bufferPointer++];
    }

    public void close() throws IOException
    {
        if (din == null)
            return;
        din.close();
    }
}
public static void main(String[] args)throws IOException {
    Reader s=new Reader();
    int n=s.nextInt();
    int a[]=new int[n+1];
    for(int i=1;i<=n;i++){
        a[i]=s.nextInt();
    }
    int ans=0;
    for(int i=0;i<=25;i++){
        int b[]=getArray(a,i);
        Arrays.sort(b);
        long count=getCount(b,n,i);
        if(count%2!=0){
            ans|=1<<i;
        }
    }
    System.out.println(ans);
}
public static int[] getArray(int a[],int k){
    int b[]=new int[a.length];
    int t=1<<(k+1);
    for(int i=1;i<a.length;i++){
        b[i]=a[i]%t;
    }
    return b;
}
public static long getCount(int b[],int n,int k){
    long ans=0;
    int left1=1<<k;
    int right1=1<<(k+1);
    int left2=(1 << k) + (1 << (k + 1));
    int right2=1 << (k + 2) - 1;
    int x=n+1;
    for(int i=1;i<=n;i++){
        int rc=getInd(b,i,n,left1);
        if(rc==x){
            continue;
        }
        int lc=getInd(b,i,n,right1);
        ans+=lc-rc;
        if(k!=0) {
            rc = getInd(b, i, n, left2);
            if(rc==x){
                continue;
            }
            lc = getInd(b, i, n, right2);
            ans += lc - rc;
        }
    }
    return ans;
}
public static int getInd(int a[],int ind,int n,int reqd){
    int num=a[ind];
    int low=ind+1;
    int high=n;
    int ans=n+1;
    while(low<=high){
        int mid=(low+high)/2;
        if(a[mid]+num>=reqd){
            ans=mid;
  • Vote: I like it
  • -10
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by SLIMSHADYNICK (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It is solved now . Time limit was very tight. I used bitwise >> 1 instead of /2 in binary search to get rid of TLE.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Time limit was very tight in this.. u could use fast scan also and bitwise operators to rid of it

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In such tight time limit you may use ArrayList instead of array because Collections.sort() is faster than Arrays.sort() or if you want to stick with array then use Arrays.parallelSort()

→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

You shouldn't use Arrays.sort for primitive arrays like int[], long[], etc. as for those it uses quicksort and is worst case $$$O(n^2)$$$. Instead, you should swap out int[] for Integer[], (or long[] for Long[]), as for arrays of Objects, Arrays.sort uses Timsort, which is worst case $$$O(n\log n)$$$.

→ Reply