Submission #1175164


Source Code Expand

#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

#ifdef _WIN32
#include <Windows.h>
#else
#include <sys/time.h>
#endif

class TicToc
{
private:
    double getCurrTime(){
    #ifdef _WIN32
        return GetTickCount() * 1e-3;
    #else
        struct timeval tv;
        gettimeofday(&tv, NULL);
        return tv.tv_sec + tv.tv_usec * 1e-6;
    #endif
    }
    double startTime;
public:
    void tic(){
        startTime = getCurrTime();
    }
    double toc(){
        return getCurrTime() - startTime;
    }
};

unsigned xor128(){
    static unsigned x=123456789,y=362436069,z=521288629,w=88675123;
    unsigned t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

void shuffle(vector<int>& v)
{
    int n = v.size();
    for(int i=0; i<n; ++i){
        int j = i + xor128() % (n - i);
        swap(v[i], v[j]);
    }
}

double getScore(const vector<int>& gy, const vector<int>& gx, const vector<int>& y, const vector<int>& x, int l)
{
    int n = gy.size();
    int pd = 20;
    for(int i=0; i<n; ++i)
        pd += abs(gy[i] - y[i]) + abs(gx[i] - x[i]);

    double pt = 10 + l * 0.01;
    double score = 1.0e7 / (pd * pt);
    return score;
}

const int dy[] = {-1, 1, 0, 0};
const int dx[] = {0, 0, -1, 1};
const string ds = "UDLR";

int main()
{
    int h, w, n, maxTurn;
    cin >> h >> w >> n >> maxTurn;
    maxTurn = min(maxTurn, 1500);

    vector<int> sy(n), sx(n), gy(n), gx(n);
    for(int i=0; i<n; ++i){
        cin >> sy[i] >> sx[i] >> gy[i] >> gx[i];
        -- sy[i];
        -- sx[i];
        -- gy[i];
        -- gx[i];
    }

    double allBestScore = 0.0;
    vector<string> ans;
    TicToc tictoc;
    tictoc.tic();
    while(tictoc.toc() < 3.5){
        vector<int> y = sy;
        vector<int> x = sx;
        vector<vector<int> > pos(h, vector<int>(w, 0));
        for(int i=0; i<n; ++i)
            pos[sy[i]][sx[i]] = 1;

        vector<string> act(maxTurn, string(n, '-'));
        vector<int> index(n);
        vector<int> d(4);
        for(int i=0; i<n; ++i)
            index[i] = i;
        for(int i=0; i<4; ++i)
            d[i] = i;

        int bestTurn = 0;
        double bestScore = getScore(gy, gx, y, x, 0);
        string lastAct;
        for(int turn=1; turn<=maxTurn; ++turn){
            shuffle(index);

            vector<int> yy = y;
            vector<int> xx = x;
            vector<vector<int> > pos2 = pos;
            string act2(n, '-');
            for(int i : index){
                shuffle(d);
                for(int k : d){
                    int y2 = yy[i] + dy[k];
                    int x2 = xx[i] + dx[k];
                    if(!(0 <= y2 && y2 < h && 0 <= x2 && x2 < w))
                        continue;
                    if(pos2[y2][x2] >= turn)
                        continue;
                    if(abs(gy[i] - y2) + abs(gx[i] - x2) < abs(gy[i] - yy[i]) + abs(gx[i] - xx[i])){
                        act2[i] = ds[k];
                        yy[i] = y2;
                        xx[i] = x2;
                        break;
                    }
                }
                pos2[yy[i]][xx[i]] = turn + 1;
            }

            double score = getScore(gy, gx, yy, xx, turn);
            if(bestScore < score){
                bestTurn = turn;
                bestScore = score;
                lastAct = act2;
            }

            for(int i : index){
                shuffle(d);
                bool isMove = false;
                for(int k : d){
                    int y2 = y[i] + dy[k];
                    int x2 = x[i] + dx[k];
                    if(!(0 <= y2 && y2 < h && 0 <= x2 && x2 < w))
                        continue;
                    if(pos[y2][x2] >= turn)
                        continue;
                    if(abs(gy[i] - y2) + abs(gx[i] - x2) < abs(gy[i] - y[i]) + abs(gx[i] - x[i])){
                        act[turn-1][i] = ds[k];
                        y[i] = y2;
                        x[i] = x2;
                        isMove = true;
                        break;
                    }
                }

                if(!isMove && xor128() % 100 < (100 - turn / 8)){ /*遠ざかる方向にも移動 */
                    shuffle(d);
                    for(int k : d){
                        int y2 = y[i] + dy[k];
                        int x2 = x[i] + dx[k];
                        if(!(0 <= y2 && y2 < h && 0 <= x2 && x2 < w))
                            continue;
                        if(pos[y2][x2] >= turn)
                            continue;
                        act[turn-1][i] = ds[k];
                        y[i] = y2;
                        x[i] = x2;
                        break;
                    }
                }

                pos[y[i]][x[i]] = turn + 1;
            }
        }

        if(allBestScore < bestScore){
            allBestScore = bestScore;
            act.resize(bestTurn);
            act.back() = lastAct;
            ans.swap(act);
        }

        cerr << tictoc.toc() << endl;
    }

    cout << ans.size() << endl;
    for(const string& s : ans)
        cout << s << endl;

    return 0;
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User mamekin
Language C++14 (GCC 5.4.1)
Score 395736
Code Size 5713 Byte
Status AC
Exec Time 3612 ms
Memory 2256 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 21560 / 50000 29586 / 50000 29138 / 50000 20784 / 50000 2808 / 50000 28852 / 50000 3229 / 50000 21622 / 50000 5443 / 50000 12706 / 50000 28869 / 50000 20167 / 50000 4318 / 50000 29087 / 50000 3463 / 50000 26691 / 50000 10958 / 50000 4833 / 50000 1648 / 50000 5609 / 50000 2499 / 50000 14099 / 50000 1804 / 50000 1287 / 50000 2268 / 50000 25850 / 50000 2742 / 50000 1481 / 50000 9503 / 50000 22832 / 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 3591 ms 1468 KB
subtask_01_02.txt AC 3506 ms 1412 KB
subtask_01_03.txt AC 3612 ms 1428 KB
subtask_01_04.txt AC 3597 ms 1456 KB
subtask_01_05.txt AC 3553 ms 1644 KB
subtask_01_06.txt AC 3541 ms 1452 KB
subtask_01_07.txt AC 3528 ms 1664 KB
subtask_01_08.txt AC 3608 ms 1432 KB
subtask_01_09.txt AC 3578 ms 1632 KB
subtask_01_10.txt AC 3561 ms 1620 KB
subtask_01_11.txt AC 3608 ms 1448 KB
subtask_01_12.txt AC 3585 ms 1512 KB
subtask_01_13.txt AC 3550 ms 1664 KB
subtask_01_14.txt AC 3595 ms 1424 KB
subtask_01_15.txt AC 3563 ms 1664 KB
subtask_01_16.txt AC 3576 ms 1448 KB
subtask_01_17.txt AC 3550 ms 1628 KB
subtask_01_18.txt AC 3555 ms 1660 KB
subtask_01_19.txt AC 3505 ms 1812 KB
subtask_01_20.txt AC 3575 ms 1632 KB
subtask_01_21.txt AC 3601 ms 1548 KB
subtask_01_22.txt AC 3561 ms 1440 KB
subtask_01_23.txt AC 3596 ms 1724 KB
subtask_01_24.txt AC 3587 ms 2256 KB
subtask_01_25.txt AC 3569 ms 1664 KB
subtask_01_26.txt AC 3596 ms 1444 KB
subtask_01_27.txt AC 3579 ms 1504 KB
subtask_01_28.txt AC 3526 ms 1696 KB
subtask_01_29.txt AC 3557 ms 1688 KB
subtask_01_30.txt AC 3587 ms 1448 KB