Submission #6966563
Source Code Expand
#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <iomanip>
#include <cmath>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
/*
typedef
tree<
int, // Data type
null_type,
less<int>, // Comparator function for the data type
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
*/
const ll MOD_CONST = 1000000007ll;
ll modSum(ll a, ll b, ll MOD = MOD_CONST) {
return ((a % MOD) + (b % MOD)) % MOD;
}
ll modSubtract(ll a, ll b, ll MOD = MOD_CONST) {
return (((a % MOD) - (b % MOD)) + MOD + MOD) % MOD;
}
ll modProd(ll a, ll b, ll MOD = MOD_CONST) {
return ((a % MOD) * (b % MOD)) % MOD;
}
ll getPowMod(ll x, ll e, ll MOD = MOD_CONST) {
if (e == 0) return 1;
if (e % 2 == 0) {
ll tmp = getPowMod(x, e/2, MOD);
return modProd(tmp, tmp, MOD);
} else {
ll tmp = getPowMod(x, e-1, MOD);
return modProd(tmp, x, MOD);
}
}
ll getPow(ll x, ll e) {
if (e == 0) return 1;
if (e % 2 == 0) {
ll tmp = getPow(x, e/2);
return tmp * tmp;
} else {
ll tmp = getPow(x, e-1);
return tmp * x;
}
}
ll getInverse(ll x, ll MOD = MOD_CONST) {
return getPowMod(x, MOD-2, MOD);
}
bool isEven(ll x) {
ll tmp = ((x % 2) + 2) % 2;
return tmp == 0;
}
ll getSumOfDigitsInBase(ll n, ll b) {
ll ret = 0;
while (n > 0) {
ret += n % b;
n /= b;
}
return ret;
}
vector<int> getKMP(string &s) {
int len = (int)s.size();
vector<int> ret (len, 0);
for (int i = 1 ; i < len ; i++) {
int at = ret[i-1];
while (at > 0 && s[i] != s[at]) {
at = ret[at-1];
}
if (s[i] == s[at]) {
at++;
}
ret[i] = at;
}
return ret;
}
string getSubstring(string &s, int from, int to) {
int l = to-from+1;
if (l <= 0) {
return "";
}
return s.substr(from, l);
}
ll gcd(ll a, ll b, ll & x, ll & y) {
if (a == 0) {
x = 0;
y = 1;
return b;
}
ll x1, y1;
ll d = gcd(b % a, a, x1, y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}
pair<ll, ll> getIntersectingRange(ll a1, ll b1, ll a2, ll b2) {
ll s = max(a1, a2);
ll e = min(b1, b2);
return {s, e};
}
bool isNonEmptyIntersection(ll a1, ll b1, ll a2, ll b2) {
auto p = getIntersectingRange(a1, b1, a2, b2);
return p.first <= p.second;
}
double getPointDistance(double x1, double y1, double x2, double y2) {
double dx = x1-x2;
double dy = y1-y2;
double d = (dx * dx) + (dy * dy);
return sqrt(d);
}
bool isPrime(ll x) {
if (x == 2 || x == 3 || x == 5 || x == 7) return true;
if (x < 10) return false;
ll till = min((ll)sqrt(x) + 1, x-1);
for (ll i = 2 ; i <= till ; i++) {
if (x % i == 0) {
return false;
}
}
return true;
}
const int TREE_SIZE = 1;
ll segTree[TREE_SIZE], lazyTree[TREE_SIZE];
void updateRange(int node, int start, int end, int l, int r, ll val)
{
if(lazyTree[node] != 0)
{
// This node needs to be updated
segTree[node] += (end - start + 1) * lazyTree[node]; // Update it
if(start != end)
{
lazyTree[node*2] += lazyTree[node]; // Mark child as lazyTree
lazyTree[node*2+1] += lazyTree[node]; // Mark child as lazyTree
}
lazyTree[node] = 0; // Reset it
}
if(start > end or start > r or end < l) // Current segment is not within range [l, r]
return;
if(start >= l and end <= r)
{
// Segment is fully within range
segTree[node] += (end - start + 1) * val;
if(start != end)
{
// Not leaf node
lazyTree[node*2] += val;
lazyTree[node*2+1] += val;
}
return;
}
int mid = (start + end) / 2;
updateRange(node*2, start, mid, l, r, val); // Updating left child
updateRange(node*2 + 1, mid + 1, end, l, r, val); // Updating right child
segTree[node] = segTree[node*2] + segTree[node*2+1]; // Updating root with max value
}
ll queryRange(int node, int start, int end, int l, int r)
{
if(start > end or start > r or end < l)
return 0; // Out of range
if(lazyTree[node] != 0)
{
// This node needs to be updated
segTree[node] += (end - start + 1) * lazyTree[node]; // Update it
if(start != end)
{
lazyTree[node*2] += lazyTree[node]; // Mark child as lazyTree
lazyTree[node*2+1] += lazyTree[node]; // Mark child as lazyTree
}
lazyTree[node] = 0; // Reset it
}
if(start >= l and end <= r) // Current segment is totally within range [l, r]
return segTree[node];
int mid = (start + end) / 2;
ll p1 = queryRange(node*2, start, mid, l, r); // Query left child
ll p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
return (p1 + p2);
}
int t_x, t_y;
string ar_s;
void input() {
cin >> ar_s >> t_x >> t_y;
}
void preprocess() {
}
void solve() {
set< pair<pair<int, int>, pair<int, int> > > cur, nxt;
cur.insert({{0, 0}, {1, 0}});
for (auto ch : ar_s) {
/*cerr << "Ch = " << ch << "\n";
for (auto state : cur) {
auto pos = state.first, dir = state.second;
cerr << "Pos = " << pos.first << ", " << pos.second << "\n";
cerr << "Dir = " << dir.first << ", " << dir.second << "\n";
}*/
if (ch == 'T') {
for (auto state : cur) {
auto pos = state.first, dir = state.second;
if (dir.first == 0) {
nxt.insert({pos, {1, 0}});
nxt.insert({pos, {-1, 0}});
} else {
nxt.insert({pos, {0, 1}});
nxt.insert({pos, {0, -1}});
}
}
} else {
for (auto state : cur) {
auto pos = state.first, dir = state.second;
nxt.insert({{pos.first+dir.first, pos.second+dir.second}, dir});
}
}
cur = nxt;
nxt.clear();
}
bool ans = false;
for (auto state : cur) {
auto pos = state.first, dir = state.second;
if (pos.first == t_x && pos.second == t_y) {
ans = true;
break;
}
}
if (ans) {
cout << "Yes";
} else {
cout << "No";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cerr.tie(0);
int T;
// cin >> T;
T = 1;
for (int i = 0 ; i < T ; i++) {
input();
preprocess();
solve();
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - FT Robot |
User |
mjguru |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
6717 Byte |
Status |
TLE |
Exec Time |
2104 ms |
Memory |
19328 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 0_04.txt, 0_05.txt |
All |
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 |
AC |
1 ms |
256 KB |
0_01.txt |
AC |
1 ms |
256 KB |
0_02.txt |
AC |
1 ms |
256 KB |
0_03.txt |
AC |
1 ms |
256 KB |
0_04.txt |
AC |
1 ms |
256 KB |
0_05.txt |
AC |
1 ms |
256 KB |
1_00.txt |
AC |
2 ms |
256 KB |
1_01.txt |
AC |
2 ms |
256 KB |
1_02.txt |
AC |
2 ms |
256 KB |
1_03.txt |
AC |
2 ms |
256 KB |
1_04.txt |
AC |
2 ms |
256 KB |
1_05.txt |
AC |
2 ms |
256 KB |
1_06.txt |
TLE |
2104 ms |
6400 KB |
1_07.txt |
TLE |
2104 ms |
7680 KB |
1_08.txt |
TLE |
2103 ms |
768 KB |
1_09.txt |
TLE |
2103 ms |
768 KB |
1_10.txt |
TLE |
2103 ms |
768 KB |
1_11.txt |
TLE |
2103 ms |
768 KB |
1_12.txt |
TLE |
2104 ms |
5248 KB |
1_13.txt |
TLE |
2104 ms |
5248 KB |
1_14.txt |
TLE |
2103 ms |
640 KB |
1_15.txt |
TLE |
2103 ms |
640 KB |
1_16.txt |
TLE |
2103 ms |
640 KB |
1_17.txt |
TLE |
2103 ms |
640 KB |
1_18.txt |
TLE |
2104 ms |
6016 KB |
1_19.txt |
TLE |
2104 ms |
6400 KB |
1_20.txt |
TLE |
2103 ms |
7652 KB |
1_21.txt |
TLE |
2104 ms |
6144 KB |
1_22.txt |
TLE |
2104 ms |
6784 KB |
1_23.txt |
TLE |
2104 ms |
5888 KB |
1_24.txt |
TLE |
2104 ms |
5888 KB |
1_25.txt |
TLE |
2104 ms |
6656 KB |
1_26.txt |
AC |
2 ms |
256 KB |
1_27.txt |
AC |
2 ms |
256 KB |
1_28.txt |
TLE |
2104 ms |
6400 KB |
1_29.txt |
TLE |
2104 ms |
6272 KB |
1_30.txt |
TLE |
2104 ms |
8960 KB |
1_31.txt |
TLE |
2104 ms |
9088 KB |
1_32.txt |
TLE |
2104 ms |
9856 KB |
1_33.txt |
TLE |
2104 ms |
10496 KB |
1_34.txt |
TLE |
2104 ms |
12928 KB |
1_35.txt |
TLE |
2104 ms |
11392 KB |
1_36.txt |
TLE |
2104 ms |
16384 KB |
1_37.txt |
TLE |
2104 ms |
12160 KB |
1_38.txt |
TLE |
2104 ms |
3968 KB |
1_39.txt |
TLE |
2104 ms |
13056 KB |
1_40.txt |
TLE |
2103 ms |
9812 KB |
1_41.txt |
TLE |
2104 ms |
17024 KB |
1_42.txt |
TLE |
2104 ms |
8448 KB |
1_43.txt |
TLE |
2104 ms |
6400 KB |
1_44.txt |
TLE |
2104 ms |
19328 KB |
1_45.txt |
TLE |
2104 ms |
13440 KB |
1_46.txt |
TLE |
2103 ms |
2688 KB |
1_47.txt |
TLE |
2104 ms |
10240 KB |
1_48.txt |
TLE |
2104 ms |
6400 KB |
1_49.txt |
TLE |
2104 ms |
13568 KB |