Submission #1173887
Source Code Expand
#include <iostream>
#include <sstream>
#include <string>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <tuple>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
struct State {
// (h, w)
vector<pair<int,int>> locs;
vector<pair<int,int>> goals;
vector<vector<char>> cells;
};
State s;
int H, W, K, T;
vector<int> shff;
bool is_out_of_range(int h2, int w2) {
return (h2 < 1 || h2 > H || w2 < 1 || w2 > W);
}
P move_result(P& before, P& diff) {
P after;
after.first = before.first + diff.first;
after.second = before.second + diff.second;
return after;
}
void update_cells() {
// 1-based
s.cells.resize(H+1, vector<char>(W+1));
for(auto p: s.locs) {
auto h = p.first;
auto w = p.second;
s.cells[h][w] = 1;
}
}
char move_to_char(const pair<int,int>& p) {
if (p == mp(0, 0)) return '-';
else if (p == mp(1, 0)) return 'D';
else if (p == mp(-1, 0)) return 'U';
else if (p == mp(0, 1)) return 'R';
else if (p == mp(0, -1)) return 'L';
return '?';
}
int count_move_num(string s) {
int num = 0;
for(auto ch: s) num += ch != '-';
return num;
}
P can_get_goal(int idx) {
auto loc = s.locs[idx];
auto goal = s.goals[idx];
set<pair<int,int>> seen;
int dh[] = {0, 0, 1, -1};
int dw[] = {1, -1, 0, 0};
priority_queue<P, vector<P>, greater<P> > que;
que.push(goal);
seen.insert(goal);
while(!que.empty()){
P p = que.top();
// cout << "p:" << p.first << "," << p.second << endl;
que.pop();
REP(d, 4) {
int h2 = p.first + dh[d];
int w2 = p.second + dw[d];
if (seen.count(mp(h2,w2))) continue;
if (is_out_of_range(h2, w2)) continue;
if (s.cells[h2][w2]) continue;
if (mp(h2,w2) == loc) {
auto h_diff = p.first - loc.first;
auto w_diff = p.second - loc.second;
return mp(h_diff, w_diff);
}
que.push(mp(h2,w2));
seen.insert(mp(h2,w2));
}
}
return mp(-1,-1);
}
int main(void)
{
cin.sync_with_stdio(false);
cin >> H >> W >> K >> T;
s.locs.resize(K);
s.goals.resize(K);
shff.resize(K);
REP(k,K) shff[k] = k;
vector<tuple<int,int,int,int>> ABCDs(K);
REP(k, K) {
int a, b, c, d;
cin >> a >> b >> c >> d;
ABCDs[k] = mt(a, b, c, d);
s.locs[k] = mp(a, b);
s.goals[k] = mp(c, d);
}
vector<string> anses;
// REP(t, T) {
int t = 0;
bool last_flag = false;
int last_time = 5;
int MAX = 7000;
for(; t < MAX; ++t) {
// for(; t < 500; ++t) {
// for(; t < 1000; ++t) {
set<pair<int,int>> occupied;
REP(k, K) {
occupied.insert(s.locs[k]);
}
string ans(K, '-');
random_shuffle(ALL(shff));
for(auto k: shff) {
vector<pair<int,int>> poss_move;
// float random_poss = 0.5 - 0.2 * t / 5000;
float random_poss = 0.5 - 0.0 * t / 5000;
if (last_flag) {
random_poss = 0.0;
}
if (rand() % 100 < (random_poss * 100)) {
int rand_res = rand() % 4;
if (rand_res == 0) poss_move.pb(mp(1,0));
else if (rand_res == 1) poss_move.pb(mp(-1,0));
else if (rand_res == 2) poss_move.pb(mp(0,1));
else if (rand_res == 3) poss_move.pb(mp(0,-1));
}
else {
if (s.locs[k] == s.goals[k]) {
poss_move.pb(mp(0,0));
}
else {
if (s.locs[k].first < s.goals[k].first) poss_move.pb(mp(1,0));
if (s.locs[k].first > s.goals[k].first) poss_move.pb(mp(-1,0));
if (s.locs[k].second < s.goals[k].second) poss_move.pb(mp(0,1));
if (s.locs[k].second > s.goals[k].second) poss_move.pb(mp(0,-1));
}
}
random_shuffle(ALL(poss_move));
bool found = false;
for (auto m : poss_move) {
auto new_loc = move_result(s.locs[k], m);
if (is_out_of_range(new_loc.first, new_loc.second)) {
continue;
}
if (!occupied.count(new_loc)) {
occupied.insert(new_loc);
ans[k] = move_to_char(m);
found = true;
s.locs[k] = new_loc;
break;
}
}
if (!found) ans[k] = '-';
}
if (last_flag) {
--last_time;
if (last_time == 0) break;
}
auto move_num = count_move_num(ans);
if (move_num < 10 || t == MAX - last_time) {
last_flag = true;
}
anses.pb(ans);
}
// int cur_t = t;
// for(; t < cur_t + 20; ++t) {
// // cout << "---t:" << t << "---" << endl;
// update_cells();
// string ans(K, '-');
// random_shuffle(ALL(shff));
// int cnt = 0;
// for(auto k: shff) {
// P move = can_get_goal(k);
// if (move != mp(-1,-1)) {
// cout << endl;
// cout << "cell:" << endl;
// REP(h,H) {
// REP(w,W) cout << (int)s.cells[h][w];
// cout << endl;
// }
// cout << k << "'s pos:" << s.locs[k].first << "," << s.locs[k].second << endl;
// cout << k << "'s goal:" << s.goals[k].first << "," << s.goals[k].second << endl;
// cout << "suggested move:" << move.first << "," << move.second << endl;
// ans[k] = move_to_char(move);
// auto new_loc = move_result(s.locs[k], move);
// s.cells[new_loc.first][new_loc.second] = 1;
// s.locs[k] = new_loc;
// ++cnt;
// }
// if (cnt == 20) break;
// }
// anses.pb(ans);
// }
// print ans
cout << SIZE(anses) << endl;
for(auto ans: anses) {
cout << ans << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
minus9d |
Language |
C++14 (GCC 5.4.1) |
Score |
37266 |
Code Size |
6996 Byte |
Status |
AC |
Exec Time |
1129 ms |
Memory |
6932 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 |
1238 / 50000 |
1202 / 50000 |
1169 / 50000 |
1107 / 50000 |
1238 / 50000 |
1389 / 50000 |
1345 / 50000 |
1009 / 50000 |
1583 / 50000 |
1389 / 50000 |
1158 / 50000 |
1583 / 50000 |
1202 / 50000 |
1374 / 50000 |
1169 / 50000 |
1454 / 50000 |
1603 / 50000 |
1087 / 50000 |
299 / 50000 |
1238 / 50000 |
1359 / 50000 |
1316 / 50000 |
1051 / 50000 |
1169 / 50000 |
1276 / 50000 |
1345 / 50000 |
1289 / 50000 |
1238 / 50000 |
1345 / 50000 |
1042 / 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 |
1085 ms |
6784 KB |
subtask_01_02.txt |
AC |
1092 ms |
6784 KB |
subtask_01_03.txt |
AC |
1083 ms |
6784 KB |
subtask_01_04.txt |
AC |
1076 ms |
6784 KB |
subtask_01_05.txt |
AC |
1081 ms |
6784 KB |
subtask_01_06.txt |
AC |
1077 ms |
6784 KB |
subtask_01_07.txt |
AC |
1075 ms |
6784 KB |
subtask_01_08.txt |
AC |
1084 ms |
6784 KB |
subtask_01_09.txt |
AC |
1092 ms |
6784 KB |
subtask_01_10.txt |
AC |
1079 ms |
6784 KB |
subtask_01_11.txt |
AC |
1129 ms |
6784 KB |
subtask_01_12.txt |
AC |
1091 ms |
6784 KB |
subtask_01_13.txt |
AC |
1089 ms |
6784 KB |
subtask_01_14.txt |
AC |
1079 ms |
6932 KB |
subtask_01_15.txt |
AC |
1076 ms |
6784 KB |
subtask_01_16.txt |
AC |
1080 ms |
6784 KB |
subtask_01_17.txt |
AC |
1093 ms |
6784 KB |
subtask_01_18.txt |
AC |
1071 ms |
6784 KB |
subtask_01_19.txt |
AC |
1082 ms |
6784 KB |
subtask_01_20.txt |
AC |
1097 ms |
6784 KB |
subtask_01_21.txt |
AC |
1083 ms |
6784 KB |
subtask_01_22.txt |
AC |
1078 ms |
6784 KB |
subtask_01_23.txt |
AC |
1101 ms |
6784 KB |
subtask_01_24.txt |
AC |
1093 ms |
6784 KB |
subtask_01_25.txt |
AC |
1076 ms |
6784 KB |
subtask_01_26.txt |
AC |
1077 ms |
6784 KB |
subtask_01_27.txt |
AC |
1093 ms |
6784 KB |
subtask_01_28.txt |
AC |
1081 ms |
6784 KB |
subtask_01_29.txt |
AC |
1087 ms |
6784 KB |
subtask_01_30.txt |
AC |
1078 ms |
6784 KB |