Samkit5025

Untitled

Jun 18th, 2022
49
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.  
  36. for(int i=0;i<D;i++){
  37. if(q.size()==0){
  38. break;
  39. }
  40. else{
  41. int size = q.size();
  42. for(int j =0 ;j<size;j++){
  43. int tempChild = q.front();
  44. q.pop();
  45.  
  46. if(tempChild>0 && Child[tempChild-1]==0 && separate[tempChild]>i){
  47. Child[tempChild-1] = 1;
  48. q.push(tempChild-1);
  49. }
  50. if(tempChild+1<N && Child[tempChild+1]==0 && separate[tempChild+1]>i){
  51. Child[tempChild+1] = 1;
  52. q.push(tempChild+1);
  53. }
  54. }
  55. }
  56. }
  57.  
  58. int ans = 0;
  59.  
  60. for(int i=0;i<N;i++){
  61. if(Child[i]==1)ans++;
  62. }
  63.  
  64. return ans;
  65. }
  66.  
  67. int main(){
  68. int N;
  69. cin>>N;
  70. vector<int> Child(N);
  71. for(int i=0;i<N;i++){
  72. cin>>Child[i];
  73. }
  74. int D;
  75. cin>>D;
  76. vector<int> Day(D);
  77. for(int i=0;i<D;i++){
  78. cin>>Day[i];
  79. }
  80.  
  81. cout<<mischievousChild(N,Child,D,Day)<<endl;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment