Submission #3830047


Source Code Expand

#include <cstdlib>
#include <chrono>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
using namespace std;
#define X 50
#define Y 50
#define K 2500
struct food {
    int initial_value;
    int dec_rate;
    food(int _f, int _d) { initial_value = _f; dec_rate = _d; }
    food() { initial_value = 0; dec_rate = 0; }
};
food F[X][Y];

char dir[X][Y];
bool visited[X][Y];
string dirs = "UDLR";
const int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
int arr_time[X][Y], score[X][Y];
int adj[X][Y];
bool allow_minus = true;

struct state { char x, y; int sum; };

state calc(char x, char y, int t, int t_limit, double e) {
    memset(visited, 0, sizeof(visited));
    memset(dir, 0, sizeof(dir));
    memset(arr_time, 0, sizeof(arr_time));
    memset(score, 0, sizeof(score));
    queue<state> q;
    q.push((state){x, y, 0});
    arr_time[x][y] = t;
    visited[x][y] = true;
    double max_avg = 0.0;
    state best = {-1, -1, 0};
    while (!q.empty()) {
        x = q.front().x, y = q.front().y;
        int sum = q.front().sum;
        q.pop();
        if (arr_time[x][y] == t_limit) continue;
        int max_score = 0, max_dir = -1;
        for (int k = 0; k < 4; k++) {
            if ((adj[x][y] & (1 << k)) == 0) continue;
            char x1 = x + dx[k], y1 = y + dy[k];
            if (visited[x1][y1]) continue;
            int t1 = arr_time[x][y] + 1;
            int val = F[x1][y1].initial_value - F[x1][y1].dec_rate * (t1 - 1);
            if (!allow_minus && val < 0) continue;
            int score1 = score[x][y] + val;
            score[x1][y1] = score1;
            arr_time[x1][y1] = t1;
            visited[x1][y1] = true;
            dir[x1][y1] = dirs[k];
            q.push((state){x1, y1, score1});
            assert (arr_time[x1][y1] > t);
            double avg = (double)score1/pow(t1 - t, e);
            if (max_avg < avg) {
                max_avg = avg;
                best = (state){x1, y1, score[x1][y1]};
            }
        }
    }
    return best;
}

int main(int argc, char** argv) {
    auto start = chrono::system_clock::now();
    int h, w, k, sx, sy; cin >> h >> w >> k >> sx >> sy;
    sx--; sy--;
    assert(h == X);
    assert(w == Y);
    assert(k == K);
    string s[X];
    for (int i = 0; i < X; i++) cin >> s[i];
    for (int x = 0; x < X; x++)
        for (int y = 0; y < Y; y++)
            for (int k = 0; k < 4; k++) {
                int x1 = x + dx[k], y1 = y + dy[k];
                if (0 <= x1 && x1 < X && 0 <= y1 && y1 < Y && s[x1][y1] == '.')
                    adj[x][y] |= 1<<k;
            }
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y, f, d; cin >> x >> y >> f >> d;
        x--; y--;
        F[x][y] = food(f, d);
    }

    int best_score = 0, iter = 1, dur = 0, margin = 5, timelimit = 10000;
    if (argc > 1) timelimit = atoi(argv[1]);
    string best_seq;
    while ((double)dur * (iter + 1) / iter + margin < timelimit) {
        int t = 0, x = sx, y = sy, cur_score = 0;
        char buf[K+1];
        food F_save[X][Y];
        memcpy(F_save, F, sizeof(F));
        // parameters
        allow_minus = true;
        double exponent = 0.1 * iter;
        while (t < K) {
            state st = calc(x, y, t, K, exponent);
            if (st.sum == 0) {
                if (allow_minus) {
                    allow_minus = false;
                    continue;
                } else {
                    while (t < K) buf[t++] = '-';
                    break;
                }
            }
            // cout << "from " << x << ' ' << y << " to " << (int)st.x << ' ' << (int)st.y << endl;
            for (int x0 = st.x, y0 = st.y, t0 = arr_time[x0][y0]-1; t <= t0; t0--) {
                assert(x0 != x || y0 != y);
                buf[t0] = dir[x0][y0];
                switch (dir[x0][y0]) {
                case 'L': y0++; break;
                case 'R': y0--; break;
                case 'U': x0++; break;
                case 'D': x0--; break;
                default: assert(false);
                }
                F[x0][y0] = {0, 0};
                // cout << t0 << ' ' << x0 << ' ' << y0 << endl;
            }
            //cout << endl;
            x = st.x; y = st.y; t = arr_time[x][y];
            cur_score += st.sum;
        }
        assert (t == K);
        buf[K] = '\0';
        if (cur_score > best_score) {
            best_score = cur_score;
            best_seq = string(buf);
            // cerr << iter << ' ' << best_score << endl;
        }
        iter++;
        memcpy(F, F_save, sizeof(F));
        dur = chrono::duration_cast<std::chrono::milliseconds>(chrono::system_clock::now() - start).count();
    }
    puts(best_seq.c_str());
    // cerr << iter << ", " << best_score << endl;
    return 0;
}

Submission Info

Submission Time
Task B - Food Collector
User kozima
Language C++14 (GCC 5.4.1)
Score 19502
Code Size 4956 Byte
Status AC
Exec Time 9996 ms
Memory 768 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 1876 / 20000 2653 / 20000 2036 / 20000 1117 / 20000 2019 / 20000 2517 / 20000 2121 / 20000 1655 / 20000 1184 / 20000 2324 / 20000
Status
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
Case Name Status Exec Time Memory
subtask_01_01.txt AC 9963 ms 768 KB
subtask_01_02.txt AC 9983 ms 384 KB
subtask_01_03.txt AC 9956 ms 384 KB
subtask_01_04.txt AC 9989 ms 384 KB
subtask_01_05.txt AC 9985 ms 384 KB
subtask_01_06.txt AC 9949 ms 384 KB
subtask_01_07.txt AC 9961 ms 384 KB
subtask_01_08.txt AC 9995 ms 384 KB
subtask_01_09.txt AC 9996 ms 384 KB
subtask_01_10.txt AC 9994 ms 384 KB