Submission #5288178

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.first<<","<<p.second<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#else
#define dbg(...) {}
#endif

bool solve(){
  int n;
  string s;
  int ox,xo,o,x;
  cin>>n>>s>>ox>>xo>>o>>x;

  int xs=0, os=0;
  rep(i,n){
    if(s[i]=='o') os++;
    else xs++;
  }

  if(os != ox+xo+o || xs != ox+xo+x) return false;

  vector<int> oxs, xos;
  int both = 0;
  int oxsum = 0, xosum = 0;
  int p=0;
  while(p<n){
    int k=0;
    while(p+k+1<n && s[p+k] != s[p+k+1]) k++;
    if(k>0){
      k++;
      if(k%2==1) both += k/2;
      else if(s[p]=='o') {
        oxs.push_back(k);
        oxsum+= k/2;
      }
      else {
        xos.push_back(k);
        xosum += k/2;
      }
      p += k;
    } else p++;
  }

  auto ok = [&](){
    return max(0, ox - oxsum) + max(0, xo - xosum) <= both;
  };
dbg(oxsum, xosum);
  if(ok()) return true;
  if(ox - oxsum > 0 && xo - xosum > 0) return false;

  if(ox - oxsum > 0) {
    swap(ox, xo);
    swap(oxsum, xosum);
    swap(xos, oxs);
  }

  // ox -> xo
  sort(all(oxs));
  oxs.push_back(1);
  while(oxsum > 0){
    if(oxs.back() == 1){
      oxs.pop_back();
      if(oxs.empty()) break;
      oxs.back()--;
      oxsum--;
      continue;
    }

    oxs.back() -= 2;

    oxsum--;
    xosum++;

    dbg(oxsum, xosum, oxs);

    if(ok()) return true;
  }

  return false;
}

int main(){
  cout << (solve() ? "Yes" : "No") << endl;
  return 0;
}

Submission Info

Judge Result