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 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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 |