Submission #1175101


Source Code Expand

#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <memory>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

int H,W,K,T;
struct state{
	int x, y;
	int tx, ty;
	int id;
	int exist;
	state(){
		x = -1, y = -1;
		tx = -1, ty = -1;
		id = -1;
		exist = 0;
	}
	state(int _x, int _y, int _id){
		x = _x, y = _y;
		id = _id;
		exist = 1;
	}
	// state operator=(const state& a){
	// 	x = a.x;	
	// 	y = a.y;	
	// 	id = a.id;	
	// 	exist = a.exist;
	// 	return state(*this);	
	// }
};

vector<vector<state>> table;
int tani[] = {32,16,8,4,2,2};
// int tani[] = {4, 2};
vint ttt = {300, 150, 120, 70, 50, 0};
// vint ttt = {70, 50};
vint bias = {10, 5, 5, 5, 5, 1};
vint bias2 = {60, 60, 60, 60, 60, 0};

int dist(int a, int b, int c, int d){
	return abs(a-c)+abs(b-d);
}

void d_set(int step){
	vint v(1,0);
	int p = tani[step];
	int t = p-1;
	while(t<32){
		v.PB(t);
		t+=p-1;
	}
	rep(i,H){
		rep(j,W){
			if(table[i][j].exist==0) continue;
			int tx = 0;
			int ty = 0;
			int x = table[i][j].x;
			int y = table[i][j].y;
			rep(i,v.size()){
				rep(j,v.size()){
					if(dist(x, y, tx, ty) > dist(x, y, v[i], v[j])){
						tx = v[i];
						ty = v[j];
					}
				}
			}
			table[i][j].tx = tx;
			table[i][j].ty = ty;
		}
	}
}

bool inside(int a, int b){
	return 0<=a&&a<30&&0<=b&&b<30;
}

int calc_score(){
	int ret = 0;
	rep(i,H){
		rep(j,W){
			if(table[i][j].exist==0) continue;
			ret += dist(i, j, table[i][j].tx, table[i][j].ty);
		}
	}
	return ret;
}

int calc_score2(int turn){
	int ret = 0;
	rep(i,H){
		rep(j,W){
			if(table[i][j].exist==0) continue;
			ret += dist(i, j, table[i][j].x, table[i][j].y);
		}
	}
	ret += 20;
	double t = 1e7 / (ret *( 10 + 0.01 * (turn+1)));
	return t;
}

int dd[] = {0,1,0,-1,0};
string sdd = "RDLU-";


void mainmain(){
	srand(time(NULL));
	cin>>H>>W>>K>>T;
	initvv(table, 30, 30);
	vector<string> ans;
	rep(i,K){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		a--,b--,c--,d--;
		table[a][b] = state(c, d, i);
	}
	int step = 0;
	d_set(step);
	set<int> kiri;
	int ttsum = 0;
	rep(i,ttt.size()){
		ttsum += ttt[i];
		kiri.insert(ttsum);
	}
	// kiri.insert(2500); // 16
	// kiri.insert(7500); // 8
	// kiri.insert(8750); // 4
	// kiri.insert(9350); // 2

	vint pre(5,INF);
	vint c_turn(1);
	vector<pii> tans;
	rep(turn, T){
		// if(kiri.find(turn)!=kiri.end()){
		// 	step++;
		// 	if(step==ttt.size()) break;
		// 	d_set(step);
		// }
		// cout<<turn<<" "<<step<<endl;
		c_turn.back()++;
		VV(state) next;
		initvv(next, H, W);
		vector<pair<int,pii>> tmp;
		rep(i,H){
			 rep(j,W){
			 	if(table[i][j].exist==0) continue;
			 	tmp.PB(mkp(dist(i, j, table[i][j].tx, table[i][j].ty), pii(i, j)));
			 }
		}
		sort(ALL(tmp));
		reverse(ALL(tmp));
		vint mov(K, 4);
		for(cauto a: tmp){
			vint b(4);
			rep(i,4) b[i] = i;
			random_shuffle(ALL(b));
			assert(table[a.S.F][a.S.S].exist);
			bool f = false;
			rep(i, 4){
				int nx = a.S.F + dd[b[i]];
				int ny = a.S.S + dd[b[i]+1];
				if(!inside(nx, ny)) continue;
				if(table[nx][ny].exist) continue;
				if(dist(nx, ny, table[a.S.F][a.S.S].tx, table[a.S.F][a.S.S].ty) < a.F){
					if(next[nx][ny].exist == 0){
						next[nx][ny] = table[a.S.F][a.S.S];
						assert(next[nx][ny].exist);
						mov[table[a.S.F][a.S.S].id] = b[i];
						f = true;
						// cout<<a.S.F<<" "<<a.S.S<<" "<<nx<<" "<<ny<<" "<<b[i]<<endl;
						// return;
						break;
					}
				}
			}
			if(!f){
				rep(i, 4){
					int nx = a.S.F + dd[b[i]];
					int ny = a.S.S + dd[b[i]+1];
					if(!inside(nx, ny)) continue;
					if(table[nx][ny].exist) continue;
					// double startTemp   =  100;
					// double endTemp     =   10;
					// int R = 1000;
					// double temp        = startTemp + (endTemp - startTemp) * turn / T;
					// double probability = exp(1 / temp);  // 最大化なので、分子はnextScore - currentScoreで良い。
					// bool FORCE_NEXT    = probability > (double)(rand() % R) / R;
					// bool FORCE_NEXT = rand() % T > turn / 500;
					if(dist(nx, ny, table[a.S.F][a.S.S].tx, table[a.S.F][a.S.S].ty) == 1+a.F && rand()%100 < bias2[step]){
						if(next[nx][ny].exist == 0){
							next[nx][ny] = table[a.S.F][a.S.S];
							assert(next[nx][ny].exist);
							mov[table[a.S.F][a.S.S].id] = b[i];
							f = true;
							// cout<<a.S.F<<" "<<a.S.S<<" "<<nx<<" "<<ny<<" "<<b[i]<<endl;
							// return;
							break;
						}
					}
				}	
			}
			if(!f){
				next[a.S.F][a.S.S] = table[a.S.F][a.S.S];
			}
		}
		// rep(i,H){
		// 	rep(j,W){
		// 		if(table[i][j].id == 2){
		// 			cout<<2<<" "<<i<<" "<<j<<endl;
		// 		}
		// 		if(table[i][j].id == 95){
		// 			cout<<95<<" "<<i<<" "<<j<<endl;
		// 		}
		// 	}
		// }
		// if(turn==1) break;
		ans.PB("");
		rep(i,K){
			// if(mov[i]!=4) update = true;
			ans.back()+=sdd[mov[i]];
		}
		table = next;
		int score = calc_score();
		bool update = false;
		int M = 0;
		rep(i,pre.size()){
			maxs(M, pre[i]);
		}
		if(score + bias[step] > M) update = true;
		// tans.PB(pii(calc_score2(turn),turn));
		if(update){
			step++;
			// cout<<"hoge"<<endl;
			if(step == ttt.size()) break;
			d_set(step);
			c_turn.PB(0);
			score = INF;
			pre = vint(pre.size(), INF);
		}
		pre.erase(pre.begin());
		pre.PB(score);
	}
	// sort(ALL(tans));
	// reverse(ALL(tans));
	// cout<<tans[0].S+1<<endl;
	cout<<ans.size()<<endl;
	rep(i,ans.size()){
		cout<<ans[i]<<endl;
	}
	// cout << tans[0].F << endl;
	// rep(i,c_turn.size()){
	// 	cout<<c_turn[i]<<endl;
	// }
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User j_gui0121
Language C++14 (GCC 5.4.1)
Score 231330
Code Size 7676 Byte
Status AC
Exec Time 76 ms
Memory 896 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 7425 / 50000 4832 / 50000 7057 / 50000 7265 / 50000 9507 / 50000 12074 / 50000 7648 / 50000 5153 / 50000 8087 / 50000 10644 / 50000 11032 / 50000 7810 / 50000 10572 / 50000 5984 / 50000 11513 / 50000 9332 / 50000 5872 / 50000 6512 / 50000 3972 / 50000 9951 / 50000 5258 / 50000 12852 / 50000 7921 / 50000 3001 / 50000 3779 / 50000 10496 / 50000 5963 / 50000 6958 / 50000 5116 / 50000 7744 / 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 55 ms 768 KB
subtask_01_02.txt AC 64 ms 768 KB
subtask_01_03.txt AC 62 ms 768 KB
subtask_01_04.txt AC 60 ms 768 KB
subtask_01_05.txt AC 59 ms 768 KB
subtask_01_06.txt AC 63 ms 768 KB
subtask_01_07.txt AC 66 ms 768 KB
subtask_01_08.txt AC 65 ms 768 KB
subtask_01_09.txt AC 67 ms 768 KB
subtask_01_10.txt AC 62 ms 768 KB
subtask_01_11.txt AC 64 ms 768 KB
subtask_01_12.txt AC 67 ms 768 KB
subtask_01_13.txt AC 63 ms 768 KB
subtask_01_14.txt AC 62 ms 768 KB
subtask_01_15.txt AC 57 ms 768 KB
subtask_01_16.txt AC 63 ms 768 KB
subtask_01_17.txt AC 68 ms 768 KB
subtask_01_18.txt AC 67 ms 768 KB
subtask_01_19.txt AC 64 ms 768 KB
subtask_01_20.txt AC 66 ms 768 KB
subtask_01_21.txt AC 57 ms 768 KB
subtask_01_22.txt AC 61 ms 768 KB
subtask_01_23.txt AC 64 ms 768 KB
subtask_01_24.txt AC 65 ms 768 KB
subtask_01_25.txt AC 63 ms 768 KB
subtask_01_26.txt AC 76 ms 896 KB
subtask_01_27.txt AC 67 ms 896 KB
subtask_01_28.txt AC 67 ms 896 KB
subtask_01_29.txt AC 60 ms 768 KB
subtask_01_30.txt AC 60 ms 768 KB