Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int mischievousChild(int N, vector<int> &Child, int D, vector<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)
- }
- vector<int> separate(N,10000); // To know that this guy was not separated by looking at the constraint initialise with a very large number.
- for(int i=0;i<D;i++){
- 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
- }
- queue<int> q;
- for(int i=0;i<N;i++){
- if(i==0){
- if(Child[i] == 1 && Child[i+1]==0){
- q.push(i);
- }
- }
- else if(i==N-1){
- if(Child[i] == 1 && Child[i-1]==0){
- q.push(i);
- }
- }
- else{
- if(Child[i]==1 && (Child[i+1]==0 || Child[i-1]==0)){
- q.push(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.front();
- q.pop();
- if(tempChild>0 && Child[tempChild-1]==0 && separate[tempChild]>i){
- Child[tempChild-1] = 1;
- q.push(tempChild-1);
- }
- if(tempChild+1<N && Child[tempChild+1]==0 && separate[tempChild+1]>i){
- Child[tempChild+1] = 1;
- q.push(tempChild+1);
- }
- }
- }
- }
- int ans = 0;
- for(int i=0;i<N;i++){
- if(Child[i]==1)ans++;
- }
- return ans;
- }
- int main(){
- int N;
- cin>>N;
- vector<int> Child(N);
- for(int i=0;i<N;i++){
- cin>>Child[i];
- }
- int D;
- cin>>D;
- vector<int> Day(D);
- for(int i=0;i<D;i++){
- cin>>Day[i];
- }
- cout<<mischievousChild(N,Child,D,Day)<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment