nickmikemurderer's blog

By nickmikemurderer, history, 3 years ago, In English

import java.io.DataInputStream; import java.io.FileInputStream; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; public class MeetInTheMiddle { 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 x=s.nextInt(); int a[]=new int[n/2]; int b[]=new int[n-n/2]; for(int i=0;i<n/2;i++){ a[i]=s.nextInt(); } for(int i=0;i<b.length;i++){ b[i]=s.nextInt(); } ArrayList<Long> list1=getMap(a); ArrayList<Long> list2=getMap(b); Collections.sort(list2); long ans=0; for(long i:list1){ long reqd=x-i; if(reqd>=0){ int ans1=-1,ans2=-1; int low=0,high=list2.size()-1; while(low<=high){ int mid=(low+high)>>1; long el=list2.get(mid); if(el>reqd){ high=mid-1; } else if(el<reqd){ low=mid+1; } else{ ans1=mid; high=mid-1; } } low=0;high=list2.size()-1; while(low<=high){ int mid=(low+high)>>1; long el=list2.get(mid); if(el>reqd){ high=mid-1; } else if(el<reqd){ low=mid+1; } else{ ans2=mid; low=mid+1; } } if(ans1!=-1){ ans+=ans2-ans1+1; } } } System.out.println(ans); } public static ArrayList<Long> getMap(int a[]){ ArrayList<Long> list=new ArrayList<>(); int l=a.length; for(int i=0;i<(1<<l);i++){ long sum=0; for(int j=0;j<a.length;j++){ if((i&(1<<j))!=0){ sum+=a[j]; } } list.add(sum); } return list; } }

My Code gives TLE, but c++ code with same logic is accepted. Kindly Help

  • Vote: I like it
  • -14
  • Vote: I do not like it