Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Solution {
- static Scanner sc = new Scanner(System.in);
- public static int mischievousChild(int N, int[] Child,int D, int[] Day){
- for(int i=0;i<D;i++) {
- Day[i]--; // Because we are using 0 based indexing so changing children number from (1 to N) to (0 to N-1)
- }
- int[] separate = new int[N];
- for(int i=0;i<N;i++) {
- separate[i] = 10000000;
- }
- for(int i=0;i<D;i++) { // to keep count on what day was he separated so that we can decide
- separate[Day[i]] = i; // whether he was changed or not changed before ith the day
- }
- Queue<Integer> q = new LinkedList<>();
- for(int i=0;i<N;i++) {
- if(i==0){
- if(Child[i] == 1 && Child[i+1]==0){
- q.add(i);
- }
- }
- else if(i==N-1){
- if(Child[i] == 1 && Child[i-1]==0){
- q.add(i);
- }
- }
- else{
- if(Child[i]==1 && (Child[i+1]==0 || Child[i-1]==0)){
- q.add(i); // if there is sequence like 1 1 1 the middle one is
- } // not contributing to the answer so excluded it.
- }
- }
- for(int i=0;i<D;i++){
- if(q.size()==0){
- break;
- }
- else{
- int size = q.size();
- for(int j =0 ;j<size;j++){
- int tempChild = q.remove();
- if(tempChild>0 && Child[tempChild-1]==0 && separate[tempChild]>i){
- Child[tempChild-1] = 1;
- q.add(tempChild-1);
- }
- if(tempChild+1<N && Child[tempChild+1]==0 && separate[tempChild+1]>i){
- Child[tempChild+1] = 1;
- q.add(tempChild+1);
- }
- }
- }
- }
- int ans = 0;
- for(int i=0;i<N;i++){
- if(Child[i]==1)ans++;
- }
- return ans;
- }
- public static void main(String[] args) {
- int N;
- N = sc.nextInt();
- int[] Child = new int[N];
- for(int i=0;i<N;i++) {
- Child[i] = sc.nextInt();
- }
- int D;
- D = sc.nextInt();
- int[] Day = new int[D];
- for(int i=0;i<D;i++) {
- Day[i] = sc.nextInt();
- }
- System.out.println(mischievousChild(N,Child,D,Day));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement