Submission #1178167


Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <stdio.h>
#include <string.h>
using namespace std;

struct Range {
    bool operator<(const Range& t) const {
        return y != t.y ? y < t.y : l < t.l;
    }
    int y, l, r;
};

int main() {
    int k;
    string s;
    cin >> k >> s;

    int u[256];
    for (int i = 0; i < 4; i++) u["LRDU"[i]] = i;

    set<Range> r[2];
    for (int j = 0; j < 2; j++) r[j].insert({ -k, -k, -k });
    int x = 0, y = 0;

    for (int i = 0; i < k; i++) {
        int x1 = x, y1 = y;
        for (int j = 0; j < 2; j++) {
            set<Range>::iterator tl, tr;
            tl = tr = r[j].upper_bound({ y, x, 0 });
            if (tl != r[j].begin()) tl--; else tl = r[j].end();
            bool bl = tl != r[j].end() && tl->y == y && tl->r == x - 1;
            bool br = tr != r[j].end() && tr->y == y && tr->l == x + 1;
            Range tt;
            if (bl && br) {
                (tt = *tl).r = tr->r;
                r[j].erase(tl);
                r[j].erase(tr);
                r[j].insert(tt);
            } else if (bl) {
                (tt = *tl).r++;
                r[j].erase(tl);
                r[j].insert(tt);
            } else if (br) {
                (tt = *tr).l--;
                r[j].erase(tr);
                r[j].insert(tt);
            } else {
                tt = *r[j].insert({ y, x, x }).first;
            }
            int v = u[s[i]] - j * 2;
            if (0 <= v && v < 2) {
                x1 = v == 0 ? tt.l - 1 : tt.r + 1;
            }
            swap(x, y);
            swap(x1, y1);
        }
        x = x1; y = y1;
    }

    cout << x << ' ' << y << endl;

    return 0;
}

Submission Info

Submission Time
Task C - 幼稚園児高橋君
User merom686
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1788 Byte
Status AC
Exec Time 227 ms
Memory 12932 KB

Judge Result

Set Name Sample Subtask1
Score / Max Score 0 / 0 100 / 100
Status
AC × 3
AC × 24
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 AC 1 ms 256 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt AC 1 ms 256 KB
subtask1_06.txt AC 1 ms 256 KB
subtask1_07.txt AC 105 ms 2692 KB
subtask1_08.txt AC 105 ms 2692 KB
subtask1_09.txt AC 107 ms 2308 KB
subtask1_10.txt AC 105 ms 3076 KB
subtask1_11.txt AC 106 ms 2436 KB
subtask1_12.txt AC 106 ms 2308 KB
subtask1_13.txt AC 106 ms 2564 KB
subtask1_14.txt AC 168 ms 12932 KB
subtask1_15.txt AC 170 ms 12932 KB
subtask1_16.txt AC 227 ms 6660 KB
subtask1_17.txt AC 70 ms 12932 KB
subtask1_18.txt AC 172 ms 12932 KB
subtask1_19.txt AC 97 ms 7300 KB
subtask1_20.txt AC 83 ms 7044 KB
subtask1_21.txt AC 144 ms 6660 KB