Submission #1173930

---

Source Code Expand

#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<vector>
#include<random>
using namespace std;
using uint = unsigned int;
using ll = long long;
const int M = 1e9 + 7;
const ll MLL = 1e18L + 9;
#pragma unused(M)
#pragma unused(MLL)
#ifdef LOCAL
#include"rprint.hpp"
#else
template <class... T> void printl(T&&...){ }
template <class... T> void printc(T&&...){ }
template <class... T> void prints(T&&...){ }
template <class... T> void printd(T&&...){ }
#endif

int main(){
    random_device rd;
    mt19937 mt(rd());
    int h, w, k, t;
    cin >> h >> w >> k >> t;
    vector<vector<int>> board(h, vector<int> (w));
    vector<pair<int, int>> abs(k), cds(k);
    for(int i=0;i<k;i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        a--; b--; c--; d--;
        abs[i] = {a, b};
        cds[i] = {c, d};
        board[a][b] = 1;
    }
    int ss = 0;
    string out;
    for(int i=0;i<t;i++){
        vector<pair<int, int>> poss = abs;
        int cnt = 0;
        if(ss % 2){
            for(int i=0;i<k;i++){
                bool done = false;
                if(mt() % 100 < 20){
                    int y = abs[i].first, x = abs[i].second;
                    vector<int> four(4);
                    iota(four.begin(), four.end(), 0);
                    shuffle(four.begin(), four.end(), mt);
                    for(int jj=0;jj<4;jj++){
                        int j = four[jj];
                        int ny = y + (j == 0 ? 1 : j == 1 ? -1 : 0), nx = x + (j == 2 ? 1 : j == 3 ? -1 : 0);
                        if(0 <= ny && ny < h && 0 <= nx && nx < w && !board[ny][nx]){
                            out += (j == 0 ? 'D' : j == 1 ? 'U' : j == 2 ? 'R' : 'L');
                            board[ny][nx] = 1;
                            abs[i] = {ny, nx};
                            done = true;
                            break;
                        }
                    }
                }
                if(!done){
                    out += '-';
                    poss[i] = {-1, -1};
                }
            }
            ss++;
        }else{
            for(int i=0;i<k;i++){
                int y = abs[i].first, x = abs[i].second;
                if(y < cds[i].first){
                    int ny = y + 1, nx = x;
                    if(0 <= ny && ny < h && 0 <= nx && nx < w && !board[ny][nx]){
                        out += 'D';
                        board[ny][nx] = 1;
                        abs[i] = {ny, nx};
                        continue;
                    }
                }
                if(y > cds[i].first){
                    int ny = y - 1, nx = x;
                    if(0 <= ny && ny < h && 0 <= nx && nx < w && !board[ny][nx]){
                        out += 'U';
                        board[ny][nx] = 1;
                        abs[i] = {ny, nx};
                        continue;
                    }
                }
                if(x < cds[i].second){
                    int ny = y, nx = x + 1;
                    if(0 <= ny && ny < h && 0 <= nx && nx < w && !board[ny][nx]){
                        out += 'R';
                        board[ny][nx] = 1;
                        abs[i] = {ny, nx};
                        continue;
                    }
                }
                if(x > cds[i].second){
                    int ny = y, nx = x - 1;
                    if(0 <= ny && ny < h && 0 <= nx && nx < w && !board[ny][nx]){
                        out += 'L';
                        board[ny][nx] = 1;
                        abs[i] = {ny, nx};
                        continue;
                    }
                }
                out += '-';
                poss[i] = {-1, -1};
                cnt++;
            }
        }
        out += '\n';
        if(cnt == k){
            if(i > t - 100){
                cout << i + 1 << '\n';
                cout << out << endl;
                return 0;
            }
            ss++;
        }
        // prints(board);
        for(int i=0;i<k;i++){
            if(poss[i].first != -1){
                board[poss[i].first][poss[i].second] = 0;
            }
        }
        // prints(board);
        // prints(abs);
    }
    return 0;
}

Submission Info

Judge Result