Submission #6009768


Source Code Expand

Copy
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
#include <queue>
#include <map> 
#include <set>
#include <string>
#include <functional>
#include <list>
#include <random>
#include <time.h>
#include <iomanip>
#include <assert.h>
#include <numeric>
#include <iterator>
#include <random>
#include <cassert>
#define int long long
#define double long double
#define oku7 1000000007
#define MAXN (int)1e+5 * 2+1
#define LL_MAX 9223372036854775807	//ない環境用
#define LL_HALFMAX 9223372036854775807 / 2	//ない環境用

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define mp make_pair

using namespace std;

std::mt19937 mt((int)time(0));

int dx[4] = { 0, 1, 0, -1 }; // x軸方向への変位
int dy[4] = { 1, 0, -1, 0 }; // y軸方向への変位

template <typename monoid>
struct segment_tree {
    using M = monoid;
    using T = typename M::value_type;

    std::size_t sz;
    std::vector<T> x;

    segment_tree(std::size_t n = 0) {
        sz = 1;
        while (sz < n) sz *= 2;
        x.assign(sz * 2, M::id());
        initialize();
    }

    template <typename iterator>
    segment_tree(iterator first, iterator last) {
        sz = 1;
        std::size_t n = std::distance(first, last);
        while (sz < n) sz *= 2;
        x.assign(sz * 2, M::id());
        std::copy(first, last, x.begin() + sz);
        initialize();
    }

    void fill(const T &val) {
        std::fill(x.begin() + sz, x.end(), val);
        initialize();
    }

    void initialize() {
        for (int i = (int)sz - 1; i >= 1; --i) {
            x[i] = M::op(x[i * 2 + 0], x[i * 2 + 1]);
        }
    }

    T accumulate(std::size_t l, std::size_t r) const {
        T al = M::id(), ar = M::id();
        for (l += sz, r += sz; l < r; l /= 2, r /= 2) {
            if (l & 1) al = M::op(al, x[l++]);
            if (r & 1) ar = M::op(x[--r], ar);
        }
        return M::op(al, ar);
    }

    void update(std::size_t i, const T &val) {
        x[i += sz] = val;
        while (i > 1) {
            x[i / 2] = M::op(x[i], x[i ^ 1]);
            i /= 2;
        }
    }

    T operator[](std::size_t i) const { return x[sz + i]; }
};

template <typename T>
struct min_monoid {
    using value_type = T;
    static constexpr T id() { return std::numeric_limits<T>::max(); }
    static T op(const T &a, const T &b) { return std::min(a, b); }
};

template <typename T>
struct max_monoid {
    using value_type = T;
    static constexpr value_type id() { return std::numeric_limits<value_type>::min(); }
    static value_type op(const value_type &a, const value_type &b) { return std::max(a, b); }
};

template <typename T>
struct sum_monoid {
    using value_type = T;
    static constexpr value_type id() { return 0; }
    static value_type op(const value_type &a, const value_type &b) { return a + b; }
};

template <typename value_type>
using rmq = segment_tree<min_monoid<value_type>>;

template <typename value_type>
using rsq = segment_tree<sum_monoid<value_type>>;


enum DIR {
    up = 0,
    down = 1,
    right=2,
    left=3
};

class dp {
private:
    bool InnerValues[20000][20000];
public:
    bool Get(int pos,int index) {
        return InnerValues[pos + 10000][index];
    }
    void Set(int pos, int index, bool value) {
        InnerValues[pos + 10000][index] = value;
    }
};

dp dpx;
dp dpy;
//dp[pos][ind][dir]: ind までの命令(shrink済)を消化したとき、posにいられるか?
vector<pair<char, int>> inst;

signed main() {
    string s;
    cin >> s;
    const int len = s.length();
    int x, y;
    cin >> x >> y;

    char now = s[0];
    int cnt = 0, consumed = 0;
    for (auto c : s) {
        if (now != c) {
            inst.push_back(make_pair(now, cnt));
            now = c;
            cnt = 0;
        }
        cnt++;
        consumed++;
        if (consumed == len) {
            inst.push_back(make_pair(now, cnt));
        }
    }

    
  

    //最初はx向き原点
    //dp[pos][ind]: ind までの命令(shrink済)を消化したとき、posにいられるか?
    //1番目の命令だけ特別扱い
    bool isX = true;
    if (inst[0].first == 'F') {
        dpx.Set(inst[0].second, 0, true);
        dpy.Set(0, 0, true);
    }
    else {
        if (inst[0].second % 2 == 1) {
            isX = !isX;
        }
        dpx.Set(0, 0, true);
        dpy.Set(0, 0, true);
    }

    //i番目の命令(shrink 済)まで消化したときにそのx/y座標にその向きでいられるか?
    rep(i, inst.size()) {
        if (i == 0) continue;

        if (inst[i].first == 'T') {
            //回転
            if (inst[i].second % 2 == 1) {
                isX = !isX;
            }

            //j: 座標
            for (int j = -len; j <= len; j++) {
                rep(k, 4) {
                    dpx.Set(j, i, dpx.Get(j, i - 1));
                    dpy.Set(j, i, dpy.Get(j, i - 1));
                }
            }
            continue;
        }

        //j: 座標 全てのX座標とY座標について、今回の更新で居る可能性があるかを調べる
        for (int j = -len; j <= len; j++) {
            if (isX) {
                //i-1 まで消化した時点で今回の命令でこの座標にこれる位置にいるか?
                bool value = dpx.Get(j - inst[i].second, i - 1) || dpx.Get(j + inst[i].second, i - 1);
                dpx.Set(j, i, value);
                //yは動かないのでi-1の時点で居たらOK、いなければNG
                dpy.Set(j, i, dpy.Get(j, i - 1));
            }
            else {
                bool value = dpy.Get(j - inst[i].second, i - 1) || dpy.Get(j + inst[i].second, i - 1);
                dpy.Set(j, i, value);
                dpx.Set(j, i, dpx.Get(j, i - 1));
            }
        }
    }

    int instLen = inst.size();

    if (dpx.Get(x, instLen - 1) && dpy.Get(y, instLen - 1)) {
        cout << "Yes\n";
    }
    else {
        cout << "No\n";
    }

    return 0;
}

Submission Info

Submission Time
Task D - FT Robot
User ymduu
Language C++14 (GCC 5.4.1)
Score 0
Code Size 6617 Byte
Status

Test Cases

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 0 / 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 2 ms 4352 KB
0_01.txt 2 ms 4352 KB
0_02.txt 2 ms 4352 KB
0_03.txt 2 ms 4352 KB
0_04.txt 2 ms 4352 KB
0_05.txt 2 ms 4352 KB
1_00.txt 2 ms 4352 KB
1_01.txt 2 ms 4352 KB
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 2 ms 4352 KB
1_27.txt 2 ms 4352 KB
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