Submission #8256452

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

//const ll mod = 1000000007;
const int INF = 1e9;
int N, M, B;
int H, W;
int dh[4] = {1, 0, -1, 0};
int dw[4] = {0, 1, 0, -1};
string DRUL = "DRUL";
int gh, gw;
struct Robot {
    int h, w, direction;
};

struct Job {
    int cost, h, w, direction;
    Job(int _h, int _w, int _direction, int _cost) {
        h = _h;
        w = _w;
        direction = _direction;
        cost = _cost;
    }
};

bool operator>(Job a, Job b) {
    if(a.cost != b.cost) return a.cost > b.cost;
    //if(a.direction != b.direction) return a.direction > b.direction;
    return abs(a.h - gh) + abs(a.w - gw) > abs(b.h - gh) + abs(b.w - gw);
}

struct Query {
    int h, w, direction;
    Query(int _h, int _w, int _direction) {
        h = _h;
        w = _w;
        direction = _direction;
    }
};

struct Restore {
    int beforeh, beforew, beforedirection;
    int tile;
    Restore() {
        beforeh = 0;
        beforew = 0;
        beforedirection = 0;
        tile = 0;
    }
    Restore(int _beforeh, int _beforew, int _beforedirection, int _tile) {
        beforeh = _beforeh;
        beforew = _beforew;
        beforedirection = _beforedirection;
        tile = _tile;
    }
};

Robot Robots[105];
int nowscore = -1;
vector<Query> ANSWER;
struct Master {
    vector<vector<int>> field;
    int dist[105][105][4];
    bool departure[105][105][4];
    Restore before[105][105][4];
    int mIndex;
    int score = 0;
    bool visited[105][105];
    vector<Query> NowAnswer;
    void input() {
        cin >> N >> M >> B;
        cin >> gh >> gw;
        H = N;
        W = N;
        for(int i = 0; i < M; i++) {
            cin >> Robots[i].h >> Robots[i].w;
            char chr;
            cin >> chr;
            for(int k = 0; k < 4; k++) {
                if(chr == DRUL[k]) Robots[i].direction = k;
            }
        }
        field.resize(H);
        for(int h = 0; h < H; h++) {
            field[h].resize(W);
            for(int w = 0; w < W; w++) {
                field[h][w] = -1;
            }
        }
        for(int i = 0; i < B; i++) {
            int h, w;
            cin >> h >> w;
            field[h][w] = -2;
        }
    }
    void initialize() {
        for(int h = 0; h < H; h++) {
            for(int w = 0; w < W; w++) {
                if(field[h][w] != -2) field[h][w] = -1;
            }
        }
    }
    void Dijkstra() {
        for(int h = 0; h < H; h++) {
            for(int w = 0; w < W; w++) {
                for(int k = 0; k < 4; k++) {
                    dist[h][w][k] = INF;
                    departure[h][w][k] = false;
                }
            }
        }
        priority_queue<Job, vector<Job>, greater<Job>> que;
        for(int k = 0; k < 4; k++) {
            dist[gh][gw][k] = 0;
            que.emplace(gh, gw, k, 0);
        }
        while(!que.empty()) {
            Job now = que.top();
            que.pop();
            if(departure[now.h][now.w][now.direction]) continue;
            departure[now.h][now.w][now.direction] = true;
            //cerr << "---" << now.h << " " << now.w << " " << DRUL[now.direction] << " " << now.cost << " " << dist[now.h][now.w][now.direction] << "---" << endl;
            int invdirection = (now.direction + 2) % 4;
            for(int delta = 1; delta < N; delta++) {
                int newh = (now.h + dh[invdirection] * delta + H) % H;
                int neww = (now.w + dw[invdirection] * delta + W) % W;
                //cerr << "searching: " << newh << " " << neww << endl;
                if(field[newh][neww] == -2) break;
                else if(field[newh][neww] == -1) {
                    for(int newdirection = 0; newdirection < 4; newdirection++) {
                        int newcost = now.cost;
                        if(newdirection == now.direction) {
                            if(chmin(dist[newh][neww][newdirection], newcost)) {
                                Job NewJob(newh, neww, newdirection, newcost);
                                que.push(NewJob);
                                before[newh][neww][newdirection] = Restore(now.h, now.w, now.direction, -1);
                            }
                        } else {
                            newcost++;
                            if(chmin(dist[newh][neww][newdirection], newcost)) {
                                Job NewJob(newh, neww, newdirection, newcost);
                                que.push(NewJob);
                                before[newh][neww][newdirection] = Restore(now.h, now.w, now.direction, now.direction);
                            }
                        }
                    }
                } else {
                    if(now.direction != field[newh][neww]) break;
                    int newcost = now.cost;
                    for(int newdirection = 0; newdirection < 4; newdirection++) {
                        if(chmin(dist[newh][neww][newdirection], newcost)) {
                            Job NewJob(newh, neww, newdirection, newcost);
                            que.push(NewJob);
                            before[newh][neww][newdirection] = Restore(now.h, now.w, now.direction, field[newh][neww]);
                        }
                    }
                    break;
                }
            }
        }
    }
    void SelectRobot() {
        mIndex = -1;
        for(int i = 0; i < M; i++) {
            int nowval = dist[Robots[i].h][Robots[i].w][Robots[i].direction];
            if(nowval == 0) continue;
            if(nowval == INF) continue;
            if(mIndex == -1 || nowval < dist[Robots[mIndex].h][Robots[mIndex].w][Robots[mIndex].direction]) {
                mIndex = i;
            }
        }
    }
    void Place(int h, int w, int direction) {
        if(dist[h][w][direction] == 0) return;
        field[h][w] = before[h][w][direction].tile;
        int beforeh = before[h][w][direction].beforeh;
        int beforew = before[h][w][direction].beforew;
        int beforedirection = before[h][w][direction].beforedirection;
        Place(beforeh, beforew, beforedirection);
    }
    void Place() {
        Place(Robots[mIndex].h, Robots[mIndex].w, Robots[mIndex].direction);
    }
    void printfield() {
        for(int h = 0; h < H; h++) {
            for(int w = 0; w < W; w++) {
                cout << field[h][w] << " ";
            }
            cout << endl;
        }
    }
    void printdist() {
        for(int k = 0; k < 4; k++) {
            cout << "---" << k << "---" << endl;
            for(int h = 0; h < H; h++) {
                for(int w = 0; w < W; w++) {
                    if(field[h][w] != -2) {
                        cout << dist[h][w][k] << " ";
                    } else {
                        cout << -1 << " ";
                    }
                }
                cout << endl;
            }
            cout << endl;
        }
    }
    void BuildNowAnswer() {
        NowAnswer.clear();
        for(int h = 0; h < H; h++) {
            for(int w = 0; w < W; w++) {
                if(field[h][w] > -1) {
                    NowAnswer.emplace_back(h, w, field[h][w]);
                }
            }
        }
        /*
        cout << v.size() << endl;
        for(auto q : v) {
            cout << q.h << " " << q.w << " " << DRUL[q.direction] << endl;
        }
        */
    }
    void calculate() {
        score = 0;
        for(int h = 0; h < H; h++) {
            for(int w = 0; w < W; w++) {
                visited[h][w] = false;
                if(field[h][w] >= 0) score -= 10;
            }
        }
        for(int i = 0; i < M; i++) {
            trip(Robots[i].h, Robots[i].w, Robots[i].direction, 0);
        }
    }
    void trip(int h, int w, int direction, int timer) {
        if(timer > (N * N - B) * 4) return;
        if(field[h][w] == -2) return;
        if(!visited[h][w]) {
            score++;
            visited[h][w] = true;
        }
        if(h == gh && w == gw) {
            score += 1000;
            return;
        }
        if(field[h][w] >= 0) direction = field[h][w];
        int newh = (h + dh[direction] + H) % H;
        int neww = (w + dw[direction] + W) % W;
        trip(newh, neww, direction, timer + 1);
    }
};

void OutputAnswer() {
    cout << ANSWER.size() << "\n";
    for(auto q : ANSWER) {
        cout << q.h << " " << q.w << " " << DRUL[q.direction] << "\n";
    }
}

const int TL = 2900;

int main() {
    auto start = chrono::steady_clock::now();
    //cin.tie(nullptr); ios_base::sync_with_stdio(false);
    //cin.ignore(numeric_limits<streamsize>::max(), '\n');
    mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
    int now;
    Master master;
    master.input();
    while ((now = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count()) < TL) {
        //cerr << now << endl;
        master.initialize();
        while(true) {
            master.Dijkstra();
            master.SelectRobot();
            if(master.mIndex == -1) break;
            master.Place();
        }
        master.BuildNowAnswer();
        master.calculate();
        if(chmax(nowscore, master.score)) {
            swap(ANSWER, master.NowAnswer);
        }
        shuffle(Robots, Robots + M, mt);
    }
    OutputAnswer();
    //master.printdist();
    //master.printfield();
    //master.output();
    cerr << nowscore << endl;
    return 0;
}

Submission Info

Submission Time
Task A - ロボットの誘導
User kort0n
Language C++14 (GCC 5.4.1)
Score 4963153
Code Size 10054 Byte
Status AC
Exec Time 3000 ms
Memory 1280 KiB

Judge Result

Set Name Sample1 Sample2 Sample3 All
Score / Max Score 99360 / 100000 99340 / 100000 99362 / 100000 4665091 / 4700000
Status
AC × 1
AC × 1
AC × 1
AC × 47
Set Name Test Cases
Sample1 example_01.txt
Sample2 example_02.txt
Sample3 example_03.txt
All subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_01_27.txt, subtask_01_28.txt, subtask_01_29.txt, subtask_01_30.txt, subtask_01_31.txt, subtask_01_32.txt, subtask_01_33.txt, subtask_01_34.txt, subtask_01_35.txt, subtask_01_36.txt, subtask_01_37.txt, subtask_01_38.txt, subtask_01_39.txt, subtask_01_40.txt, subtask_01_41.txt, subtask_01_42.txt, subtask_01_43.txt, subtask_01_44.txt, subtask_01_45.txt, subtask_01_46.txt, subtask_01_47.txt, subtask_01_48.txt, subtask_01_49.txt, subtask_01_50.txt
Case Name Status Exec Time Memory
example_01.txt AC 2909 ms 1152 KiB
example_02.txt AC 2928 ms 1152 KiB
example_03.txt AC 2997 ms 1152 KiB
subtask_01_04.txt AC 2959 ms 1152 KiB
subtask_01_05.txt AC 2907 ms 1152 KiB
subtask_01_06.txt AC 2962 ms 1152 KiB
subtask_01_07.txt AC 2916 ms 1152 KiB
subtask_01_08.txt AC 2970 ms 1152 KiB
subtask_01_09.txt AC 2941 ms 1152 KiB
subtask_01_10.txt AC 2943 ms 1152 KiB
subtask_01_11.txt AC 2908 ms 1152 KiB
subtask_01_12.txt AC 2947 ms 1152 KiB
subtask_01_13.txt AC 2964 ms 1152 KiB
subtask_01_14.txt AC 2930 ms 1152 KiB
subtask_01_15.txt AC 2936 ms 1152 KiB
subtask_01_16.txt AC 2929 ms 1152 KiB
subtask_01_17.txt AC 2950 ms 1152 KiB
subtask_01_18.txt AC 2939 ms 1152 KiB
subtask_01_19.txt AC 2995 ms 1152 KiB
subtask_01_20.txt AC 2918 ms 1152 KiB
subtask_01_21.txt AC 2975 ms 1152 KiB
subtask_01_22.txt AC 2934 ms 1152 KiB
subtask_01_23.txt AC 2958 ms 1152 KiB
subtask_01_24.txt AC 2957 ms 1152 KiB
subtask_01_25.txt AC 3000 ms 1152 KiB
subtask_01_26.txt AC 2935 ms 1152 KiB
subtask_01_27.txt AC 2911 ms 1152 KiB
subtask_01_28.txt AC 2932 ms 1152 KiB
subtask_01_29.txt AC 2916 ms 1152 KiB
subtask_01_30.txt AC 2936 ms 1280 KiB
subtask_01_31.txt AC 2989 ms 1152 KiB
subtask_01_32.txt AC 2905 ms 1152 KiB
subtask_01_33.txt AC 2979 ms 1152 KiB
subtask_01_34.txt AC 2906 ms 1280 KiB
subtask_01_35.txt AC 2920 ms 1152 KiB
subtask_01_36.txt AC 2997 ms 1152 KiB
subtask_01_37.txt AC 2991 ms 1152 KiB
subtask_01_38.txt AC 2917 ms 1280 KiB
subtask_01_39.txt AC 2988 ms 1152 KiB
subtask_01_40.txt AC 2937 ms 1152 KiB
subtask_01_41.txt AC 2904 ms 1152 KiB
subtask_01_42.txt AC 2973 ms 1152 KiB
subtask_01_43.txt AC 2943 ms 1152 KiB
subtask_01_44.txt AC 2976 ms 1152 KiB
subtask_01_45.txt AC 2935 ms 1152 KiB
subtask_01_46.txt AC 2928 ms 1152 KiB
subtask_01_47.txt AC 2927 ms 1152 KiB
subtask_01_48.txt AC 2995 ms 1152 KiB
subtask_01_49.txt AC 2969 ms 1152 KiB
subtask_01_50.txt AC 2938 ms 1152 KiB