Submission #1174244


Source Code Expand

#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

struct State {
    int turn;
    int dist;
    int x[450];
    int y[450];
    
    double get_score() {
        return 1e7 / (dist * (10 + turn * 0.01));
    }
};

int H, W, K, T;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
char direction[5] = "RDLU";
int dest_x[450];
int dest_y[450];
bool used[30][30];

void solve(State &state) {
    int i, j, k, l;
    double best_score = state.get_score();
    vector <string> ans;
    vector <int> order;
    
    for (i = 0; i < K; i++) order.push_back(i);
    
    for (i = 0; i < T; i++) {
        double next_score = best_score;
        State next_state;
        string next_movement;
        
        int loop;
        if (i < 20) {
            loop = 500;
        } else {
            loop = 10;
        }
        
        for (j = 0; j < loop; j++) {
            random_shuffle(order.begin(), order.end());
            
            for (k = 0; k < H; k++) {
                for (l = 0; l < W; l++) {
                    used[k][l] = false;
                }
            }
            
            for (k = 0; k < K; k++) used[state.x[k]][state.y[k]] = true;
            
            int move_dist = 0;
            string movement = string(K, '-');
            
            for (k = 0; k < K; k++) {
                int pos = order[k];
                
                for (l = 0; l < 4; l++) {
                    int x = state.x[pos];
                    int y = state.y[pos];
                    int nx = x + dx[l];
                    int ny = y + dy[l];
                    
                    if (nx < 0 || nx >= H || ny < 0 || ny >= W || used[nx][ny] == true) continue;
                    
                    if (abs(x - dest_x[pos]) + abs(y - dest_y[pos]) > abs(nx - dest_x[pos]) + abs(ny - dest_y[pos])) {
                        used[nx][ny] = true;
                        state.x[pos] = nx;
                        state.y[pos] = ny;
                        move_dist++;
                        movement[pos] = direction[l];
                        
                        break;
                    }
                }
            }
            
            state.turn++;
            state.dist -= move_dist;
            
            double score = state.get_score();
            if (score > next_score) {
                next_score = score;
                next_state = state;
                next_movement = movement;
            }
            
            state.turn--;
            state.dist += move_dist;
            
            for (k = 0; k < K; k++) {
                if (movement[k] == '-') continue;
                if (movement[k] == 'R') {
                    state.y[k]--;
                } else if (movement[k] == 'D') {
                    state.x[k]--;
                } else if (movement[k] == 'L') {
                    state.y[k]++;
                } else {
                    state.x[k]++;
                }
            }
        }
        
        if (next_score > best_score) {
            best_score = next_score;
            state = next_state;
            ans.push_back(next_movement);
        }
    }
    
    printf("%d\n", ans.size());
    for (i = 0; i < ans.size(); i++) printf("%s\n", ans[i].c_str());
}

int main() {
    int i;
    
    scanf("%d %d %d %d", &H, &W, &K, &T);
    
    State state;
    state.turn = 0;
    state.dist = 20;
    
    for (i = 0; i < K; i++) {
        int a, b, c, d;
        
        scanf("%d %d %d %d", &a, &b, &c, &d);
        
        a--;
        b--;
        c--;
        d--;
        
        state.x[i] = a;
        state.y[i] = b;
        
        dest_x[i] = c;
        dest_y[i] = d;
        
        state.dist += abs(a - c) + abs(b - d);
    }
    
    solve(state);
    
    return 0;
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User kawatea
Language C++14 (GCC 5.4.1)
Score 4711
Code Size 3990 Byte
Status AC
Exec Time 2455 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘void solve(State&)’:
./Main.cpp:118:30: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘std::vector<std::basic_string<char> >::size_type {aka long unsigned int}’ [-Wformat=]
     printf("%d\n", ans.size());
                              ^
./Main.cpp: In function ‘int main()’:
./Main.cpp:125:41: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &H, &W, &K, &T);
                                         ^
./Main.cpp:134:45: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &a, &b, &c, &d);
                                             ^

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 164 / 50000 160 / 50000 163 / 50000 163 / 50000 178 / 50000 154 / 50000 157 / 50000 169 / 50000 151 / 50000 156 / 50000 162 / 50000 156 / 50000 154 / 50000 167 / 50000 149 / 50000 167 / 50000 154 / 50000 149 / 50000 154 / 50000 150 / 50000 164 / 50000 152 / 50000 153 / 50000 149 / 50000 148 / 50000 161 / 50000 156 / 50000 144 / 50000 156 / 50000 151 / 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 2367 ms 256 KB
subtask_01_02.txt AC 2349 ms 256 KB
subtask_01_03.txt AC 2336 ms 256 KB
subtask_01_04.txt AC 2347 ms 256 KB
subtask_01_05.txt AC 2423 ms 256 KB
subtask_01_06.txt AC 2355 ms 256 KB
subtask_01_07.txt AC 2328 ms 256 KB
subtask_01_08.txt AC 2344 ms 256 KB
subtask_01_09.txt AC 2339 ms 256 KB
subtask_01_10.txt AC 2391 ms 256 KB
subtask_01_11.txt AC 2348 ms 256 KB
subtask_01_12.txt AC 2324 ms 256 KB
subtask_01_13.txt AC 2316 ms 256 KB
subtask_01_14.txt AC 2419 ms 256 KB
subtask_01_15.txt AC 2313 ms 256 KB
subtask_01_16.txt AC 2455 ms 256 KB
subtask_01_17.txt AC 2293 ms 256 KB
subtask_01_18.txt AC 2337 ms 256 KB
subtask_01_19.txt AC 2278 ms 256 KB
subtask_01_20.txt AC 2320 ms 256 KB
subtask_01_21.txt AC 2358 ms 256 KB
subtask_01_22.txt AC 2314 ms 256 KB
subtask_01_23.txt AC 2237 ms 256 KB
subtask_01_24.txt AC 2275 ms 256 KB
subtask_01_25.txt AC 2375 ms 256 KB
subtask_01_26.txt AC 2357 ms 256 KB
subtask_01_27.txt AC 2340 ms 256 KB
subtask_01_28.txt AC 2294 ms 256 KB
subtask_01_29.txt AC 2380 ms 256 KB
subtask_01_30.txt AC 2295 ms 256 KB