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 |
|
|
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 |