Submission #2083917


Source Code Expand

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

#define int long long

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

int H, W, K, sr, sc;
int s[50][50] = {};
int d[50][50] = {};
char ans[4] = {'R', 'D', 'L', 'U'};

unsigned randxor() {
    static unsigned x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned t;
    t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}

int rand_dist(int max) {
    return randxor() % max;
}

void sqcpy(int parent[50][50], int child[50][50]) {
    for (int i = 0; i < 50; i++) {
        for (int j = 0; j < 50; j++) {
            child[i][j] = parent[i][j];
        }
    }
}

int evaluate(int state[50][50], int cd[50][50], int turn, int x, int y) {
    int res = 0;
    for (int i = turn; i < K; i++) {
        res += state[y][x] - i * cd[y][x];
        state[y][x] = 0, cd[y][x] = 0;
        vector<int> way;
        for (int j = 0; j < 4; j++) {
            if (state[y + dy[j]][x + dx[j]] != LLONG_MIN) {
                way.push_back(j);
            }
        }
        int det = rand_dist(way.size());
        x += dx[way[det]], y += dy[way[det]];
    }
    return res;
}

int determine_hand(int state[50][50], int cd[50][50], int turn, int x, int y) {
    int hand;
    int max_score = LLONG_MIN;
    for (int i = 0; i < 4; i++) {
        if (state[y + dy[i]][x + dx[i]] == LLONG_MIN) {
            continue;
        }
        int cur_score = 0;
        for (int i = 0; i < 3; i++) {
            int state_cpy[50][50];
            sqcpy(state, state_cpy);
            int cd_cpy[50][50];
            sqcpy(cd, cd_cpy);
            cur_score += evaluate(state_cpy, cd_cpy, turn, x + dx[i], y + dy[i]);
        }
        if (cur_score > max_score) {
            max_score = cur_score;
            hand = i;
        }
    }
    return hand;
}

signed main() {
    cin >> H >> W >> K >> sr >> sc;
    for (int i = 0; i < 50; i++) {
        string a;
        cin >> a;
        for (int j = 0; j < 50; j++) {
            if (a[j] == '#') {
                s[i][j] = LLONG_MIN;
            }
        }
    }
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        int fr, fc, F, D;
        cin >> fr >> fc >> F >> D;
        s[fr - 1][fc - 1] = F;
        d[fr - 1][fc - 1] = D;
    }
    sr--, sc--;
    for (int i = 0; i < K; i++) {
        int hand = determine_hand(s, d, i, sc, sr);
        cout << ans[hand];
        sc += dx[hand], sr += dy[hand];
        s[sr][sc] = 0, d[sr][sc] = 0;
    }
    cout << endl;
    return 0;
}

Submission Info

Submission Time
Task B - Food Collector
User packer_jp
Language C++14 (GCC 5.4.1)
Score 349
Code Size 2712 Byte
Status RE
Exec Time 5085 ms
Memory 384 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
Score / Max Score 111 / 20000 0 / 20000 0 / 20000 54 / 20000 120 / 20000 14 / 20000 0 / 20000 50 / 20000 0 / 20000 0 / 20000
Status
AC × 1
RE × 1
AC × 1
AC × 1
AC × 1
AC × 1
RE × 1
AC × 1
AC × 1
RE × 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
Case Name Status Exec Time Memory
subtask_01_01.txt AC 4977 ms 384 KB
subtask_01_02.txt RE 3706 ms 256 KB
subtask_01_03.txt AC 4356 ms 256 KB
subtask_01_04.txt AC 4542 ms 384 KB
subtask_01_05.txt AC 5085 ms 256 KB
subtask_01_06.txt AC 4898 ms 256 KB
subtask_01_07.txt RE 1868 ms 256 KB
subtask_01_08.txt AC 4839 ms 256 KB
subtask_01_09.txt AC 4706 ms 384 KB
subtask_01_10.txt RE 315 ms 256 KB