Блог пользователя SLIMSHADYNICK

Автор SLIMSHADYNICK, история, 4 года назад, По-английски

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;
  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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()

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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)$$$.