Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #6005413

Source Code Expand

Copy
```///////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <typeinfo>
#include <numeric>
#include <cassert>
#include <string.h>

using namespace std;

///////////////////////////////////////////////////////////////////////////////

#define pb push_back
#define V vector
#define M unordered_map
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll, ll> t2;
typedef tuple<ll, ll, ll> t3;
typedef tuple<ll, ll, ll, ll> t4;

struct UnionFind
{
ull *parent, *count, *rank;

UnionFind(ull n) {
parent = new ull[n+1];
count = new ull[n+1];
rank = new ull[n+1];
for (ull i = 0ULL; i < n+1; ++i) {
parent[i] = i;
count[i] = 1;
rank[i] = 0;
}
}

ull root(ull i) {
if (parent[i] == i) return i;
parent[i] = root(parent[i]);
return parent[i];
}

void unite(ull i, ull j) {
ull rooti = root(i);
ull rootj = root(j);

if (rooti == rootj) return;

if (rank[rootj] < rank[rooti]) {
parent[i] = parent[j] = parent[rootj] = rooti;
count[rooti] += count[rootj];
}
else {
parent[i] = parent[j] = parent[rooti] = rootj;
count[rootj] += count[rooti];
if (rank[rootj] == rank[rooti]) rank[rootj]++;
}
}

bool same(ull i, ull j) {
return root(i) == root(j);
}
};

struct BIT
{
ll *tree;
ll size;

BIT(ll n, ll init) {
tree = new ll[n+1];
size = n;
rep (i, n+1) tree[i] = init;
}

// idx is 1 origin
void add(ll idx, ll x) {
assert(idx > 0LL);
while (idx <= size) {
tree[idx] += x;
idx += (idx & (-idx));
}
}

// idx is 1 origin
ll sum(ll idx) {
assert(idx > 0LL);
ll ret = 0LL;
while (idx > 0LL) {
ret += tree[idx];
idx -= (idx & (-idx));
}
return ret;
}
};

void llin(ll &a)
{
cin >> a;
}

void llinl1(auto &v, ll count)
{
for (ll i = 0LL; i < count ; ++i) {
ll a;
cin >> a;
v.push_back(a);
}
}

void llinl2(auto &v, ll count)
{
for (ll i = 0LL; i < count ; ++i) {
ll a, b;
cin >> a >> b;
v.push_back(tuple<ll, ll>(a, b));
}
}

void llinl3(auto &v, ll count)
{
for (ll i = 0LL; i < count ; ++i) {
ll a, b, c;
cin >> a >> b >> c;
v.push_back(tuple<ll, ll, ll>(a, b, c));
}
}

void llina(auto &v, ll count)
{
llinl1(v, count);
}

template <typename T>
T min(const V<T> v)
{
T ret = v[0];
for (auto i : v) ret = min(ret, i);
return ret;
}

template <typename T>
T max(const V<T> v)
{
T ret = v[0];
for (auto i : v) ret = max(ret, i);
return ret;
}

ll absll(ll x)
{
if (x < 0) return -x;
return x;
}

ll mod_mlt(ll x, ll y, ll mod)
{
ll ret = 0LL;
x %= mod;

while (y) {
if (y & 1LL) {
ret += x;
ret %= mod;
}
y >>= 1;
x <<= 1;
x %= mod;
}

return ret;
}

ll mod_pow(ll base, ll exp, ll mod)
{
ll ret = 1LL;

for ( ; exp; ) {
if (exp & 1LL) {
ret *= base;
ret %= mod;
}
base = (base * base) % mod;
exp >>= 1;
}

return ret;
}

ll mod_inv(ll x, ll mod)
{
// available only when mod is prime
return mod_pow(x, mod - 2LL, mod);
}

ll gcm(ll x, ll y)
{
while (y != 0) {
ll z = x % y;
x = y;
y = z;
}
return x;
}

template <typename T>
void sort(V<T> &v)
{
sort(v.begin(), v.end());
}

template <typename T>
void sort_reverse(V<T> &v)
{
sort(v.begin(), v.end(), greater<T>());
}

void get_divisors(V<ll> &retlist, ll x)
{
for (ll i = 1LL; i < sqrt(x) + 3LL; ++i) {
if (x % i == 0LL) {
retlist.push_back(i);
retlist.push_back(x / i);
}
}
}

void get_factors(V<ll> &retlist, ll x)
{
for (ll i = 2LL; i < (ll)(sqrt(x)) + 3LL; ++i) {
while (x % i == 0LL) {
retlist.pb(i);
x /= i;
}
}
retlist.pb(x);
}

template <typename T>
void intersection(const set<T> &a, const set<T> &b,
set<T> &result)
{
V<T> resultlist;

set_intersection(a.begin(), a.end(),
b.begin(), b.end(),
back_inserter(resultlist));

set<T> resultset(resultlist.begin(), resultlist.end());
result = resultset;
}

ull combination(ll x, ll y)
{
if (y > x / 2LL) y = x - y;

ull ret = 1LL;
for (ll i = 0LL; i < y; ++i) {
ret *= x--;
ret /= (i + 1LL);
}

return ret;
}

ull mod_combination(ll x, ll y, ll mod)
{
if (y > x / 2LL) y = x - y;

ll ret = 1;

for (ll i = 0LL; i < y; ++i) {
ret = (ret * x--) % mod;
ret = (ret * mod_inv(i + 1LL, mod)) % mod;
}

return ret;
}

void make_linklist(const V<tuple<ll, ll>> &srclist, V<V<ll>> &dstlist)
{
for (auto src : srclist) {
ll a = get<0>(src);
ll b = get<1>(src);
dstlist[a].pb(b);
dstlist[b].pb(a);
}
}

void debug_print(auto xlist)
{
for (auto x : xlist) cout << "-- " << x << endl;
}

int _main();
int main()
{
cout << setprecision(12);
return _main();
}

///////////////////////////////////////////////////////////////////////////////

V<ll> xcounts;
V<ll> ycounts;
M<int, M<ll, bool>> xchecked;
M<int, M<ll, bool>> ychecked;

bool fx(ll goal, ll now, int idx)
{
auto iter = xchecked.find(idx);
if (iter == xchecked.end()) {
xchecked[idx] = M<ll, bool>();
iter = xchecked.find(idx);
}
if (iter->second.find(now) != iter->second.end()) return false;
(iter->second)[now] = true;

if (now == goal) return true;
if (now < goal) return false;
if (idx >= xcounts.size()) return false;

return fx(goal, now, idx + 1) || fx(goal, now - xcounts[idx] * 2, idx + 1);
}

bool fy(ll goal, ll now, int idx)
{
auto iter = ychecked.find(idx);
if (iter == ychecked.end()) {
ychecked[idx] = M<ll, bool>();
iter = ychecked.find(idx);
}
if (iter->second.find(now) != iter->second.end()) return false;
(iter->second)[now] = true;

if (now == goal) return true;
if (now < goal) return false;
if (idx >= ycounts.size()) return false;

return fy(goal, now, idx + 1) || fy(goal, now - ycounts[idx] * 2, idx + 1);
}

int _main()
{
string s;
cin >> s;

ll x, y;
llin(x); llin(y);

ll xplus = 0LL;
char now = 0;

for (auto c : s) {
if (c == 'F') {
if (now == 0) {
xplus++;
}
if (now == 'x') {
xcounts[xcounts.size()-1]++;
}
if (now == 'y') {
ycounts[ycounts.size()-1]++;
}
}
if (c == 'T') {
if (now == 0 || now == 'x') {
now = 'y';
ycounts.pb(0);
}
else if (now == 'y') {
now = 'x';
xcounts.pb(0);
}
}
}

x -= xplus;

V<ll> xcounts_new;
for (auto x : xcounts) if (x != 0) xcounts_new.pb(x);

V<ll> ycounts_new;
for (auto y : ycounts) if (y != 0) ycounts_new.pb(y);

xcounts = xcounts_new;
ycounts = ycounts_new;
sort_reverse(xcounts);
sort_reverse(ycounts);

ll xsum = 0LL;
for (auto count : xcounts) xsum += count;

ll ysum = 0LL;
for (auto count : ycounts) ysum += count;

if (fx(x, xsum, 0) && fy(y, ysum, 0)) cout << "Yes";
else cout << "No";

return 0;
}

///////////////////////////////////////////////////////////////////////////////
```

#### Submission Info

Submission Time 2019-06-18 10:58:43+0900 D - FT Robot mjtai C++14 (GCC 5.4.1) 500 9974 Byte AC 1245 ms 155392 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 0_05.txt
All 500 / 500 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 0_05.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt
Case Name Status Exec Time Memory
0_00.txt 1 ms 256 KB
0_01.txt 1 ms 256 KB
0_02.txt 1 ms 256 KB
0_03.txt 1 ms 256 KB
0_04.txt 1 ms 256 KB
0_05.txt 1 ms 256 KB
1_00.txt 1 ms 256 KB
1_01.txt 1 ms 256 KB
1_02.txt 1 ms 256 KB
1_03.txt 1 ms 256 KB
1_04.txt 1 ms 256 KB
1_05.txt 1 ms 256 KB
1_06.txt 652 ms 87040 KB
1_07.txt 2 ms 384 KB
1_08.txt 2 ms 384 KB
1_09.txt 1238 ms 155264 KB
1_10.txt 1245 ms 155392 KB
1_11.txt 2 ms 384 KB
1_12.txt 177 ms 31872 KB
1_13.txt 73 ms 17664 KB
1_14.txt 604 ms 80768 KB
1_15.txt 4 ms 1280 KB
1_16.txt 501 ms 77568 KB
1_17.txt 194 ms 35840 KB
1_18.txt 166 ms 31744 KB
1_19.txt 2 ms 256 KB
1_20.txt 168 ms 32128 KB
1_21.txt 405 ms 57984 KB
1_22.txt 225 ms 41216 KB
1_23.txt 447 ms 62208 KB
1_24.txt 211 ms 39552 KB
1_25.txt 145 ms 30208 KB
1_26.txt 2 ms 384 KB
1_27.txt 2 ms 384 KB
1_28.txt 2 ms 256 KB
1_29.txt 412 ms 58368 KB
1_30.txt 909 ms 134784 KB
1_31.txt 430 ms 67200 KB
1_32.txt 291 ms 46208 KB
1_33.txt 2 ms 256 KB
1_34.txt 301 ms 52480 KB
1_35.txt 1 ms 256 KB
1_36.txt 1 ms 256 KB
1_37.txt 2 ms 256 KB
1_38.txt 1 ms 256 KB
1_39.txt 1 ms 256 KB
1_40.txt 23 ms 4992 KB
1_41.txt 15 ms 3408 KB
1_42.txt 2 ms 384 KB
1_43.txt 2 ms 384 KB
1_44.txt 3 ms 768 KB
1_45.txt 2 ms 384 KB
1_46.txt 2 ms 256 KB
1_47.txt 2 ms 256 KB
1_48.txt 2 ms 256 KB
1_49.txt 221 ms 38784 KB