Advertisement
saurav_kalsoor

Untitled

Jun 22nd, 2022
917
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.64 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class Solution {
  4.    
  5.     static Scanner sc = new Scanner(System.in);
  6.    
  7.     public static int mischievousChild(int N, int[] Child,int D, int[] Day){
  8.        
  9.         for(int i=0;i<D;i++) {
  10.             Day[i]--;        // Because we are using 0 based indexing so changing children number from (1 to N) to (0 to N-1)
  11.         }
  12.        
  13.         int[] separate = new int[N];
  14.        
  15.         for(int i=0;i<N;i++) {
  16.             separate[i] = 10000000;
  17.         }
  18.        
  19.         for(int i=0;i<D;i++) {           //   to keep count on what day was he separated so that we can decide  
  20.             separate[Day[i]] = i;        //   whether he was changed or not changed before ith the day
  21.         }
  22.        
  23.         Queue<Integer> q = new LinkedList<>();
  24.        
  25.         for(int i=0;i<N;i++) {
  26.             if(i==0){
  27.                 if(Child[i] == 1 && Child[i+1]==0){
  28.                     q.add(i);
  29.                 }
  30.             }
  31.             else if(i==N-1){
  32.                 if(Child[i] == 1 && Child[i-1]==0){
  33.                     q.add(i);
  34.                 }
  35.             }
  36.             else{
  37.                 if(Child[i]==1 && (Child[i+1]==0 || Child[i-1]==0)){
  38.                     q.add(i);     // if there is sequence like 1 1 1 the middle one is
  39.                 }                 // not contributing to the answer so excluded it.
  40.             }
  41.         }
  42.        
  43.         for(int i=0;i<D;i++){
  44.             if(q.size()==0){
  45.                 break;
  46.             }
  47.             else{
  48.                 int size = q.size();
  49.                 for(int j =0 ;j<size;j++){
  50.                     int tempChild = q.remove();
  51.      
  52.                     if(tempChild>0 && Child[tempChild-1]==0 && separate[tempChild]>i){
  53.                         Child[tempChild-1] = 1;
  54.                         q.add(tempChild-1);
  55.                     }
  56.                     if(tempChild+1<N && Child[tempChild+1]==0 && separate[tempChild+1]>i){
  57.                         Child[tempChild+1] = 1;
  58.                         q.add(tempChild+1);
  59.                     }
  60.                 }
  61.             }
  62.         }
  63.         int ans = 0;
  64.          
  65.         for(int i=0;i<N;i++){
  66.             if(Child[i]==1)ans++;
  67.         }
  68.        
  69.         return ans;
  70.     }
  71.    
  72.     public static void main(String[] args) {
  73.         int N;
  74.         N = sc.nextInt();
  75.        
  76.         int[] Child = new int[N];
  77.        
  78.         for(int i=0;i<N;i++) {
  79.             Child[i] = sc.nextInt();
  80.         }
  81.        
  82.         int D;
  83.         D = sc.nextInt();
  84.        
  85.         int[] Day = new int[D];
  86.        
  87.         for(int i=0;i<D;i++) {
  88.             Day[i] = sc.nextInt();
  89.         }
  90.        
  91.        
  92.         System.out.println(mischievousChild(N,Child,D,Day));
  93.     }
  94. }
  95.  
  96.  
  97.  
  98.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement