Submission #1174191


Source Code Expand

#define DINGER_GISBAR
#include <bits/stdc++.h>
using namespace std;
const long long MOD = static_cast<int>(1e9) + 7;
//{{{TEMPLATE_BEGIN
#include <unistd.h>
using namespace std::rel_ops;
#ifdef ZEROKUGI
#include <dumper.hpp>
#define dump(x) dumper::dumper(cerr, __LINE__, (#x), (x), 50, 1, 1)
#define tick(...) dumper::tick(__VA_ARGS__)
#pragma message "Compiling " __FILE__
#else
#define dump(x)
#define tick(...)
#endif
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;
typedef vector<int> vint;
#define rep(i, n) \
    for (int i = 0, i##_len = static_cast<int>(n); i < i##_len; i++)
#define all(c) begin(c), end(c)
#define perm(c)   \
    sort(all(c)); \
    for (bool c##p = 1; c##p; c##p = next_permutation(all(c)))
#define uniquenize(v) (v).erase(unique(all(v)), end(v))
#define cauto const auto&
#define memset(x, y) memset(x, y, sizeof(x))
#define popcount __builtin_popcount
#define gcd __gcd
inline lint bit(int x) { return 1LL << x; }
template <class T>
inline int size(const T& a) {
    return (int)a.size();
}
template <class T>
inline bool chmin(T& a, const T& b) {
    return a > b ? a = b, 1 : 0;
}
template <class T>
inline int clamp(T v, T lo, T hi) {
    return (v > hi) - (v < lo);
}
template <class T>
inline bool chmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0;
}
template <class T>
inline pair<vector<T>, char> operator*(const vector<T>& v, const char& c) {
    return make_pair(v, c);
}
template <class T>
inline istream& operator>>(istream& is, vector<T>& v) {
#ifdef ZEROKUGI
    if (v.empty()) {
        cerr << "Error L" << __LINE__ << ": vector size is zero." << endl;
        exit(EXIT_FAILURE);
    }
#endif
    for (auto& x : v) is >> x;
    return is;
}
template <class T>
inline ostream& operator<<(ostream& os, const pair<vector<T>, char>& v) {
    bool t = 0;
    for (const T& x : v.first) {
        if (t) os << v.second;
        os << x;
        t = 1;
    }
    return os;
}
template <class T>
inline ostream& operator<<(ostream& os, vector<T>& v) {
    return os << v * ' ';
}
struct before_main {
    before_main() {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(20);
        tick(0, 0);
    };
} __before_main;
//}}}TEMPLATE_END

int h, w, k, t;
int a[555], b[555], c[555], d[555], e[555], f[555];

bool field[50][50];
bool nxt[50][50];

vector<char> mov[555];

bool ok(int y, int x) {
    if (y < 0 || y >= 30) return false;
    if (x < 0 || x >= 30) return false;
    return !field[y][x] && !nxt[y][x];
}

vector<int> vvvvvv() {
    vector<int> v(450);
    iota(all(v), 0);
    random_shuffle(all(v));
    return v;
}

void tate() {
    memset(nxt, 0);
    memset(field, 0);

    rep(i, k) field[a[i]][b[i]] = true;
    rep(i, k) {
        int dy;
        if (a[i] < e[i]) {
            dy = 1;
        } else if (a[i] > e[i]) {
            dy = -1;
        } else {
            dy = 0;
        }

        if (!ok(a[i] + dy, b[i])) dy = 0;
        a[i] += dy;
        nxt[a[i]][b[i]] = true;

        char c;
        if (dy == 1) {
            c = 'D';
        } else if (dy == 0) {
            c = '-';
        } else {
            c = 'U';
        }
        mov[i].push_back(c);
    }
}

void yoko() {
    memset(nxt, 0);
    memset(field, 0);

    rep(i, k) field[a[i]][b[i]] = true;

    for(int i: vvvvvv()){
        int dx;
        if (b[i] < f[i]) {
            dx = 1;
        } else if (b[i] > f[i]) {
            dx = -1;
        } else {
            dx = 0;
        }

        if (!ok(a[i], b[i] + dx)) dx = 0;
        b[i] += dx;
        nxt[a[i]][b[i]] = true;

        char c;
        if (dx == 1) {
            c = 'R';
        } else if (dx == 0) {
            c = '-';
        } else {
            c = 'L';
        }
        mov[i].push_back(c);
    }
}

int dya[] = {0, 1, 0, -1};
int dxa[] = {1, 0, -1, 0};

void aaaa() {
    memset(nxt, 0);
    memset(field, 0);

    rep(i, k) field[a[i]][b[i]] = true;

    for (int i : vvvvvv()) {
        int dir = rand() % 4;

        int dy = dya[dir];
        int dx = dxa[dir];

        if (!ok(a[i] + dy, b[i] + dx)) {
            dx = 0;
            dy = 0;
        }

        b[i] += dx;
        a[i] += dy;

        nxt[a[i]][b[i]] = true;

        char c;
        if (dy == 1) {
            c = 'D';
        } else if (dy == -1) {
            c = 'U';
        } else if (dx == 1) {
            c = 'R';
        } else if (dx == -1) {
            c = 'L';
        } else {
            c = '-';
        }
        mov[i].push_back(c);
    }
}

void bbbb() {
    memset(nxt, 0);
    memset(field, 0);

    rep(i, k) field[a[i]][b[i]] = true;

    rep(i, k) {
        int dir = rand() % 4;

        int dy = dya[dir];
        int dx = dxa[dir];

        if (!ok(a[i] + dy, b[i] + dx)) {
            dx = 0;
            dy = 0;
        }

        b[i] += dx;
        a[i] += dy;

        nxt[a[i]][b[i]] = true;

        char c;
        if (dy == 1) {
            c = 'D';
        } else if (dy == -1) {
            c = 'U';
        } else if (dx == 1) {
            c = 'R';
        } else if (dx == -1) {
            c = 'L';
        } else {
            c = '-';
        }
        mov[i].push_back(c);
    }
}
int main() {
    cin >> h >> w >> k >> t;
    rep(i, k) cin >> a[i] >> b[i] >> c[i] >> d[i];
    rep(i, k) {
        a[i]--;
        b[i]--;
        c[i]--;
        d[i]--;
        field[a[i]][b[i]] = true;
    }

    rep(aaa, 100) {
        // random
        rep(i, 3) aaaa();

        // tate
        rep(i, k) {
            f[i] = d[i];
            if (b[i] / 3 < d[i] / 3) {
                e[i] = a[i] / 6 * 6 + rand() % 2;
            } else if (b[i] / 3 > d[i] / 3) {
                e[i] = a[i] / 6 * 6 + 2 + rand() % 2;
            } else {
                e[i] = a[i] / 6 * 6 + 4 + rand() % 2;
            }
        }

        rep(_, 3) { tate(); }

        rep(_, 3) { yoko(); }

        // yoko
        rep(i, k) {
            e[i] = c[i];
            if (a[i] / 3 < c[i] / 3) {
                f[i] = b[i] / 6 * 6 + rand() % 2;
            } else if (a[i] / 3 > c[i] / 3) {
                f[i] = b[i] / 6 * 6 + 2 + rand() % 2;
            } else {
                f[i] = b[i] / 6 * 6 + 4 + rand() % 2;
            }
        }

        rep(_, 3) { yoko(); }

        rep(_, 3) { tate(); }
    }

    int len = mov[0].size();
    cout << len << endl;

    rep(i, len) {
        rep(j, k) { cout << mov[j][i]; }
        cout << endl;
    }
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User eha
Language C++14 (GCC 5.4.1)
Score 6622
Code Size 6769 Byte
Status AC
Exec Time 42 ms
Memory 1920 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10 test_11 test_12 test_13 test_14 test_15 test_16 test_17 test_18 test_19 test_20 test_21 test_22 test_23 test_24 test_25 test_26 test_27 test_28 test_29 test_30
Score / Max Score 212 / 50000 251 / 50000 258 / 50000 229 / 50000 236 / 50000 231 / 50000 206 / 50000 248 / 50000 241 / 50000 242 / 50000 228 / 50000 206 / 50000 214 / 50000 206 / 50000 211 / 50000 204 / 50000 213 / 50000 166 / 50000 183 / 50000 243 / 50000 164 / 50000 221 / 50000 197 / 50000 202 / 50000 210 / 50000 235 / 50000 231 / 50000 262 / 50000 218 / 50000 254 / 50000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
test_11 subtask_01_11.txt
test_12 subtask_01_12.txt
test_13 subtask_01_13.txt
test_14 subtask_01_14.txt
test_15 subtask_01_15.txt
test_16 subtask_01_16.txt
test_17 subtask_01_17.txt
test_18 subtask_01_18.txt
test_19 subtask_01_19.txt
test_20 subtask_01_20.txt
test_21 subtask_01_21.txt
test_22 subtask_01_22.txt
test_23 subtask_01_23.txt
test_24 subtask_01_24.txt
test_25 subtask_01_25.txt
test_26 subtask_01_26.txt
test_27 subtask_01_27.txt
test_28 subtask_01_28.txt
test_29 subtask_01_29.txt
test_30 subtask_01_30.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 41 ms 1920 KB
subtask_01_02.txt AC 41 ms 1920 KB
subtask_01_03.txt AC 41 ms 1920 KB
subtask_01_04.txt AC 41 ms 1920 KB
subtask_01_05.txt AC 41 ms 1920 KB
subtask_01_06.txt AC 41 ms 1920 KB
subtask_01_07.txt AC 41 ms 1920 KB
subtask_01_08.txt AC 41 ms 1920 KB
subtask_01_09.txt AC 41 ms 1920 KB
subtask_01_10.txt AC 41 ms 1920 KB
subtask_01_11.txt AC 41 ms 1920 KB
subtask_01_12.txt AC 42 ms 1920 KB
subtask_01_13.txt AC 42 ms 1920 KB
subtask_01_14.txt AC 41 ms 1920 KB
subtask_01_15.txt AC 41 ms 1920 KB
subtask_01_16.txt AC 41 ms 1920 KB
subtask_01_17.txt AC 41 ms 1920 KB
subtask_01_18.txt AC 41 ms 1920 KB
subtask_01_19.txt AC 41 ms 1920 KB
subtask_01_20.txt AC 41 ms 1920 KB
subtask_01_21.txt AC 41 ms 1920 KB
subtask_01_22.txt AC 42 ms 1920 KB
subtask_01_23.txt AC 41 ms 1920 KB
subtask_01_24.txt AC 41 ms 1920 KB
subtask_01_25.txt AC 41 ms 1920 KB
subtask_01_26.txt AC 41 ms 1920 KB
subtask_01_27.txt AC 41 ms 1920 KB
subtask_01_28.txt AC 41 ms 1920 KB
subtask_01_29.txt AC 41 ms 1920 KB
subtask_01_30.txt AC 41 ms 1920 KB