QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61068#3832. Robert FloydNYCU_Yamada#AC ✓7ms3708kbC++20949b2022-11-09 19:43:302022-11-09 19:43:33

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-09 19:43:33]
  • Judged
  • Verdict: AC
  • Time: 7ms
  • Memory: 3708kb
  • [2022-11-09 19:43:30]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#ifdef local
#define fastIO() void()
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#endif

using pii = pair<int, int>;

#define SZ(x) (x).size()

int mx[128], my[128];


void solve() {
    string s; cin >> s;
    int nx, ny, x = 0, y = 0;
    set<pii> pt; 
    pt.insert({0, 0});
    set<pair<pii, pii>> edge;
    for(char c : s) {
        nx = x + mx[c];
        ny = y + my[c];
        pt.insert({nx, ny});
        pii A = make_pair(x, y);
        pii B = make_pair(nx, ny);
        if(A > B) swap(A, B);
        edge.insert({A, B});
        x = nx; y = ny;
    }
    // cout << SZ(edge) << ' ' << SZ(pt) << '\n';
    cout << (SZ(edge) - SZ(pt) + 2) << '\n'; 
}

int32_t main() {
    fastIO();
    mx['L'] = -1;
    mx['R'] = 1;
    my['U'] = 1;
    my['D'] = -1;
    int t = 1; cin >> t;
    while (t--) solve();
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 3708kb

input:

30
URDR
URDRDLDR
URDRDLDRDLULDLDR
URDRDLDRDLULDLDRDLULURULDLULDLDR
URDRDLDRDLULDLDRDLULURULDLULDLDRDLULURULURDRURULDLULURULDLULDLDR
URDRDLDRDLULDLDRDLULURULDLULDLDRDLULURULURDRURULDLULURULDLULDLDRDLULURULURDRURULURDRDLDRURDRURULDLULURULURDRURULDLULURULDLULDLDR
URDRDLDRDLULDLDRDLULURULDLULDLDRDLULURU...

output:

1
1
2
5
12
29
68
153
336
725
331
235
333
213
357
249
322
229
342
230
348
231
328
225
366
513
2
2
2
3

result:

ok 30 lines