Submission #1173246


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int vy[] = {-1, 0, 1, 0}, vx[] = {0, 1, 0, -1};
const string vv = "URDL";


int H, W, K, T, A[450], B[450], C[450], D[450];

bool isover(int y, int x)
{
  return (y < 0 || y >= H || x < 0 || x >= W);
}

int getCost(int y, int x, int id)
{
  return (abs(y - C[id]) + abs(x - D[id]));
}


struct State
{
  int mas[30][30];
  vector< string > dd;
  int score;

  State()
  {
    memset(mas, -1, sizeof(mas));
  }

  int getScore()
  {
    int Pd = 20;
    for(int i = 0; i < H; i++) {
      for(int j = 0; j < W; j++) {
        if(~mas[i][j]) Pd += abs(C[mas[i][j]] - i) + abs(D[mas[i][j]] - j);
      }
    }
    double Pt = 10 + (int) dd.back().size() * 0.01;
    return ((int) ceil(10000000 / (Pd * Pt)));
  }


};

int main()
{
  cin >> H >> W >> K >> T;

  int S[500][500];
  memset(S, -1, sizeof(S));

  for(int i = 0; i < K; i++) {
    cin >> A[i] >> B[i] >> C[i] >> D[i];
    --A[i], --B[i], --C[i], --D[i];
    S[A[i]][B[i]] = i;
  }

  int lim = 25;
  char dd[lim][450];

  for(int i = 0; i < lim; i++) {
    int T[500][500];
    memset(T, -1, sizeof(T));

    for(int j = 0; j < H; j++) {
      for(int k = 0; k < W; k++) {
        if(~S[j][k]) {
          char flop = '-';
          int id = S[j][k];

          for(int l = 0; l < 4; l++) {
            int ny = j + vy[l], nx = k + vx[l];
            if(isover(ny, nx)) continue;

            int predist = getCost(j, k, id);
            int curdist = getCost(ny, nx, id);

            if(predist > curdist && T[ny][nx] == -1 && S[ny][nx] == -1) {
              T[ny][nx] = id;
              flop = vv[l];
              break;
            }
          }

          if(flop == '-') T[j][k] = id;
          dd[i][id] = flop;
        }
      }
    }
    swap(S, T);
  }

  cout << lim << endl;
  for(int i = 0; i < lim; i++) {
    for(int j = 0; j < K; j++) cout << dd[i][j];
    cout << endl;
  }
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User ei13333
Language C++14 (GCC 5.4.1)
Score 4617
Code Size 2008 Byte
Status AC
Exec Time 31 ms
Memory 2176 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 159 / 50000 159 / 50000 154 / 50000 159 / 50000 171 / 50000 152 / 50000 153 / 50000 163 / 50000 145 / 50000 152 / 50000 162 / 50000 150 / 50000 149 / 50000 161 / 50000 148 / 50000 162 / 50000 151 / 50000 150 / 50000 154 / 50000 153 / 50000 162 / 50000 149 / 50000 151 / 50000 146 / 50000 147 / 50000 155 / 50000 156 / 50000 140 / 50000 152 / 50000 152 / 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 9 ms 2176 KB
subtask_01_02.txt AC 9 ms 2176 KB
subtask_01_03.txt AC 9 ms 2176 KB
subtask_01_04.txt AC 9 ms 2176 KB
subtask_01_05.txt AC 9 ms 2176 KB
subtask_01_06.txt AC 9 ms 2176 KB
subtask_01_07.txt AC 9 ms 2176 KB
subtask_01_08.txt AC 9 ms 2176 KB
subtask_01_09.txt AC 9 ms 2176 KB
subtask_01_10.txt AC 9 ms 2176 KB
subtask_01_11.txt AC 9 ms 2176 KB
subtask_01_12.txt AC 9 ms 2176 KB
subtask_01_13.txt AC 9 ms 2176 KB
subtask_01_14.txt AC 9 ms 2176 KB
subtask_01_15.txt AC 9 ms 2176 KB
subtask_01_16.txt AC 9 ms 2176 KB
subtask_01_17.txt AC 9 ms 2176 KB
subtask_01_18.txt AC 9 ms 2176 KB
subtask_01_19.txt AC 9 ms 2176 KB
subtask_01_20.txt AC 9 ms 2176 KB
subtask_01_21.txt AC 9 ms 2176 KB
subtask_01_22.txt AC 9 ms 2176 KB
subtask_01_23.txt AC 9 ms 2176 KB
subtask_01_24.txt AC 9 ms 2176 KB
subtask_01_25.txt AC 31 ms 2176 KB
subtask_01_26.txt AC 9 ms 2176 KB
subtask_01_27.txt AC 9 ms 2176 KB
subtask_01_28.txt AC 9 ms 2176 KB
subtask_01_29.txt AC 9 ms 2176 KB
subtask_01_30.txt AC 9 ms 2176 KB