Submission #1173397


Source Code Expand

#include <bits/stdc++.h>
 
using namespace std;
 
const int vy[] = {-1, 0, 1, 0, 0}, vx[] = {0, 1, 0, -1, 0};
const string vv = "URDL-";
const int lim = 1000;
 
int H, W, K, T, A[450], B[450], C[450], D[450];
vector< pair< int, int > > vs;

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 S[30][30];
  int line;
  int score;
  vector< vector< char > > dd;

  void init()
  {
    memset(S, -1, sizeof(S));
  }
  
  int getScore()
  {
    int Pd = 20;
    for(int i = 0; i < H; i++) {
      for(int j = 0; j < W; j++) {
        if(~S[i][j]) Pd += abs(C[S[i][j]] - i) + abs(D[S[i][j]] - j);
      }
    }
    double Pt = 10 + (int) line * 0.01;
    return ((int) ceil(10000000 / (Pd * Pt)));
  }
 
  void Simulate()
  {
    dd.push_back(vector< char >(K));
    
    int T[30][30];
    memset(T, -1, sizeof(T));
    random_shuffle(begin(vs), end(vs));
    for(auto& pp : vs) {
      int j = pp.first;
      int k = pp.second;
      if(~S[j][k]) {
        char flop = '-';
        int id = S[j][k];
        int smallest = 114514;
        for(int l = 0; l < 4; l++) {
          int ny = j + vy[l], nx = k + vx[l];
          if(isover(ny, nx)) continue;
          int curdist = getCost(ny, nx, id);
          if(curdist - getCost(j, k, id) == 2) continue;
          if(T[ny][nx] == -1 && S[ny][nx] == -1) smallest = min(smallest, curdist);
        }
        vector< int > ch;
        for(int l = 0; l < 4; l++) {
          int ny = j + vy[l], nx = k + vx[l];
          if(isover(ny, nx)) continue;
          int curdist = getCost(ny, nx, id);
          if(T[ny][nx] == -1 && S[ny][nx] == -1 && smallest == curdist) ch.push_back(l);
        }
        if(!ch.empty()) flop = vv[ch[rand() % ch.size()]];
        
        int dir = vv.find(flop);
        T[j + vy[dir]][k + vx[dir]] = id;
        dd[line][id] = flop;
      }
    }
    swap(S, T);
    
    ++line;
    score = getScore();
  }

  void dump()
  {
    cerr << score << endl;
    
    cout << line << endl;
    for(int i = 0; i < line; i++) {
      for(int j = 0; j < K; j++) cout << dd[i][j];
      cout << endl;
    }
  }

  bool operator<(const State& s) const
  {
    return(score < s.score);
  }
  
};

State beststate;

void Beam(State now_state)
{

  priority_queue< State > now_q[lim + 1];
  now_q[0].emplace(now_state);

  time_t start = clock();
  while((clock() - start) / CLOCKS_PER_SEC < 1) {
    for(int tern = 0; tern < lim; tern++) {
      if(!now_q[tern].empty()) {
        State state = now_q[tern].top();
        now_q[tern].pop();
        if(state.score > beststate.score) beststate = state;
        for(int j = 0; j < 3; j++) {
          State nextstate = state;
          nextstate.Simulate();
          now_q[tern + 1].emplace(nextstate);
        }
      }
    }
  }
}

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

  for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) vs.emplace_back(i, j);
  
  State now_state;
  now_state.init();
  
  for(int i = 0; i < K; i++) {
    cin >> A[i] >> B[i] >> C[i] >> D[i];
    --A[i], --B[i], --C[i], --D[i];
    now_state.S[A[i]][B[i]] = i;
  }
  
  Beam(now_state);
  beststate.dump();
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User ei13333
Language C++14 (GCC 5.4.1)
Score 32248
Code Size 3385 Byte
Status AC
Exec Time 1887 ms
Memory 981216 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 1154 / 50000 1162 / 50000 1152 / 50000 1049 / 50000 981 / 50000 1154 / 50000 1009 / 50000 1056 / 50000 1054 / 50000 1120 / 50000 1144 / 50000 1158 / 50000 1111 / 50000 1155 / 50000 1074 / 50000 1072 / 50000 1004 / 50000 1065 / 50000 954 / 50000 1128 / 50000 966 / 50000 1116 / 50000 1047 / 50000 945 / 50000 1001 / 50000 1176 / 50000 1094 / 50000 971 / 50000 1034 / 50000 1142 / 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 1868 ms 981216 KB
subtask_01_02.txt AC 1881 ms 980696 KB
subtask_01_03.txt AC 1839 ms 980572 KB
subtask_01_04.txt AC 1870 ms 980640 KB
subtask_01_05.txt AC 1868 ms 980832 KB
subtask_01_06.txt AC 1871 ms 980708 KB
subtask_01_07.txt AC 1871 ms 980760 KB
subtask_01_08.txt AC 1867 ms 980756 KB
subtask_01_09.txt AC 1874 ms 980668 KB
subtask_01_10.txt AC 1871 ms 980812 KB
subtask_01_11.txt AC 1876 ms 980740 KB
subtask_01_12.txt AC 1865 ms 980788 KB
subtask_01_13.txt AC 1884 ms 980800 KB
subtask_01_14.txt AC 1887 ms 980760 KB
subtask_01_15.txt AC 1871 ms 980848 KB
subtask_01_16.txt AC 1865 ms 980788 KB
subtask_01_17.txt AC 1866 ms 980852 KB
subtask_01_18.txt AC 1865 ms 980832 KB
subtask_01_19.txt AC 1868 ms 980760 KB
subtask_01_20.txt AC 1853 ms 980728 KB
subtask_01_21.txt AC 1873 ms 980752 KB
subtask_01_22.txt AC 1873 ms 980784 KB
subtask_01_23.txt AC 1871 ms 980828 KB
subtask_01_24.txt AC 1861 ms 980808 KB
subtask_01_25.txt AC 1878 ms 980772 KB
subtask_01_26.txt AC 1871 ms 980668 KB
subtask_01_27.txt AC 1874 ms 980676 KB
subtask_01_28.txt AC 1864 ms 980872 KB
subtask_01_29.txt AC 1874 ms 980720 KB
subtask_01_30.txt AC 1869 ms 980696 KB