Rishabh.Jain's blog

By Rishabh.Jain, history, 3 years ago, In English

Problem: Cards

This code got accepted

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define int lli
int n;
int m;
vector<int> arr;
vector<int> inp;
void can(int pos){
  if(pos == m){
    cout<<"YES"<<endl;
    exit(0);
  }

  int  cur = inp[pos];
  assert(cur>=0);

  if(arr[cur]<=0){
    return;
  }

  arr[cur]--;

  if(cur == 0){
    if(arr[cur+1]>0){
      arr[cur+1]--;
      can(pos+1);
      arr[cur+1]++;
    }
  }else{
    if(arr[cur-1]>0){
      arr[cur-1]--;
      can(pos+1);
      arr[cur-1]++;
    }
    if(arr[cur+1]>0){
      arr[cur+1]--;
      can(pos+1);
      arr[cur+1]++;
    }

  }
}
void solve(){
  cin>>n>>m;
  arr.resize(n+4);
  inp.resize(m);
  for(int i=1;i<=n;i++){
    arr[i-1]++;
    arr[i]++;
  }

  for(int i=0;i<m;i++){
    cin>>inp[i];
  }
  sort(inp.begin(), inp.end());
  can(0);

  cout<<"NO"<<endl;
}
signed main(){
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   solve();
}

But the following code, which is essentially the same(looks same to me) didn't:

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define int lli
int n;
int m;
vector<int> arr;
vector<int> inp;
void can(int pos){
  if(pos == m){
    cout<<"YES"<<endl;
    exit(0);
  }

  int  cur = inp[pos];
  assert(cur>=0);

  if(arr[cur]<=0){
    return;
  }

  arr[cur]--;

  if(cur == 0){
    if(arr[cur+1]>0){
      arr[cur+1]--;
      can(pos+1);
      arr[cur+1]++;
    }
  }else{
    if(arr[cur+1]>0){
      arr[cur+1]--;
      can(pos+1);
      arr[cur+1]++;
    }

    if(arr[cur-1]>0){
      arr[cur-1]--;
      can(pos+1);
      arr[cur-1]++;
    }
  }
}
void solve(){
  cin>>n>>m;
  arr.resize(n+4);
  inp.resize(m);
  for(int i=1;i<=n;i++){
    arr[i-1]++;
    arr[i]++;
  }

  for(int i=0;i<m;i++){
    cin>>inp[i];
  }
  sort(inp.begin(), inp.end());
  can(0);

  cout<<"NO"<<endl;
}
signed main(){
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   solve();
}

I want to know what's causing this, aren't both the same? It's my first blog so I am learning how to write a good looking blog, be merciful in that respect. If the doubt is stupid, I'll happily accept the downvotes.

Thanks, in advance.

Full text and comments »

  • Vote: I like it
  • -27
  • Vote: I do not like it