Samkit5025

Untitled

Jun 18th, 2022
44
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.18 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int mischievousChild(int N, vector<int> &Child, int D, vector<int> &Day){
  5. for(int i=0;i<D;i++){
  6. Day[i]--; // Because we are using 0 based indexing so changing children number from (1 to N) to (0 to N-1)
  7. }
  8.  
  9. vector<int> separate(N,10000); // To know that this guy was not separated by looking at the constraint initialise with a very large number.
  10.  
  11. for(int i=0;i<D;i++){
  12. separate[Day[i]] = i; // to keep count on what day was he separated so that we can decide whether he was changed or not changed before ith the day
  13. }
  14.  
  15. queue<int> q;
  16.  
  17. for(int i=0;i<N;i++){
  18. if(i==0){
  19. if(Child[i] == 1 && Child[i+1]==0){
  20. q.push(i);
  21. }
  22. }
  23. else if(i==N-1){
  24. if(Child[i] == 1 && Child[i-1]==0){
  25. q.push(i);
  26. }
  27. }
  28. else{
  29. if(Child[i]==1 && (Child[i+1]==0 || Child[i-1]=='0')){
  30. q.push(i); // if there is sequence like 1 1 1 the middle one is not contributing to the answer so excluded it.
  31. }
  32. }
  33. }
  34.  
  35. for(int i=0;i<D;i++){
  36. if(q.size()==0){
  37. break;
  38. }
  39. else{
  40. int size = q.size();
  41. for(int j =0 ;j<size;j++){
  42. int tempChild = q.front();
  43. q.pop();
  44.  
  45. if(tempChild>0 && Child[tempChild-1]==0 && separate[tempChild]>i){
  46. Child[tempChild-1] = 1;
  47. q.push(tempChild-1);
  48. }
  49. if(tempChild+1<N && Child[tempChild+1]==0 && separate[tempChild+1]>i){
  50. Child[tempChild+1] = 1;
  51. q.push(tempChild+1);
  52. }
  53. }
  54. }
  55. }
  56.  
  57. int ans = 0;
  58.  
  59. for(int i=0;i<N;i++){
  60. if(Child[i]==1)ans++;
  61. }
  62.  
  63. return ans;
  64. }
  65.  
  66. int main(){
  67. int N;
  68. cin>>N;
  69. vector<int> Child(N);
  70. for(int i=0;i<N;i++){
  71. cin>>Child[i];
  72. }
  73. int D;
  74. cin>>D;
  75. vector<int> Day(D);
  76. for(int i=0;i<D;i++){
  77. cin>>Day[i];
  78. }
  79.  
  80. cout<<mischievousChild(N,Child,D,Day)<<endl;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment