Submission #73751275

---

Source Code Expand

#include <bits/stdc++.h>
#include <chrono>

using namespace std;

struct Timer {
    std::chrono::high_resolution_clock::time_point start_time;
    Timer() { start_time = std::chrono::high_resolution_clock::now(); }
    double get_time() const {
        auto end_time = std::chrono::high_resolution_clock::now();
        return std::chrono::duration<double>(end_time - start_time).count();
    }
};

uint32_t xorshift() {
    static uint32_t x = 123456789;
    static uint32_t y = 362436069;
    static uint32_t z = 521288629;
    static uint32_t w = 88675123;
    uint32_t t = x ^ (x << 11);
    x = y; y = z; z = w;
    return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
double rnd() { return xorshift() * 2.3283064365386962e-10; }

int R_c = 20, C_c = 20; // renamed to avoid macro conflict just in case
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
// U=0, R=1, D=2, L=3

int encode_state(int r, int c, int d) {
    return r * 80 + c * 4 + d;
}

int num_states = 1600;

enum EdgeType {
    EDGE_F,
    EDGE_R,
    EDGE_L,
    EDGE_F_UNTIL_R,
    EDGE_F_UNTIL_L,
    EDGE_F_UNTIL_STOP
};

struct Edge {
    int to;
    EdgeType type;
    uint64_t cov[7];
};

short dist_st[1600][1600];
short parent_st[1600][1600];
EdgeType parent_edge_type[1600][1600];
uint64_t pre_cov[1600][1600][7];

int cell_visit_count[400] = {0};
int uncov_count = 400;

void add_path(int u, int v) {
    for (int j = 0; j < 7; ++j) {
        uint64_t mask = pre_cov[u][v][j];
        while (mask) {
            int bit = std::countr_zero(mask);
            int cell = j * 64 + bit;
            if (cell_visit_count[cell] == 0) uncov_count--;
            cell_visit_count[cell]++;
            mask &= mask - 1;
        }
    }
}

void rem_path(int u, int v) {
    for (int j = 0; j < 7; ++j) {
        uint64_t mask = pre_cov[u][v][j];
        while (mask) {
            int bit = std::countr_zero(mask);
            int cell = j * 64 + bit;
            cell_visit_count[cell]--;
            if (cell_visit_count[cell] == 0) uncov_count++;
            mask &= mask - 1;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    Timer timer;

    int N, Ak, Am, Aw;
    if (!(cin >> N >> Ak >> Am >> Aw)) return 0;

    vector<string> right_wall(N), down_wall(N - 1);
    for (int i = 0; i < N; ++i) cin >> right_wall[i];
    for (int i = 0; i < N - 1; ++i) cin >> down_wall[i];

    vector<vector<Edge>> adj(num_states);

    auto has_wall = [&](int r, int c, int d) {
        if (d == 0) {
            if (r == 0) return true;
            return down_wall[r - 1][c] == '1';
        } else if (d == 1) {
            if (c == C_c - 1) return true;
            return right_wall[r][c] == '1';
        } else if (d == 2) {
            if (r == R_c - 1) return true;
            return down_wall[r][c] == '1';
        } else if (d == 3) {
            if (c == 0) return true;
            return right_wall[r][c - 1] == '1';
        }
        return true;
    };

    for (int r = 0; r < R_c; ++r) {
        for (int c = 0; c < C_c; ++c) {
            for (int d = 0; d < 4; ++d) {
                int u = encode_state(r, c, d);
                
                // Micro edges (cost 1 state transition)
                if (!has_wall(r, c, d)) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];
                    int v = encode_state(nr, nc, d);
                    Edge e = {v, EDGE_F};
                    for (int j = 0; j<7; ++j) e.cov[j] = 0;
                    int cell_v = v / 4;
                    e.cov[cell_v / 64] |= (1ULL << (cell_v % 64));
                    adj[u].push_back(e);
                }
                
                {
                    int v = encode_state(r, c, (d + 1) % 4);
                    Edge e = {v, EDGE_R};
                    for (int j = 0; j<7; ++j) e.cov[j] = 0;
                    adj[u].push_back(e);
                }
                
                {
                    int v = encode_state(r, c, (d + 3) % 4);
                    Edge e = {v, EDGE_L};
                    for (int j = 0; j<7; ++j) e.cov[j] = 0;
                    adj[u].push_back(e);
                }

                // Macro edges (cost 1 state transition but multiple physical cells)
                if (!has_wall(r, c, d)) {
                    int cr = r, cc = c;
                    uint64_t path_cov[7] = {0};
                    
                    while (!has_wall(cr, cc, d)) {
                        cr += dr[d];
                        cc += dc[d];
                        int cell = (cr * C_c + cc);
                        path_cov[cell / 64] |= (1ULL << (cell % 64));
                    }
                    
                    // Hit a wall at (cr, cc). We can turn Right, Left, or Stop.
                    int v_r = encode_state(cr, cc, (d + 1) % 4);
                    Edge e_r = {v_r, EDGE_F_UNTIL_R};
                    for (int j = 0; j<7; ++j) e_r.cov[j] = path_cov[j];
                    adj[u].push_back(e_r);

                    int v_l = encode_state(cr, cc, (d + 3) % 4);
                    Edge e_l = {v_l, EDGE_F_UNTIL_L};
                    for (int j = 0; j<7; ++j) e_l.cov[j] = path_cov[j];
                    adj[u].push_back(e_l);

                    // EDGE_F_UNTIL_STOP removed: on_wall='F' is illegal per problem constraints
                    // BFS can reach (cr,cc,d) via EDGE_F_UNTIL_R + EDGE_L or EDGE_F_UNTIL_L + EDGE_R
                }
            }
        }
    }

    for (int s = 0; s < num_states; ++s) {
        for (int i = 0; i < num_states; ++i) {
            dist_st[s][i] = 10000;
            parent_st[s][i] = -1;
            for (int j = 0; j < 7; ++j) pre_cov[s][i][j] = 0;
        }
        dist_st[s][s] = 0;
        int cell_s = s / 4;
        pre_cov[s][s][cell_s / 64] |= (1ULL << (cell_s % 64));

        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (const auto& e : adj[u]) {
                int v = e.to;
                if (dist_st[s][v] == 10000) {
                    dist_st[s][v] = dist_st[s][u] + 1;
                    parent_st[s][v] = u;
                    parent_edge_type[s][v] = e.type;
                    for (int j = 0; j < 7; ++j) {
                        pre_cov[s][v][j] = pre_cov[s][u][j] | e.cov[j];
                    }
                    if (e.type == EDGE_F && u == s) {
                        // The initial state cell coverage is already handled, this ensures the destination cell is added for F
                        int cell_v = v / 4;
                        pre_cov[s][v][cell_v / 64] |= (1ULL << (cell_v % 64));
                    }
                    q.push(v);
                }
            }
        }
    }

    // Init TSP path
    vector<int> current_W;
    vector<bool> init_visited(400, false);
    int cur_s = encode_state(0, 0, 1);
    current_W.push_back(cur_s);
    init_visited[0] = true;

    for (int step = 1; step < 400; ++step) {
        int best_v = -1;
        int best_dist = 10000;
        for (int c = 0; c < 400; ++c) {
            if (init_visited[c]) continue;
            for (int d = 0; d < 4; ++d) {
                int v = c * 4 + d;
                if (dist_st[cur_s][v] < best_dist) {
                    best_dist = dist_st[cur_s][v];
                    best_v = v;
                }
            }
        }
        init_visited[best_v / 4] = true;
        current_W.push_back(best_v);
        cur_s = best_v;
    }

    int current_len = 0;
    for (int i = 0; i < current_W.size(); ++i) {
        int u = current_W[i];
        int v = current_W[(i + 1) % current_W.size()];
        current_len += dist_st[u][v];
        add_path(u, v);
    }
    int current_score = current_len + uncov_count * 10000;

    vector<int> best_W = current_W;
    int best_score = current_score;

    double start_temp = 200.0;
    double end_temp = 0.1;
    int iter = 0;

    while (true) {
        if ((iter & 2047) == 0) {
            if (timer.get_time() > 1.90) break;
        }
        iter++;

        double elapsed = timer.get_time();
        double temp = start_temp * pow(end_temp / start_temp, elapsed / 1.90);

        int k = current_W.size();
        if (k == 0) continue;

        int type = xorshift() % 100;
        if (uncov_count > 0 && type < 60) {
            type = 50; // Force insert when cells are uncovered
        }

        if (type < 40 && k > 1) { // Delete
            int idx = xorshift() % k;
            int prev = current_W[(idx - 1 + k) % k];
            int curr = current_W[idx];
            int next = current_W[(idx + 1) % k];

            int delta_len = dist_st[prev][next] - dist_st[prev][curr] - dist_st[curr][next];
            rem_path(prev, curr);
            rem_path(curr, next);
            add_path(prev, next);

            int next_score = current_len + delta_len + uncov_count * 10000;
            if (next_score <= current_score || rnd() < exp((current_score - next_score) / temp)) {
                current_score = next_score;
                current_len += delta_len;
                current_W.erase(current_W.begin() + idx);
                if (current_score < best_score) {
                    best_score = current_score;
                    best_W = current_W;
                }
            } else {
                rem_path(prev, next);
                add_path(prev, curr);
                add_path(curr, next);
            }
        } else if (type < 70) { // Insert
            int new_c;
            if (uncov_count > 0 && (xorshift() % 2 == 0)) {
                vector<int> uncovs;
                for (int i = 0; i < 400; ++i) if (cell_visit_count[i] == 0) uncovs.push_back(i);
                new_c = uncovs[xorshift() % uncovs.size()];
            } else {
                new_c = xorshift() % 400;
            }
            int new_s = new_c * 4 + (xorshift() % 4);
            int idx = xorshift() % (k + 1);
            
            int prev = current_W[(idx - 1 + k) % k];
            int next = current_W[idx % k];

            if (idx == k && k == 1) {
                prev = current_W[0];
                next = current_W[0];
            }

            int delta_len = dist_st[prev][new_s] + dist_st[new_s][next] - dist_st[prev][next];
            rem_path(prev, next);
            add_path(prev, new_s);
            add_path(new_s, next);

            int next_score = current_len + delta_len + uncov_count * 10000;
            if (next_score <= current_score || rnd() < exp((current_score - next_score) / temp)) {
                current_score = next_score;
                current_len += delta_len;
                current_W.insert(current_W.begin() + idx, new_s);
                if (current_score < best_score) {
                    best_score = current_score;
                    best_W = current_W;
                }
            } else {
                rem_path(prev, new_s);
                rem_path(new_s, next);
                add_path(prev, next);
            }
        } else if (k > 1) { // Replace
            int idx = xorshift() % k;
            int new_c;
            if (uncov_count > 0 && (xorshift() % 2 == 0)) {
                vector<int> uncovs;
                for (int i = 0; i < 400; ++i) if (cell_visit_count[i] == 0) uncovs.push_back(i);
                new_c = uncovs[xorshift() % uncovs.size()];
            } else {
                new_c = xorshift() % 400;
            }
            int new_s = new_c * 4 + (xorshift() % 4);

            int curr = current_W[idx];
            if (curr == new_s) continue;

            int prev = current_W[(idx - 1 + k) % k];
            int next = current_W[(idx + 1) % k];

            int delta_len = dist_st[prev][new_s] + dist_st[new_s][next] - dist_st[prev][curr] - dist_st[curr][next];
            rem_path(prev, curr);
            rem_path(curr, next);
            add_path(prev, new_s);
            add_path(new_s, next);

            int next_score = current_len + delta_len + uncov_count * 10000;
            if (next_score <= current_score || rnd() < exp((current_score - next_score) / temp)) {
                current_score = next_score;
                current_len += delta_len;
                current_W[idx] = new_s;
                if (current_score < best_score) {
                    best_score = current_score;
                    best_W = current_W;
                }
            } else {
                rem_path(prev, new_s);
                rem_path(new_s, next);
                add_path(prev, curr);
                add_path(curr, next);
            }
        }
    }

struct OutputState {
        char on_empty_cmd;
        int on_empty_next;
        char on_wall_cmd;
        int on_wall_next;
        bool mapped = false;
    };

    vector<OutputState> out_states;
    auto add_state = [&](char ec, int en, char wc, int wn) {
        out_states.push_back({ec, en, wc, wn, true});
        return (int)out_states.size() - 1;
    };

    int start_s = best_W[0];
    int init_r = (start_s / 4) / 20;
    int init_c = (start_s / 4) % 20;
    int init_d = start_s % 4;
    char dc_char[] = {'U', 'R', 'D', 'L'};

    int current_state_idx = 0; // Starting from state 0
    out_states.push_back({'F', 0, 'R', 0, false}); // Placeholder for start state

    // We only construct if best_W makes a valid cover.
    for (int i = 0; i < best_W.size(); ++i) {
        int u = best_W[i];
        int v = best_W[(i + 1) % best_W.size()];
        
        vector<int> path_nodes;
        vector<EdgeType> path_edges;
        
        int curr = v;
        while (curr != u) {
            path_nodes.push_back(curr);
            path_edges.push_back(parent_edge_type[u][curr]);
            curr = parent_st[u][curr];
        }
        reverse(path_nodes.begin(), path_nodes.end());
        reverse(path_edges.begin(), path_edges.end());
        
        for (int j = 0; j < path_nodes.size(); ++j) {
            int next_node = path_nodes[j];
            EdgeType e_type = path_edges[j];
            
            int next_state_idx = current_state_idx + 1;
            
            if (e_type == EDGE_F) {
                out_states[current_state_idx] = {'F', next_state_idx, 'R', current_state_idx, true};
            } else if (e_type == EDGE_R) {
                out_states[current_state_idx] = {'R', next_state_idx, 'R', next_state_idx, true};
            } else if (e_type == EDGE_L) {
                out_states[current_state_idx] = {'L', next_state_idx, 'L', next_state_idx, true};
            } else if (e_type == EDGE_F_UNTIL_R) {
                out_states[current_state_idx] = {'F', current_state_idx, 'R', next_state_idx, true};
            } else if (e_type == EDGE_F_UNTIL_L) {
                out_states[current_state_idx] = {'F', current_state_idx, 'L', next_state_idx, true};
            }
            
            current_state_idx = next_state_idx;
            out_states.push_back({'F', 0, 'R', 0, false}); // Prepare next state holder
        }
    }
    
    // Output Loop ties the last state back to 0
    out_states.pop_back(); // Remove the unfilled trailing state holder
    if (!out_states.empty()) {
        int last_idx = out_states.size() - 1;
        if (out_states[last_idx].on_empty_next > last_idx) out_states[last_idx].on_empty_next = 0;
        if (out_states[last_idx].on_wall_next > last_idx) out_states[last_idx].on_wall_next = 0;
    }

    int M = out_states.size();

    cout << 1 << "\n";
    cout << M << " " << init_r << " " << init_c << " " << dc_char[init_d] << "\n";

    for (int i = 0; i < M; ++i) {
        cout << out_states[i].on_empty_cmd << " " << out_states[i].on_empty_next << " "
             << out_states[i].on_wall_cmd << " " << out_states[i].on_wall_next << "\n";
    }

    // output remaining W walls (0 elements)
    for (int i = 0; i < N; ++i) { for (int j = 0; j < N - 1; ++j) cout << "0"; cout << "\n"; }
    for (int i = 0; i < N - 1; ++i) { for (int j = 0; j < N; ++j) cout << "0"; cout << "\n"; }

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'int main()':
./Main.cpp:128:40: warning: missing initializer for member 'Edge::cov' [-Wmissing-field-initializers]
  128 |                     Edge e = {v, EDGE_F};
      |                                        ^
./Main.cpp:137:40: warning: missing initializer for member 'Edge::cov' [-Wmissing-field-initializers]
  137 |                     Edge e = {v, EDGE_R};
      |                                        ^
./Main.cpp:144:40: warning: missing initializer for member 'Edge::cov' [-Wmissing-field-initializers]
  144 |                     Edge e = {v, EDGE_L};
      |                                        ^
./Main.cpp:163:52: warning: missing initializer for member 'Edge::cov' [-Wmissing-field-initializers]
  163 |                     Edge e_r = {v_r, EDGE_F_UNTIL_R};
      |                                                    ^
./Main.cpp:168:52: warning: missing initializer for member 'Edge::cov' [-Wmissing-field-initializers]
  168 |                     Edge e_l = {v_l, EDGE_F_UNTIL_L};
      |                                                    ^
./Main.cpp:239:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  239 |     for (int i = 0; i < current_W.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~~
./Main.cpp:401:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  401 |     for (int i = 0; i < best_W.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
./Main.cpp:417:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  417 |         for (int j = 0; j < path_nodes.size(); ++j) {
      |                         ~~^~~~~~~~~~~~~~~~~~~
./Main.cpp:418:17: warning: unused variable 'next_node' [-Wunused-variable]
  418 |             int next_node = path_nodes[j];
      |                 ^~~~~~~~~
./Main.cpp:386:10: warning: variable 'add_state' set but not used [-Wunused-but-set-variable]
  386 |     auto add_state = [&](char ec, int en, char wc, int wn) {
      |          ^~~~~~~~~

Judge Result