Submission #1185354


Source Code Expand

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <functional>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <stack>
#include <random>
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;
typedef long long int ll;
const ll  MOD = 1000000007;
typedef pair<ll,ll> P;

ll H,W,K,T;
ll A[1000],B[1000],C[1000],D[1000];
vector<string> ans;
ll move_dir[1000];
string dir="UDLR-";
ll field[1000][1000];
ll d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
bool reserved[1000][1000];
ll dontmove_count = 0;

vector<ll> now_moving;

random_device rnd;
mt19937 mt(rnd());

double score = 0;
ll score_pos = 0;

double score_count(ll L){
  double Pd = 20;
  double Pt = 10+L*0.01;
  rep(i,K){
    Pd += abs(A[i]-C[i]) + abs(B[i]-D[i]);
  }
  double s = 10000000/(Pd*Pt);
  return s;
}
bool is_inside(ll y,ll x){
  if(y<=0 || y > H || x<=0 || x > W){
    return false;
  }
  return true;
}
bool is_spaced(ll y,ll x){
  if(field[y][x] > 0){
    return false;
  }
  if(reserved[y][x]){
    return false;
  }
  return true;
}
bool is_regal(ll y,ll x){
  if(is_inside(y,x) && is_spaced(y,x)){
    return true;
  }
  return false;
}
ll eval(ll nowpos ,ll y , ll x){
  // kyori
  ll score = 0;
  //if(min(x,y)%2 == 1) score+=100;
  score += max(10000*(W/2-min(x,W-x)),10000*(H/2-min(y,H-y)));
  score += min(100*(W/2-min(x,W-x)),100*(H/2-min(y,H-y)));
  /*
     if(x < 4) score += 10000*(5-x);
     if(y < 4) score += 10000*(5-y);
     if(x > W-3) score += 10000*(5-(W-x));
     if(y > H-3) score += 10000*(5-(H-y));
   */
  return score;
}
int main(){
  cin >> H >> W >> K >> T;
  rep(i,K){
    cin >> A[i] >> B[i] >> C[i] >> D[i];
    field[A[i]][B[i]] = i+1;
  }

  rep(r,T){
    rep(i,H+1){
      rep(j,W+1){
        reserved[i][j] = false;
      }
    }
    dontmove_count = 0;
    if(r%10>6 && r % 60 < 50 && r<=800){
      rep(i,K){
        ll d_score[4] = {0};
        ll y_diff = A[i]-C[i];
        ll x_diff = B[i]-D[i];
        move_dir[i] = 4;
        //if(abs(x_diff) + abs(y_diff)<= 1)continue;
        //if(abs(x_diff) + abs(y_diff) >= 15) continue;

        rep(j,4){
          ll y_ = A[i] + d[j][0];
          ll x_ = B[i] + d[j][1];
          d_score[j] = eval(i,y_,x_);
          if(abs(x_diff) + abs(y_diff)<= 2){
            d_score[j] = mt() % 100;
          }

        }
        rep(j,4){
          ll tmp_max = eval(i,A[i],B[i]);
          if(abs(x_diff) + abs(y_diff)<= 2){
            tmp_max = mt() % 100;
          }
          ll mem = 4;
          rep(k,4){
            if(d_score[k] > tmp_max){
              tmp_max = d_score[k];
              mem = k;
            }
          }
          ll y_ = A[i] + d[mem][0];
          ll x_ = B[i] + d[mem][1];
          d_score[mem] = -1001001001;
          if(is_regal(y_,x_)){
            move_dir[i] = mem;
            reserved[y_][x_] = true;
            break;
          }
        }
        if(move_dir[i] == 4){
          reserved[A[i]][B[i]] = true;
        }
      }
    }
    if(r%10<=6 && r%60 < 50){
      rep(i,K){
        /*
           if(B[i] < 7 || A[i] < 7 || B[i] > W-6 || A[i] > H-6){
           move_dir[i] = 4;
           continue;
           }
         */
        ll y_diff = A[i]-C[i];
        ll x_diff = B[i]-D[i];
        if(y_diff > 0 && is_regal(A[i]-1,B[i])){//U
          move_dir[i] = 0;
          reserved[A[i]-1][B[i]] = true;
        }
        else if(y_diff < 0 && is_regal(A[i]+1,B[i])){//D
          move_dir[i] = 1;
          reserved[A[i]+1][B[i]] = true;
        }
        else if(x_diff > 0 && is_regal(A[i],B[i]-1)){//L
          move_dir[i] = 2;
          reserved[A[i]][B[i]-1] = true;
        }
        else if(x_diff < 0 && is_regal(A[i],B[i]+1)){//R
          move_dir[i] = 3;
          reserved[A[i]][B[i]+1] = true;
        }
        else if(mt()%10 == 0 && abs(x_diff) + abs(y_diff) > 0){
          move_dir[i] = 4;
          rep(j,4){
            ll y_ = A[i] + d[j][0];
            ll x_ = B[i] + d[j][1];
            if(is_regal(y_,x_)){
              move_dir[i] = j;
              reserved[y_][x_] = true;
              break;
            }
          }
          if(move_dir[i] == 4 )dontmove_count++;
        }
        else{
          move_dir[i] = 4;
          dontmove_count++;
        }
      }
    }
    if(r % 60 >= 50 ||(r%10>6 && r % 60 < 50 && r>800)){
      rep(i,K){
        ll d_score[4] = {0};
        ll y_diff = A[i]-C[i];
        ll x_diff = B[i]-D[i];
        move_dir[i] = 4;
        ll aaa = 30;
        if(r > 1000){
          aaa = 0;
        }
        //if(abs(x_diff) + abs(y_diff)<= 2)continue;
        if(mt()%4 < 3 && abs(x_diff) + abs(y_diff) > aaa){
          if(y_diff > 0 && is_regal(A[i]-1,B[i])){//U
            move_dir[i] = 0;
            reserved[A[i]-1][B[i]] = true;
          }
          else if(y_diff < 0 && is_regal(A[i]+1,B[i])){//D
            move_dir[i] = 1;
            reserved[A[i]+1][B[i]] = true;
          }
          else if(x_diff > 0 && is_regal(A[i],B[i]-1)){//L
            move_dir[i] = 2;
            reserved[A[i]][B[i]-1] = true;
          }
          else if(x_diff < 0 && is_regal(A[i],B[i]+1)){//R
            move_dir[i] = 3;
            reserved[A[i]][B[i]+1] = true;
          }
          else{
            move_dir[i] = 4;
            dontmove_count++;
          }
        }
        else{

          rep(j,4){
            d_score[j] = mt() % 100;
          }
          rep(j,4){
            ll tmp_max = mt()%100;
            ll mem = 4;
            rep(k,4){
              if(d_score[k] > tmp_max){
                tmp_max = d_score[k];
                mem = k;
              }
            }
            ll y_ = A[i] + d[mem][0];
            ll x_ = B[i] + d[mem][1];
            d_score[mem] = -1001001001;
            if(is_regal(y_,x_)){
              move_dir[i] = mem;
              reserved[y_][x_] = true;
              break;
            }
          }
          if(move_dir[i] == 4){
            reserved[A[i]][B[i]] = true;
          }
        }
      }


    }
    string tmp;
    rep(i,K){
      /*
         if(move_dir[i] < 4 && mt() % 3 > 0){
         move_dir[i] = 4;
         dontmove_count++;
         }
       */
      tmp += dir[move_dir[i]];
      if(move_dir[i] < 4){
        field[A[i]][B[i]] = 0;
        A[i] += d[move_dir[i]][0];
        B[i] += d[move_dir[i]][1];
        field[A[i]][B[i]] = i+1;
      }
    }
    ans.push_back(tmp);
    double tmp_score = score_count(r+1);
    if(tmp_score > score){
      score_pos = r+1;
      score = tmp_score;
    }
    /*
       if(r > 1000){
       break;
       }
     */
  }
  //score_pos = 200;
  ll l = score_pos;
  cout << l << endl;
  rep(i,l){
    cout << ans[i] << endl;
  }
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User gamelove765
Language C++14 (GCC 5.4.1)
Score 169345
Code Size 6973 Byte
Status AC
Exec Time 263 ms
Memory 8448 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 6096 / 50000 5572 / 50000 7517 / 50000 3979 / 50000 6401 / 50000 5302 / 50000 5221 / 50000 6544 / 50000 7695 / 50000 5778 / 50000 4932 / 50000 6154 / 50000 5377 / 50000 4881 / 50000 3949 / 50000 5884 / 50000 6003 / 50000 3877 / 50000 7921 / 50000 5492 / 50000 5938 / 50000 5514 / 50000 6532 / 50000 5222 / 50000 6216 / 50000 6296 / 50000 4945 / 50000 5847 / 50000 4606 / 50000 3654 / 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 253 ms 6784 KB
subtask_01_02.txt AC 257 ms 6912 KB
subtask_01_03.txt AC 253 ms 6784 KB
subtask_01_04.txt AC 256 ms 6656 KB
subtask_01_05.txt AC 259 ms 7552 KB
subtask_01_06.txt AC 254 ms 6656 KB
subtask_01_07.txt AC 258 ms 7424 KB
subtask_01_08.txt AC 256 ms 6656 KB
subtask_01_09.txt AC 256 ms 6656 KB
subtask_01_10.txt AC 255 ms 6784 KB
subtask_01_11.txt AC 255 ms 7168 KB
subtask_01_12.txt AC 254 ms 6912 KB
subtask_01_13.txt AC 260 ms 7424 KB
subtask_01_14.txt AC 257 ms 6784 KB
subtask_01_15.txt AC 263 ms 8448 KB
subtask_01_16.txt AC 253 ms 6656 KB
subtask_01_17.txt AC 256 ms 6912 KB
subtask_01_18.txt AC 259 ms 7424 KB
subtask_01_19.txt AC 256 ms 6912 KB
subtask_01_20.txt AC 255 ms 6912 KB
subtask_01_21.txt AC 258 ms 7296 KB
subtask_01_22.txt AC 255 ms 6912 KB
subtask_01_23.txt AC 255 ms 7168 KB
subtask_01_24.txt AC 258 ms 7424 KB
subtask_01_25.txt AC 255 ms 6656 KB
subtask_01_26.txt AC 253 ms 6656 KB
subtask_01_27.txt AC 260 ms 7936 KB
subtask_01_28.txt AC 257 ms 7552 KB
subtask_01_29.txt AC 255 ms 6784 KB
subtask_01_30.txt AC 259 ms 7424 KB