Submission #65213583

---

Source Code Expand

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) (v).begin(), (v).end()
#define sz(a) ((long long)(a).size())
#define X first
#define Y second
// #define endl '\n'
 
using ll = long long;
using ull = unsigned long long;
using dbl = long double;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll myRandMod) {
    return (ull)rng() % myRandMod;
}
 
const ll INF = 1e9;
const ll LINF = 1e18;
const int MOD = (int)1e9 + 7;
const int MAXN = 4e5 + 555;

const int N = 20;
const int M = 40;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const char dir[] = {'U', 'D', 'L', 'R'};
const int INF_SIZE = 1000;

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

vector<Point> targets;
vector<vector<char>> grid;
vector<vector<pair<char, char>>> actions;

// Precalculated slide destinations for each position and direction
vector<vector<vector<Point>>> slide_dest;

bool isValid(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

void precalculateSlides() {
    slide_dest.assign(N, vector<vector<Point>>(N, vector<Point>(4)));
    
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            for (int d = 0; d < 4; d++) {
                int nx = x;
                int ny = y;
                while (true) {
                    int nextX = nx + dx[d];
                    int nextY = ny + dy[d];
                    if (!isValid(nextX, nextY) || grid[nextX][nextY] == 'B') {
                        break;
                    }
                    nx = nextX;
                    ny = nextY;
                }
                slide_dest[x][y][d] = Point(nx, ny);
            }
        }
    }
}

vector<pair<char, char>> findPath(Point start, Point end, const vector<vector<char>>& grid) {
    vector<vector<int>> dist(N, vector<int>(N, INF));
    vector<vector<pair<char, char>>> prev_action(N, vector<pair<char, char>>(N));
    vector<vector<Point>> prev_pos(N, vector<Point>(N));
    queue<Point> q;
    
    dist[start.x][start.y] = 0;
    q.push(start);
    
    while (!q.empty()) {
        Point cur = q.front();
        q.pop();
        
        if (cur == end) break;
        
        // Try all possible moves and slides
        for (int d = 0; d < 4; d++) {
            // Try move
            int nx = cur.x + dx[d];
            int ny = cur.y + dy[d];
            
            if (isValid(nx, ny) && grid[nx][ny] != 'B' && dist[nx][ny] > dist[cur.x][cur.y] + 1) {
                dist[nx][ny] = dist[cur.x][cur.y] + 1;
                prev_action[nx][ny] = {'M', dir[d]};
                prev_pos[nx][ny] = cur;
                q.push(Point(nx, ny));
            }
            
            // Try slide using precalculated destination
            Point slideEnd = slide_dest[cur.x][cur.y][d];
            if (slideEnd != cur && dist[slideEnd.x][slideEnd.y] > dist[cur.x][cur.y] + 1) {
                dist[slideEnd.x][slideEnd.y] = dist[cur.x][cur.y] + 1;
                prev_action[slideEnd.x][slideEnd.y] = {'S', dir[d]};
                prev_pos[slideEnd.x][slideEnd.y] = cur;
                q.push(slideEnd);
            }
        }
    }
    
    if (dist[end.x][end.y] == INF) {
        return vector<pair<char, char>>(INF_SIZE);
    }
    
    vector<pair<char, char>> path;
    Point cur = end;
    while (cur != start) {
        path.push_back(prev_action[cur.x][cur.y]);
        cur = prev_pos[cur.x][cur.y];
    }
    reverse(all(path));
    
    // Verify path
    /*
    Point pos = start;
    for (auto [action, direction] : path) {
        int d = static_cast<int>(find(dir, dir + 4, direction) - dir);
        if (action == 'M') {
            pos.x += dx[d];
            pos.y += dy[d];
            if (!isValid(pos.x, pos.y) || grid[pos.x][pos.y] == 'B') {
                cerr << "Invalid move in path: " << action << " " << direction << " at (" << pos.x << "," << pos.y << ")" << endl;
                cerr << "Grid state:" << endl;
                for (int x = 0; x < N; x++) {
                    for (int y = 0; y < N; y++) {
                        cerr << (grid[x][y] == 'B' ? 'B' : '.');
                    }
                    cerr << endl;
                }
                assert(false);
                return vector<pair<char, char>>(INF_SIZE);
            }
        } else if (action == 'S') {
            pos = slide_dest[pos.x][pos.y][d];
        }
    }
    */
    
    return path;
}

double sum_path_length = 0;

int n, m;

void read_input() {
    cin >> n >> m;
    
    targets.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> targets[i].x >> targets[i].y;
    }
}

void generate_input() {
    n = 20;
    m = 40;
    targets.resize(m);
    vector<Point> all_points;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            all_points.push_back(Point(i, j));
        }
    }
    random_shuffle(all(all_points));
    for (int i = 0; i < m; i++) {
        targets[i] = all_points[i];
    }
}

void print_ans() {
    for (int i = 0; i < m; i++) {
        for (auto [a, dc] : actions[i]) {
            cout << a << " " << dc << endl;
        }
    }
}

void print_input() {
    cout << n << " " << m << endl;
    for (int i = 0; i < m; i++) {
        cout << targets[i].x << " " << targets[i].y << endl;
    }
    cout << endl;
}

auto calc_slide_dest(int x, int y, int d) {
    int nx = x;
    int ny = y;
    while (true) {
        int nextX = nx + dx[d];
        int nextY = ny + dy[d];
        if (!isValid(nextX, nextY) || grid[nextX][nextY] == 'B') {
            break;
        }
        nx = nextX;
        ny = nextY;
    }   
    return make_pair(nx, ny);
}

bool is_target[N][N];

void solve(bool need_cout = true) {
    grid.assign(N, vector<char>(N, '.'));
    precalculateSlides();

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            is_target[i][j] = false;
        }
    }
    for (int i = 0; i < m; i++) {
        is_target[targets[i].x][targets[i].y] = true;
    }
    

    // Initial solution without alter operations
    actions.clear();
    actions.push_back({});
    for (int i = 1; i < m; i++) {
        vector<pair<char, char>> path = findPath(targets[i-1], targets[i], grid);
        actions.push_back(path);
    }
    // Calculate total number of actions in the solution
    auto countTotalActions = [&]() -> int {
        int total = 0;
        for (const auto& path : actions) {
            total += (int)path.size();
        }
        return total;
    };
    
    cerr << "initial actions size: " << countTotalActions() << endl;

    // cerr << targets[7].x << " " << targets[7].y << endl;
    // cerr << targets[8].x << " " << targets[8].y << endl;
    
    // Optimization phase
    for (int i = 1; i < m; i++) {
        cerr << "optimization phase " << i << " start" << endl;
        cerr << "time = " << clock() / (double)CLOCKS_PER_SEC << endl;
        bool improved = true;
        int iter = 0;

        vector<Point> cur_iter_blocked;
        while (improved) {
            improved = false;
            int bestDelta = 0;
            Point bestPos;
            // cerr << "i = " << i << " iter = " << iter << endl;
            
            // vector<pair<char, char>> currentPath = findPath(targets[i-1], targets[i], grid);
            // assert(currentPath.size() == actions[i].size());
            // assert(currentPath.size() != INF_SIZE);
            auto currentPath = actions[i];
            // Precalculate which cells we'll visit in the current path
            vector<vector<int>> willVisit(N, vector<int>(N, 0));
            Point pos = targets[i-1];
            ++willVisit[pos.x][pos.y];

            // cerr << "precalculate willVisit" << endl;
            // cerr << "currentPath = " << currentPath.size() << endl;

            for (auto p : cur_iter_blocked) {
                grid[p.x][p.y] = (grid[p.x][p.y] == 'B' ? '.' : 'B');
                willVisit[p.x][p.y] = 1000;
            }
            
            for (auto [a, dc] : currentPath) {
                int d = static_cast<int>(find(dir, dir + 4, dc) - dir);
                if (a == 'M') {
                    pos.x += dx[d];
                    pos.y += dy[d];
                } else if (a == 'S') {
                    int sx, sy;
                    tie(sx, sy) = calc_slide_dest(pos.x, pos.y, d);
                    assert(isValid(sx, sy));
                    int stx = min(pos.x, sx);
                    int enx = max(pos.x, sx);
                    int sty = min(pos.y, sy);
                    int eny = max(pos.y, sy);
                    for (int q = stx; q <= enx; ++q) {
                        for (int w = sty; w <= eny; ++w) {
                            assert(isValid(q, w));
                            ++willVisit[q][w];
                        }
                    }
                    pos = Point(sx, sy);
                    int tx = pos.x + dx[d];
                    int ty = pos.y + dy[d];
                    if (isValid(tx, ty)) {
                        ++willVisit[tx][ty];
                    }
                } else if (a == 'A') {
                    int tx = pos.x + dx[d];
                    int ty = pos.y + dy[d];
                    assert(isValid(tx, ty));
                    assert(!is_target[tx][ty]);
                    ++willVisit[tx][ty];
                    grid[tx][ty] = (grid[tx][ty] == 'B' ? '.' : 'B');
                }
                assert(isValid(pos.x, pos.y));
                ++willVisit[pos.x][pos.y];
            }
            if (pos != targets[i]) {
                print_input();
                print_ans();
            }
            assert(pos == targets[i]);
            precalculateSlides();
            // cerr << "precalculate willVisit end" << endl;
            
            // Try placing blocks along the path
            pos = targets[i-1];
            vector<vector<bool>> triedBlock(N, vector<bool>(N, false));
            
            
            int insertPos = -1;
            char insertDir;
            int currentPathIt = -1;
            // cerr << "currentPath = " << currentPath.size() << endl;

            cerr << "try to find insert position" << endl;
            for (auto [a, dc] : currentPath) {
                ++currentPathIt;

                // cerr << "currentPathIt = " << currentPathIt << endl;
                int d = static_cast<int>(find(dir, dir + 4, dc) - dir);
                if (a == 'M') {
                    pos.x += dx[d];
                    pos.y += dy[d];
                } else if (a == 'S') {
                    pos = slide_dest[pos.x][pos.y][d];
                    int tx = pos.x + dx[d];
                    int ty = pos.y + dy[d];
                    if (isValid(tx, ty)) {
                        // --willVisit[tx][ty];
                    }
                }
                static auto prevA = a;
                --willVisit[pos.x][pos.y];
                // if (a == 'A' || prevA == 'A') {
                //     continue;
                // }
                prevA = a;
                
                // Try placing/removing block in each direction
                for (int d1 = 0; d1 < 4; d1++) {
                    int nx = pos.x + dx[int(d1)];
                    int ny = pos.y + dy[int(d1)];
                    
                    // Check if the position is valid and we won't visit it later
                    if (isValid(nx, ny) && !willVisit[nx][ny] && !triedBlock[nx][ny]) {
                        if (is_target[nx][ny]) {
                            continue;
                        }
                        triedBlock[nx][ny] = true;
                        
                        // Toggle the block state
                        grid[nx][ny] = (grid[nx][ny] == 'B' ? '.' : 'B');
                        
                        // Recalculate slides after grid change
                        precalculateSlides();
                        
                        // Calculate new path lengths
                        int delta = 1;
                        for (int j = i + 1; j < m; j++) {
                            vector<pair<char, char>> path = findPath(targets[j - 1], targets[j], grid);
                            delta += static_cast<int>(path.size()) - static_cast<int>(actions[j].size());
                        }
                        
                        // Revert block change
                        grid[nx][ny] = (grid[nx][ny] == 'B' ? '.' : 'B');
                        
                        // Recalculate slides after reverting
                        precalculateSlides();
                        
                        if (delta < bestDelta) {
                            insertPos = currentPathIt + 1;
                            insertDir = dir[d1];

                            bestDelta = delta;
                            bestPos = Point(nx, ny);
                        }
                    }
                }
            }
            if (bestDelta < 0) {
                improved = true;
                grid[bestPos.x][bestPos.y] = (grid[bestPos.x][bestPos.y] == 'B' ? '.' : 'B');
                assert(!is_target[bestPos.x][bestPos.y]);
                cur_iter_blocked.push_back(bestPos);
                
                // Recalculate slides after final grid change
                precalculateSlides();

                // Insert block placement action at the saved position
                cerr << "insertPos = " << insertPos << " " << actions[i].size() << endl;
                if (insertPos != -1) {
                    assert(insertPos <= (int)actions[i].size());
                    actions[i].insert(actions[i].begin() + insertPos, {'A', insertDir});
                } else {
                    assert(false);
                }
                
                // if (i == 7) {
                //     int cnt = 0;
                //     for (int l = 0; l < i; ++l) {
                //         cnt += actions[l].size();
                //     }
                //     cerr << "cnt = " << cnt << endl;
                //     cerr << "actions[i].size() = " << actions[i].size() << endl;
                //     for (auto [a, dc] : actions[i]) {
                //         cerr << a << " " << dc << endl;
                //     }
                // }
                
                // Update actions for remaining paths
                // cerr << "update actions for remaining paths" << endl;
                for (int j = i + 1; j < m; j++) {
                    vector<pair<char, char>> path = findPath(targets[j - 1], targets[j], grid);
                    assert(path.size() != INF_SIZE);
                    actions[j] = path;
                }
            }
        }
        // cerr << "optimization phase " << i << " end" << endl;
    }
    
    cerr << "final actions size: " << countTotalActions() << endl;
    sum_path_length += countTotalActions();
    if (need_cout) {    
        // Output the solution
        for (auto path : actions) {
            for (auto [action, direction] : path) {
                assert(action == 'M' || action == 'S' || action == 'A');
                assert(direction == 'U' || direction == 'D' || direction == 'L' || direction == 'R');
                cout << action << " " << direction << "\n";
            }
        }
    }
}

const int STRESS = 0;
 
signed main() {
#ifdef LOCAL
    assert(freopen("in.txt", "r", stdin));
    assert(freopen("out.txt", "w", stdout));
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(20);
 
    int T = 1;
    // cin >> T;
    if (STRESS) {
        T = 10;
    }
    for (int numt = 0; numt < T; ++numt) {
        if (STRESS) {
            generate_input();
            solve(false);
        } else {
            read_input();
            solve(true);
        }
    }
    double avg_path_len = sum_path_length / (double)T;
    cerr << "avg path length = " << avg_path_len<< endl;
    cerr << "avg path_per_target length = " << avg_path_len / (double)M << endl;
    cerr << "score = " << (M + 2 * N * M - avg_path_len) * 150 << endl;
 
#ifdef LOCAL
    cerr << endl << endl << "time = " << clock() / (double)CLOCKS_PER_SEC << endl;
#endif
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve(bool)’:
Main.cpp:355:29: warning: variable ‘prevA’ set but not used [-Wunused-but-set-variable]
  355 |                 static auto prevA = a;
      |                             ^~~~~
Main.cpp:258:13: warning: unused variable ‘iter’ [-Wunused-variable]
  258 |         int iter = 0;
      |             ^~~~
In file included from /usr/include/c++/12/bits/stl_algobase.h:64,
                 from /usr/include/c++/12/bits/specfun.h:45,
                 from /usr/include/c++/12/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/12/bits/stdc++.h:41,
                 from Main.cpp:4:
In constructor ‘constexpr std::pair<_T1, _T2>::pair(_U1&&, _U2&&) [with _U1 = char; _U2 = char&; _T1 = char; _T2 = char]’,
    inlined from ‘void solve(bool)’ at Main.cpp:416:38:
/usr/include/c++/12/bits/stl_pair.h:281:42: warning: ‘insertDir’ may be used uninitialized [-Wmaybe-uninitialized]
  281 |         : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y))
      |                                          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function ‘void solve(bool)’:
Main.cpp:334:18: note: ‘insertDir’ was declared here
  334 |             char insertDir;
      |                  ^~~~~~~~~

Judge Result