Submission #1604839


Source Code Expand

#include <bits/stdc++.h>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;

int dx[] = {0, -1, 0, 1};
int dy[] = {-1, 0, 1, 0};

// #define DEBUG_MODE
#ifdef DEBUG_MODE
#define dump(x) cerr << #x << " : " << x << endl
#define LINE cerr << "line : " << __LINE__ << endl
#define dumpV(v) cerr << #v << " : ["; for(auto& t : v) cerr << t << ", "; cerr<<"]" << endl
#define STOP assert(false)
#else
#define dump(x) 
#define LINE     
#define dumpV(v)
#define STOP     
#endif
#define mkp make_pair

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fi<<", "<<a.se<<')';
    return out;
  }
}


int main(){
#ifdef LOCAL_TEST
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int k;
    string s;
    cin >> k >> s;
    pii now = make_pair(0, 0);
    map<char, int> dir;
    dir['D'] = 0;
    dir['L'] = 1;
    dir['U'] = 2;
    dir['R'] = 3;
    map<pii, array<pii, 4>> mp;
    array<pii, 4> ar;
    rep(i, 4) ar[i] = make_pair(dx[i], dy[i]);
    mp[now] = ar;
    LINE;
    rep(i, k) {
        auto& tmp = mp[now];
        auto nxt = tmp[dir[s[i]]];
        // cerr << nxt.fi << " " << nxt.se << endl;
        dump(mkp(now, nxt));
        array<pii, 4> nxtAr;
        rep(j, 4) {
            int nx = nxt.fi + dx[j], ny = nxt.se + dy[j];
            if(mp.count(make_pair(nx, ny))) {
                nxtAr[j] = mp[make_pair(nx, ny)][j];
            }
            else {
                nxtAr[j] = make_pair(nx, ny);
            }
            auto p = make_pair(tmp[(j+2)%4].fi + dx[j], tmp[(j+2)%4].se + dy[j]);
            if(p == now) continue;
            if(mp.count(p)) {
                mp[p][j] = tmp[j];
                dump(mkp(p, mp[p][j]));
            }
        }
        mp[nxt] = nxtAr;
        tmp[dir[s[i]]] = nxtAr[dir[s[i]]];
        now = nxt;
    }
    cout << now.fi << " " << now.se << endl;
    return 0;
}

Submission Info

Submission Time
Task C - 幼稚園児高橋君
User T1610
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2488 Byte
Status WA
Exec Time 446 ms
Memory 16132 KB

Judge Result

Set Name Sample Subtask1
Score / Max Score 0 / 0 0 / 100
Status
AC × 3
AC × 12
WA × 12
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
Subtask1 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 1 ms 256 KB
subtask0_sample_02.txt AC 1 ms 256 KB
subtask0_sample_03.txt AC 1 ms 256 KB
subtask1_01.txt AC 1 ms 256 KB
subtask1_02.txt WA 1 ms 256 KB
subtask1_03.txt WA 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt WA 1 ms 256 KB
subtask1_06.txt WA 1 ms 256 KB
subtask1_07.txt WA 268 ms 11396 KB
subtask1_08.txt WA 266 ms 11524 KB
subtask1_09.txt WA 266 ms 11652 KB
subtask1_10.txt WA 251 ms 12036 KB
subtask1_11.txt WA 261 ms 11780 KB
subtask1_12.txt WA 253 ms 11780 KB
subtask1_13.txt WA 283 ms 10884 KB
subtask1_14.txt AC 332 ms 16132 KB
subtask1_15.txt AC 362 ms 16004 KB
subtask1_16.txt AC 446 ms 16132 KB
subtask1_17.txt WA 109 ms 10244 KB
subtask1_18.txt AC 423 ms 16004 KB
subtask1_19.txt AC 225 ms 16004 KB
subtask1_20.txt AC 210 ms 16004 KB
subtask1_21.txt AC 402 ms 16132 KB