Submission #1173887


Source Code Expand

#include <iostream>
#include <sstream>
#include <string>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <tuple>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

typedef pair<int, int> P;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

struct State {
    // (h, w)
    vector<pair<int,int>> locs;
    vector<pair<int,int>> goals;
    vector<vector<char>> cells;
};
State s;
int H, W, K, T;
vector<int> shff;


bool is_out_of_range(int h2, int w2) {
    return (h2 < 1 || h2 > H ||  w2 < 1 || w2 > W);
}

P move_result(P& before, P& diff) {
    P after;
    after.first = before.first + diff.first;
    after.second = before.second + diff.second;
    return after;
}

void update_cells() {
    // 1-based
    s.cells.resize(H+1, vector<char>(W+1));
    for(auto p: s.locs) {
        auto h = p.first;
        auto w = p.second;
        s.cells[h][w] = 1;
    }
}

char move_to_char(const pair<int,int>& p) {
    if (p == mp(0, 0)) return '-';
    else if (p == mp(1, 0)) return 'D';
    else if (p == mp(-1, 0)) return 'U';
    else if (p == mp(0, 1)) return 'R';
    else if (p == mp(0, -1)) return 'L';
    return '?';
}
int count_move_num(string s) {
    int num = 0;
    for(auto ch: s) num += ch != '-';
    return num;
}

P can_get_goal(int idx) {
    auto loc = s.locs[idx];
    auto goal = s.goals[idx];
    
    set<pair<int,int>> seen;
    int dh[] = {0, 0, 1, -1};
    int dw[] = {1, -1, 0, 0};

    priority_queue<P, vector<P>, greater<P> > que;
    que.push(goal);
    seen.insert(goal);
    while(!que.empty()){
       P p = que.top();
       // cout << "p:" << p.first << "," << p.second << endl;
       que.pop();
       REP(d, 4) {
           int h2 = p.first + dh[d];
           int w2 = p.second + dw[d];
           if (seen.count(mp(h2,w2))) continue;
           if (is_out_of_range(h2, w2)) continue;
           if (s.cells[h2][w2]) continue;
           if (mp(h2,w2) == loc) {
               auto h_diff = p.first - loc.first;
               auto w_diff = p.second - loc.second;
               return mp(h_diff, w_diff);
           }
           que.push(mp(h2,w2));
           seen.insert(mp(h2,w2));
       }
    }
    return mp(-1,-1);
}

int main(void)
{
    cin.sync_with_stdio(false);
    cin >> H >> W >> K >> T;

    s.locs.resize(K);
    s.goals.resize(K);
    shff.resize(K);
    REP(k,K) shff[k] = k;

    vector<tuple<int,int,int,int>> ABCDs(K);
    REP(k, K) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        ABCDs[k] = mt(a, b, c, d);
        s.locs[k] = mp(a, b);
        s.goals[k] = mp(c, d);
    }

    vector<string> anses;

//    REP(t, T) {
    int t = 0;
    bool last_flag = false;
    int last_time = 5;
    int MAX = 7000;
    for(; t < MAX; ++t) {
    // for(; t < 500; ++t) {
//    for(; t < 1000; ++t) {
        set<pair<int,int>> occupied;
        REP(k, K) {
            occupied.insert(s.locs[k]);
        }
        string ans(K, '-');
        random_shuffle(ALL(shff));
        for(auto k: shff) {
            vector<pair<int,int>> poss_move;

            // float random_poss = 0.5 - 0.2 * t / 5000;
            float random_poss = 0.5 - 0.0 * t / 5000;
            if (last_flag) {
                random_poss = 0.0;
            }

            if (rand() % 100 < (random_poss * 100)) {
                int rand_res = rand() % 4;
                if (rand_res == 0) poss_move.pb(mp(1,0));
                else if (rand_res == 1) poss_move.pb(mp(-1,0));
                else if (rand_res == 2) poss_move.pb(mp(0,1));
                else if (rand_res == 3) poss_move.pb(mp(0,-1));
            }
            else {
                if (s.locs[k] == s.goals[k]) {
                    poss_move.pb(mp(0,0));
                }
                else {
                    if (s.locs[k].first < s.goals[k].first) poss_move.pb(mp(1,0));
                    if (s.locs[k].first > s.goals[k].first) poss_move.pb(mp(-1,0));
                    if (s.locs[k].second < s.goals[k].second) poss_move.pb(mp(0,1));
                    if (s.locs[k].second > s.goals[k].second) poss_move.pb(mp(0,-1));
                }
            }

            random_shuffle(ALL(poss_move));
            bool found = false;
            for (auto m : poss_move) {
                auto new_loc = move_result(s.locs[k], m);
                if (is_out_of_range(new_loc.first, new_loc.second)) {
                    continue;
                }

                if (!occupied.count(new_loc)) {
                    occupied.insert(new_loc);
                    ans[k] = move_to_char(m);
                    found = true;
                    s.locs[k] = new_loc;
                    break;
                }
            }
            if (!found) ans[k] = '-';
        }

        if (last_flag) {
            --last_time;
            if (last_time == 0) break;
        }

        auto move_num = count_move_num(ans);
        if (move_num < 10 || t == MAX - last_time) {
            last_flag = true;
        }
        anses.pb(ans);
    }

    // int cur_t = t;
    // for(; t < cur_t + 20; ++t) {
    //     // cout << "---t:"  << t << "---" << endl;
    //     update_cells();
    //     string ans(K, '-');
    //     random_shuffle(ALL(shff));
    //     int cnt = 0;
    //     for(auto k: shff) {
    //         P move = can_get_goal(k);
    //         if (move != mp(-1,-1)) {
    //             cout << endl;
    //             cout << "cell:" << endl;
    //             REP(h,H) {
    //                 REP(w,W) cout << (int)s.cells[h][w];
    //                 cout << endl;
    //             }
    //             cout << k << "'s pos:" << s.locs[k].first << "," << s.locs[k].second << endl;
    //             cout << k << "'s goal:" << s.goals[k].first << "," << s.goals[k].second << endl;
    //             cout << "suggested move:" << move.first << "," << move.second << endl;


    //             ans[k] = move_to_char(move);
    //             auto new_loc = move_result(s.locs[k], move);
    //             s.cells[new_loc.first][new_loc.second] = 1;
    //             s.locs[k] = new_loc;
    //             ++cnt;
    //         }
    //         if (cnt == 20) break;
    //     }
    //     anses.pb(ans);
    // }

    // print ans
    cout << SIZE(anses) << endl;
    for(auto ans: anses) {
        cout << ans << endl;
    }

    return 0;
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User minus9d
Language C++14 (GCC 5.4.1)
Score 37266
Code Size 6996 Byte
Status AC
Exec Time 1129 ms
Memory 6932 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 1238 / 50000 1202 / 50000 1169 / 50000 1107 / 50000 1238 / 50000 1389 / 50000 1345 / 50000 1009 / 50000 1583 / 50000 1389 / 50000 1158 / 50000 1583 / 50000 1202 / 50000 1374 / 50000 1169 / 50000 1454 / 50000 1603 / 50000 1087 / 50000 299 / 50000 1238 / 50000 1359 / 50000 1316 / 50000 1051 / 50000 1169 / 50000 1276 / 50000 1345 / 50000 1289 / 50000 1238 / 50000 1345 / 50000 1042 / 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 1085 ms 6784 KB
subtask_01_02.txt AC 1092 ms 6784 KB
subtask_01_03.txt AC 1083 ms 6784 KB
subtask_01_04.txt AC 1076 ms 6784 KB
subtask_01_05.txt AC 1081 ms 6784 KB
subtask_01_06.txt AC 1077 ms 6784 KB
subtask_01_07.txt AC 1075 ms 6784 KB
subtask_01_08.txt AC 1084 ms 6784 KB
subtask_01_09.txt AC 1092 ms 6784 KB
subtask_01_10.txt AC 1079 ms 6784 KB
subtask_01_11.txt AC 1129 ms 6784 KB
subtask_01_12.txt AC 1091 ms 6784 KB
subtask_01_13.txt AC 1089 ms 6784 KB
subtask_01_14.txt AC 1079 ms 6932 KB
subtask_01_15.txt AC 1076 ms 6784 KB
subtask_01_16.txt AC 1080 ms 6784 KB
subtask_01_17.txt AC 1093 ms 6784 KB
subtask_01_18.txt AC 1071 ms 6784 KB
subtask_01_19.txt AC 1082 ms 6784 KB
subtask_01_20.txt AC 1097 ms 6784 KB
subtask_01_21.txt AC 1083 ms 6784 KB
subtask_01_22.txt AC 1078 ms 6784 KB
subtask_01_23.txt AC 1101 ms 6784 KB
subtask_01_24.txt AC 1093 ms 6784 KB
subtask_01_25.txt AC 1076 ms 6784 KB
subtask_01_26.txt AC 1077 ms 6784 KB
subtask_01_27.txt AC 1093 ms 6784 KB
subtask_01_28.txt AC 1081 ms 6784 KB
subtask_01_29.txt AC 1087 ms 6784 KB
subtask_01_30.txt AC 1078 ms 6784 KB