Create a gist now

Instantly share code, notes, and snippets.

#include <bits/stdc++.h>
using namespace std;
#define int long long // <-----!!!!!!!!!!!!!!!!!!!
#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto x : v){cout << x << " ";} cout << endl
#define printVS(vs) for(auto x : vs){cout << x << endl;}
#define printVV(vv) for(auto v : vv){for(auto&& x : v){cout << x << " ";}cout << endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto p : vp) printP(p);
typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;
bool dfs(string s) {
if (s == "ABC") {
return true;
} else if (s.find("ABC") == string::npos) {
return false;
}
vector<bool> valid(3, true);
{
string t;
int i = 0;
while (i < s.size()) {
if (i <= (int)s.size() - 3 && s.substr(i, 3) == "ABC") {
i += 3;
} else {
t += s[i];
i++;
}
}
rep(i, t.size()) {
valid[t[i] - 'A'] = false;
}
}
bool ret = false;
rep(k, 3) {
if (!valid[k]) continue;
string t;
int i = 0;
while (i < s.size()) {
if (i <= (int)s.size() - 3 && s.substr(i, 3) == "ABC") {
t += 'A' + k;
i += 3;
} else {
t += s[i];
i++;
}
}
ret |= dfs(t);
}
return ret;
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
string s;
cin >> s;
cout << (dfs(s) ? "Yes" : "No") << endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment