Submission #1174154


Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
int H, W, K, T;
int a[450], b[450], c[450], d[450];
P v[5] = {P(1, 0), P(0, 1), P(-1, 0), P(0, -1), P(0, 0)};
int state[2][30][30];
char howmove[10010][455];
int waittime = 4;


int iabs(int x){
  if(x > 0) return x;
  else return -x;
}
int distance(int i){
  return iabs(a[i]-c[i]) + iabs(b[i]-d[i]);
}

int move1(int L, int xmin, int xmax, int ymin, int ymax){
  int movenum = 0;

  for(int i = 0; i < H; i++) fill(state[1][i], state[1][i]+W, 0); //次のstateの初期化

  for(int i = 0; i < K; i++){
    movenum++;
    if(distance(i) > L / 5 + 1 && L/2 % 2 == 0 && (c[i] > xmin && c[i] < xmax) && (d[i] > ymin && d[i] < ymax)){
      if(a[i] > H/2 && a[i] < 29 && state[0][a[i]+1][b[i]] == 0 && state[1][a[i]+1][b[i]] == 0){
        howmove[L][i] = 'D';
        state[1][++a[i]][b[i]] = 1;
      }
      else if(a[i] < H/2 && a[i] > 0 && state[0][a[i]-1][b[i]] == 0 && state[1][a[i]-1][b[i]] == 0){
        howmove[L][i] = 'U';
        state[1][--a[i]][b[i]] = 1;
      }
      else if(b[i] > W / 2 && b[i] < 29 && state[0][a[i]][b[i]+1] == 0 && state[1][a[i]][b[i]+1] == 0){
        howmove[L][i] = 'R';
        state[1][a[i]][++b[i]] = 1;
      }
      else if(b[i] < W / 2 && b[i] > 0 && state[0][a[i]][b[i]-1] == 0 && state[1][a[i]][b[i]-1] == 0){
        howmove[L][i] = 'L';
        state[1][a[i]][--b[i]] = 1;
      }
      else{
        howmove[L][i] = '-';
        state[1][a[i]][b[i]] = 1;
        movenum--;
      }
    }
    else if(distance(i) > L / 5 + 1 && L/2 % 2 == 1 && (c[i] > xmin && c[i] < xmax) && (d[i] > ymin && d[i] < ymax)){
      if(b[i] > W / 2 && b[i] < 29 && state[0][a[i]][b[i]+1] == 0 && state[1][a[i]][b[i]+1] == 0){
        howmove[L][i] = 'R';
        state[1][a[i]][++b[i]] = 1;
      }
      else if(b[i] < W / 2 && b[i] > 0 && state[0][a[i]][b[i]-1] == 0 && state[1][a[i]][b[i]-1] == 0){
        howmove[L][i] = 'L';
        state[1][a[i]][--b[i]] = 1;
      }
      else if(a[i] > H/2 && a[i] < 29 && state[0][a[i]+1][b[i]] == 0 && state[1][a[i]+1][b[i]] == 0){
        howmove[L][i] = 'D';
        state[1][++a[i]][b[i]] = 1;
      }
      else if(a[i] < H/2 && a[i] > 0 && state[0][a[i]-1][b[i]] == 0 && state[1][a[i]-1][b[i]] == 0){
        howmove[L][i] = 'U';
        state[1][--a[i]][b[i]] = 1;
      }
      else{
        howmove[L][i] = '-';
        state[1][a[i]][b[i]] = 1;
        movenum--;
      }
    }
    else if(c[i] - a[i] > 0 && state[0][a[i]+1][b[i]] == 0 && state[1][a[i]+1][b[i]] == 0){
      howmove[L][i] = 'D';
      state[1][++a[i]][b[i]] = 1;
    }
    else if(c[i] - a[i] < 0 && state[0][a[i]-1][b[i]] == 0 && state[1][a[i]-1][b[i]] == 0){
      howmove[L][i] ='U';
      state[1][--a[i]][b[i]] = 1;
      }
    else if(d[i] - b[i] > 0 && state[0][a[i]][b[i]+1] == 0 && state[1][a[i]][b[i]+1] == 0){
      howmove[L][i] = 'R';
      state[1][a[i]][++b[i]] = 1;
      }
    else if(d[i] - b[i] < 0 && state[0][a[i]][b[i]-1] == 0 && state[1][a[i]][b[i]-1] == 0){
      howmove[L][i] = 'L';
      state[1][a[i]][--b[i]] = 1;
    }
    else{
      howmove[L][i] = '-';
      state[1][a[i]][b[i]] = 1;
      movenum--;
    }
  }
  return movenum;
}

int move2(int L, int xmin, int xmax, int ymin, int ymax){
  int movenum = 0;
  for(int i = 0; i < H; i++) fill(state[0][i], state[0][i]+W, 0); //次のstateの初期化

  for(int i = K-1; i >= 0; i--){
    movenum++;
    if(distance(i) > L / 5 + 1 && (c[i] > xmin && c[i] < xmax) && (d[i] > ymin && d[i] < ymax)){
      /*if(a[i] > H/2 && a[i] < 29 && state[0][a[i]+1][b[i]] == 0 && state[1][a[i]+1][b[i]] == 0){
        howmove[L][i] = 'D';
        state[0][++a[i]][b[i]] = 1;
      }
      else if(a[i] < H/2 && a[i] > 0 && state[0][a[i]-1][b[i]] == 0 && state[1][a[i]-1][b[i]] == 0){
        howmove[L][i] = 'U';
        state[0][--a[i]][b[i]] = 1;
      }
      else if(b[i] > W / 2 && b[i] < 29 && state[0][a[i]][b[i]+1] == 0 && state[1][a[i]][b[i]+1] == 0){
        howmove[L][i] = 'R';
        state[0][a[i]][++b[i]] = 1;
      }
      else if(b[i] < W / 2 && b[i] > 0 && state[0][a[i]][b[i]-1] == 0 && state[1][a[i]][b[i]-1] == 0){
        howmove[L][i] = 'L';
        state[0][a[i]][--b[i]] = 1;
      }*/
        howmove[L][i] = '-';
        state[0][a[i]][b[i]] = 1;
        movenum--;
    }
    else if(d[i] - b[i] > 0 && state[0][a[i]][b[i]+1] == 0 && state[1][a[i]][b[i]+1] == 0){
      howmove[L][i] = 'R';
      state[0][a[i]][++b[i]] = 1;
    }
    else if(d[i] - b[i] < 0 && state[0][a[i]][b[i]-1] == 0 && state[1][a[i]][b[i]] == 0){
      howmove[L][i] = 'L';
      state[0][a[i]][b[i]--] = 1;
    }
    else if(c[i] - a[i] > 0 && state[0][a[i]+1][b[i]] == 0 && state[1][a[i]+1][b[i]] == 0){
      howmove[L][i] = 'D';
      state[0][++a[i]][b[i]] = 1;
    }
    else if(c[i] - a[i] < 0 && state[0][a[i]-1][b[i]] == 0 && state[1][a[i]-1][b[i]] == 0){
      howmove[L][i] = 'U';
      state[0][--a[i]][b[i]] = 1;
    }
    else{
      howmove[L][i] = '-';
      state[0][a[i]][b[i]] = 1;
      movenum--;
    }
  }
  return movenum;
}


int main(){
  cin >> H >> W >> K >> T;
  for(int i = 0; i < H; i++){
    fill(state[0][i], state[0][i]+W, 0);
    fill(state[1][i], state[1][i]+W, 0);
  }
  for(int i = 0; i < K; i++){
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    a[i]--; b[i]--; c[i]--; d[i]--;
    state[1][a[i]][b[i]] = 1;
  }

  int L = 0;
  while(L < T){
    int movenum;
    L++;
    if(L % 2 == 0) movenum = move1(L, L/waittime, H-L/waittime-1, L/waittime, W-L/waittime-1);
    else movenum = move2(L, L/waittime, H-L/waittime-1, L/waittime, W-L/waittime-1);
    if(movenum == 0)  break;
    //cout << a[0] << " " << b[0] << "  " << a[1] << " " << b[1] << endl;
  }

  cout << L << endl;
  for(int i = 1; i <= L; i++){
    cout << howmove[i] << endl;
  }

  return 0;
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User bomac1
Language C++14 (GCC 5.4.1)
Score 4768
Code Size 6068 Byte
Status AC
Exec Time 4 ms
Memory 384 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 172 / 50000 153 / 50000 171 / 50000 164 / 50000 163 / 50000 159 / 50000 162 / 50000 141 / 50000 155 / 50000 151 / 50000 162 / 50000 159 / 50000 170 / 50000 145 / 50000 179 / 50000 160 / 50000 155 / 50000 160 / 50000 162 / 50000 158 / 50000 159 / 50000 169 / 50000 144 / 50000 146 / 50000 150 / 50000 169 / 50000 145 / 50000 159 / 50000 167 / 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 2 ms 384 KB
subtask_01_02.txt AC 3 ms 384 KB
subtask_01_03.txt AC 2 ms 384 KB
subtask_01_04.txt AC 2 ms 384 KB
subtask_01_05.txt AC 2 ms 384 KB
subtask_01_06.txt AC 4 ms 384 KB
subtask_01_07.txt AC 3 ms 384 KB
subtask_01_08.txt AC 3 ms 384 KB
subtask_01_09.txt AC 3 ms 384 KB
subtask_01_10.txt AC 2 ms 384 KB
subtask_01_11.txt AC 2 ms 256 KB
subtask_01_12.txt AC 3 ms 384 KB
subtask_01_13.txt AC 3 ms 384 KB
subtask_01_14.txt AC 3 ms 384 KB
subtask_01_15.txt AC 3 ms 384 KB
subtask_01_16.txt AC 3 ms 384 KB
subtask_01_17.txt AC 2 ms 384 KB
subtask_01_18.txt AC 2 ms 384 KB
subtask_01_19.txt AC 3 ms 384 KB
subtask_01_20.txt AC 3 ms 384 KB
subtask_01_21.txt AC 3 ms 384 KB
subtask_01_22.txt AC 2 ms 384 KB
subtask_01_23.txt AC 3 ms 384 KB
subtask_01_24.txt AC 3 ms 384 KB
subtask_01_25.txt AC 3 ms 384 KB
subtask_01_26.txt AC 2 ms 384 KB
subtask_01_27.txt AC 3 ms 384 KB
subtask_01_28.txt AC 2 ms 384 KB
subtask_01_29.txt AC 3 ms 384 KB
subtask_01_30.txt AC 2 ms 384 KB