Samkit5025

Untitled

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