Submission #1177375
Source Code Expand
#include <iostream>
#include <cstdlib>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <iostream>
#include <fstream>
#include <unistd.h>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include "sys/time.h"
using namespace std;
#define ITER(l,i) for(decltype(l.begin()) i=l.begin();i!=l.end();i++)
#define HERE (cerr << "LINE: " << __LINE__ << endl)
typedef long long ll_t;
typedef unsigned long long ull_t;
#ifdef LOCAL
#define msg(x) (x)
#else
#define msg(x)
#endif
#define DBG(x) cerr << #x << ": " << x << endl
struct timeval timer_begin, timer_end;
int timer_called;
inline void timer_start()
{
timer_called++;
gettimeofday(&timer_begin, NULL);
}
inline double timer_now()
{
timer_called++;
gettimeofday(&timer_end, NULL);
return timer_end.tv_sec - timer_begin.tv_sec +
(timer_end.tv_usec - timer_begin.tv_usec)/1000000.0;
}
template<class T>
const T& clamp(const T& v,const T& lo,const T& hi) {
return (v < lo) ? lo : (v > hi) ? hi : v;
}
unsigned int hash_function(unsigned long p) {
// xor32()
p ^= p<<7;
p ^= p>>1;
p ^= p<<25;
unsigned int c = __builtin_popcount(p);
return p<<c | p>>(32-c);
}
unsigned long long hash_function64(unsigned long long p) {
// xor64()
p ^= p<<16;
p ^= p>>7;
p ^= p<<39;
unsigned long long c = __builtin_popcount(p);
return p<<c | p>>(64-c);
}
struct xor128_t {
unsigned long long x, y, z, w;
xor128_t(int seed=0) : x(123456789^seed) , y(362436069), z(521288629), w(88675123) {
for (int i=0; i<48; i++)
get();
}
void init(int seed) {
x = 123456789^seed;
y = 362436069;
z = 521288629;
w = 88675123;
for (int i=0; i<48; i++)
get();
}
inline unsigned long long get() {
unsigned long long t=(x^(x<<11)); x=y; y=z; z=w;
return (w=(w^(w>>19))^(t^(t>>8)));
}
inline unsigned long long get(unsigned int sz) {
if (sz <= 1)
return 0;
unsigned long long x;
const unsigned long long mask = (1<<(ilogb(sz-1)+1)) - 1;
//cout << sz << " " << mask << endl;
assert(mask >= (sz-1) && mask < 2*sz-1);
do {
x = get() & mask;
} while (x >= sz);
return x;
}
inline unsigned long long get(int beg,int end) {
return get(end-beg) + beg;
}
double get_double() {
static const double double_factor = 1.0 / (1.0 + 0xffffffffffffffffuLL);
return get() * double_factor;
}
template<typename T> void shuffle(vector<T>& v,int partial=-1) {
int sz = v.size();
if (partial < 0 || partial > sz)
partial = sz;
for (int i=0; i<partial; i++) {
swap(v[i], v[i + get(sz-i)]);
}
}
};
struct uf_t {
vector <int16_t> parent;
void clear() {
parent.clear();
}
void add(int elm) {
if (elm >= parent.size())
parent.resize(elm+1, -1);
}
void merge(int a,int b) {
add(a);
add(b);
int ia = a;
int ib = b;
if ((ia^ib)&1) swap(ia, ib); // ok?
int ra = root(ia);
int rb = root(ib);
if (ra != rb) {
parent[ra] += parent[rb];
parent[rb] = ra;
}
}
int size(int elm) {
return -parent[root(elm)];
}
int id(int elm) {
return root(elm);
}
int root(int ia) {
add(ia);
return (parent[ia] < 0) ? ia : (parent[ia] = root(parent[ia]));
}
};
template <typename Score_t,typename Item_t,typename HashFunc_t>
struct best_k_t {
vector<pair<Score_t,int>> v;
vector<Item_t> items;
HashFunc_t hashfunc;
set<uint32_t> used;
bool never_push;
best_k_t() : never_push(false) {}
void push_force(const Score_t sc,const Item_t& e) {
int id = items.size();
items.push_back(e);
int n = v.size();
v.push_back(pair<Score_t,int>(sc,id));
int m = (n+1)/2 - 1;
while (n > 0 && v[n] < v[m]) {
swap(v[n], v[m]);
n = m;
m = (n+1)/2 - 1;
}
}
bool push(const Score_t sc,const Item_t& e,int w) {
assert(!never_push);
if (v.size() < w) {
auto h = hashfunc(e);
if (!used.count(h)) {
used.insert(h);
push_force(sc, e);
return true;
} else {
return false;
}
} else if (sc > v[0].first) {
auto h = hashfunc(e);
if (!used.count(h)) {
int id = v[0].second;
v[0].first = sc;
items[id] = e;
used.insert(h);
rebuild();
return true;
} else {
return false;
}
}
return false;
}
bool match(const Score_t sc,int w) {
return (v.size() < w || sc > v[0].first);
}
void rebuild() {
int n = 0;
while (true) {
int L = (n+1)*2 - 1;
int R = L+1;
if (L >= v.size())
break;
int m = (R >= v.size() || v[L] < v[R]) ? L : R;
if (v[m] < v[n]) {
swap(v[m], v[n]);
n = m;
} else {
break;
}
}
}
Item_t pop() {
// fix me
never_push = true;
int id = v[0].second;
Item_t ret = items[id];
v[0] = v.back();
v.pop_back();
rebuild();
return ret;
}
Item_t top() { return v[0].second; }
Item_t best() const {
int best_i = 0;
for (int i=0; i<v.size(); i++) {
if (v[i] < v[best_i])
best_i = i;
}
return items[v[best_i].second];
}
void clear() { v.clear(); }
bool empty() const { return v.empty(); }
int size() const { return v.size(); }
};
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
os << "[ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " ]";
return os;
}
template<typename T> ostream& operator<<(ostream& os, const set<T>& v) {
os << "{ ";
for(typename set<T>::const_iterator it=v.begin(); it!=v.end(); ++it) {
if (it != v.begin())
os << ", ";
os << *it;
}
os << " }";
return os;
}
template<typename T1,typename T2> ostream& operator<<(ostream& os, const pair<T1,T2>& v) {
os << "[ " << v.first << ", " << v.second << "]";
return os;
}
#ifdef LOCAL
double TIME_LIMIT_FACTOR = 0.55;
#else
double TIME_LIMIT_FACTOR = 1.0;
#endif
double TIME_LIMIT = TIME_LIMIT_FACTOR * 4.0;
/* insert here */
struct car_t {
int id;
int ix, iy, tx, ty;
int x, y;
car_t() {}
car_t(int id,int a, int b,int c,int d) : id(id) {
ix = b-1;
iy = a-1;
tx = d-1;
ty = c-1;
x = ix;
y = iy;
}
bool finished() const {
return x == tx && y == ty;
}
static bool less_tyx(const car_t& a,const car_t& b) {
return (a.ty != b.ty) ? (a.ty < b.ty) : (a.tx < b.tx);
}
static bool less_txy(const car_t& a,const car_t& b) {
return (a.tx != b.tx) ? (a.tx < b.tx) : (a.ty < b.ty);
}
int cost() const {
return abs(tx - x) + abs(ty - y);
}
};
ostream& operator<<(ostream& os,const car_t& car) {
os << "#" << car.id
<< "(" << car.x << " " << car.y << ")"
<< "->(" << car.tx << " " << car.ty << ")";
return os;
}
int H, W, K, T;
int cp(int x,int y) { return y*W+x; }
double score_function(int t,const vector<car_t>& cars) {
double pd = 20;
for (const auto& car : cars) {
pd += abs(car.tx - car.x) + abs(car.ty - car.y);
}
double pt = 10 + t * 0.01;
return 10000000 / (pd * pt);
}
bool move_or_stay(int id,char dir,
vector<car_t>& cars,
vector<vector<int>>& cur,
vector<vector<int>>& nxt,
string& moves) {
if (id < 0 || id >= K || moves[id] != '*')
return false;
assert(dir == 'R' || dir == 'L' || dir == 'D' || dir == 'U' || dir == '-');
auto& car(cars[id]);
int dx = (dir == 'R') ? 1 : (dir == 'L') ? -1 : 0;
int dy = (dir == 'D') ? 1 : (dir == 'U') ? -1 : 0;
int nx = car.x + dx;
int ny = car.y + dy;
if (nx < 0 || nx >= W || ny < 0 || ny >= H ||
cur[ny][nx] >= 0 || nxt[ny][nx] >= 0) {
moves[id] = '-';
nxt[car.y][car.x] = id;
return false;
}
assert(dir != '-');
car.x = nx;
car.y = ny;
nxt[ny][nx] = id;
moves[id] = dir;
return true;
}
bool move_if_possible(int id,char dir,
vector<car_t>& cars,
vector<vector<int>>& cur,
vector<vector<int>>& nxt,
string& moves) {
if (id < 0 || id >= K || moves[id] != '*')
return false;
assert(dir == 'R' || dir == 'L' || dir == 'D' || dir == 'U' || dir == '-');
auto& car(cars[id]);
int dx = (dir == 'R') ? 1 : (dir == 'L') ? -1 : 0;
int dy = (dir == 'D') ? 1 : (dir == 'U') ? -1 : 0;
int nx = car.x + dx;
int ny = car.y + dy;
if (nx < 0 || nx >= W || ny < 0 || ny >= H ||
cur[ny][nx] >= 0 || nxt[ny][nx] >= 0) {
return false;
}
assert(dir != '-');
car.x = nx;
car.y = ny;
nxt[ny][nx] = id;
moves[id] = dir;
return true;
}
void rotate(int left,int top,int right,int bottom,
vector<car_t>& cars,
vector<vector<int>>& cur,
vector<vector<int>>& nxt,
string& moves,
const set<int> ignores = set<int>()) {
for (int x=left; x<right; x++) {
int id = cur[top][x];
if (id >= 0 && !ignores.count(id))
move_if_possible(id, 'R', cars, cur, nxt, moves);
}
for (int y=top; y<bottom; y++) {
int id = cur[y][right];
if (id >= 0 && !ignores.count(id))
move_if_possible(id, 'D', cars, cur, nxt, moves);
}
for (int x=right; x>left; x--) {
int id = cur[bottom][x];
if (id >= 0 && !ignores.count(id))
move_if_possible(id, 'L', cars, cur, nxt, moves);
}
for (int y=bottom; y>top; y--) {
int id = cur[y][left];
if (id >= 0 && !ignores.count(id))
move_if_possible(id, 'U', cars, cur, nxt, moves);
}
}
vector<string> solve_greedy(vector<car_t> cars) {
vector<vector<int>> cur(H, vector<int>(W, -1));
vector<vector<int>> nxt(H, vector<int>(W, -1));
vector<vector<int>> goal(H, vector<int>(W, -1));
for (const auto car: cars) {
cur[car.y][car.x] = car.id;
goal[car.ty][car.tx] = car.id;
}
auto mid(goal);
for (int x=0; x<W; x++)
for (int y=H-1, c=0; c<H-1; c++) {
if (mid[y][x] < 0) {
for (int k=y; k>0; k--)
swap(mid[k][x], mid[k-1][x]);
} else {
y--;
}
}
vector<int> mx(K), my(K);
for (int y=0; y<H; y++)
for (int x=0; x<W; x++) {
int id = mid[y][x];
if (id >= 0) {
mx[id] = x;
my[id] = y;
}
}
vector<int> rx(K);
{
for (int y=0; y+3<H; y+=4) {
vector<car_t> ord;
for (int dy=0; dy<4; dy++)
for (int x=0; x<W; x++) {
if (cur[y+dy][x] >= 0)
ord.push_back(cars[cur[y+dy][x]]);
}
sort(ord.begin(), ord.end(), car_t::less_txy);
cerr << ord.size()/2+1 << endl;
for (int i=0; i<ord.size(); i++) {
rx[ord[i].id] = 1 + i*(W-2)/ord.size();
}
}
}
vector<string> sol;
xor128_t rng;
int best_t = -1;
double best_score = 0;
int target_y = H-1;
enum phase_t {
PHASE_ROT,
PHASE_UP,
PHASE_MID,
PHASE_FINISH,
PHASE_DONE,
};
phase_t phase = PHASE_ROT;
for (int t=0; t<T; t++) {
{
bool error_found = false;
for (const auto& car : cars) {
if (cur[car.y][car.x] != car.id) {
error_found = true;
cerr << "t: " << t << " " << car << " " << cur[car.y][car.x] << endl;
}
}
if (error_found)
break;
for (const auto& car : cars) {
assert(cur[car.y][car.x] == car.id);
}
}
string moves(K, '*');
if (phase == PHASE_ROT) {
int T = 45;
for (int y=t/T%2; y<H; y+=2)
for (int x=0; x<W; x++) {
int id = cur[y][x];
//if (id >= 0 && abs(cars[id].tx-x) <= 1) {
//if (id >= 0 && cars[id].tx/3 == x/3) {
if (id >= 0 && rx[id]/3 == x/3) {
if (x > 0 && t/T%2 == 0)
move_if_possible(id, 'D', cars, cur, nxt, moves);
if (x < W-1)
move_if_possible(id, 'U', cars, cur, nxt, moves);
if (x > 0)
move_if_possible(id, 'D', cars, cur, nxt, moves);
}
}
if (true || t%T < 30) {
for (int y=t/T%4; y+2<H; y+=4)
rotate(0, y, W-1, y+2, cars, cur, nxt, moves);
} else {
for (int y=0; y<H; y++)
for (int x=0; x<W; x++) {
int id = cur[y][x];
if (id >= 0)
if (cars[id].x < rx[id])
move_if_possible(id, 'R', cars, cur, nxt, moves);
else if (cars[id].x > rx[id])
move_if_possible(id, 'L', cars, cur, nxt, moves);
else
move_if_possible(id, '-', cars, cur, nxt, moves);
}
}
for (int i=0; i<K; i++)
if (moves[i] == '*')
move_or_stay(i, '-', cars, cur, nxt, moves);
if (t >= 2*T)
phase = PHASE_UP;
} else if (phase == PHASE_UP) {
for (int id=0; id<K; id++)
move_or_stay(id, 'U', cars, cur, nxt, moves);
int c = 0;
for (int id=0; id<K; id++)
if (cars[id].y < target_y-2)
c++;
if (c == K)
phase = PHASE_MID;
} if (phase == PHASE_MID) {
int c = 0;
int n = 0;
for (int x=0; x<W; x+=3) {
int qy = -1;
for (int y=0; y<target_y-2; y++)
for (int dx=0; dx<3; dx++) {
int id = cur[y][x+dx];
if (id >= 0 && my[id] > qy)
qy = my[id];
}
for (int y=0; y<H; y++) {
for (int dx=0; dx<3; dx++) {
int id = cur[y][x+dx];
if (id < 0)
continue;
if (my[id] >= target_y) {
n++;
if (cars[id].x == mx[id] && cars[id].y > my[id]) {
c++;
move_or_stay(id, 'U', cars, cur, nxt, moves);
} else if (cars[id].x == mx[id] && cars[id].y == my[id]) {
c++;
move_or_stay(id, '-', cars, cur, nxt, moves);
} else if (cars[id].y >= target_y-2 && cars[id].x == mx[id])
move_or_stay(id, 'D', cars, cur, nxt, moves);
else if (cars[id].y == target_y-1 && cars[id].x < mx[id])
move_or_stay(id, 'R', cars, cur, nxt, moves);
else if (cars[id].y == target_y-2 && cars[id].x > mx[id])
move_or_stay(id, 'L', cars, cur, nxt, moves);
else if (cars[id].y >= target_y-1 && cars[id].x != mx[id])
move_or_stay(id, 'U', cars, cur, nxt, moves);
else {
move_or_stay(id, "RDL"[dx], cars, cur, nxt, moves);
}
} else if (t > 10 && my[id] == qy) {
if (cars[id].y < qy-4)
move_or_stay(id, "RDL"[dx], cars, cur, nxt, moves);
else
move_or_stay(id, "R-L"[dx], cars, cur, nxt, moves);
}
}
if (cur[y][x+1] >= 0) {
if (cars[cur[y][x+1]].x > cars[cur[y][x+1]].tx)
move_if_possible(cur[y][x+1], 'L', cars, cur, nxt, moves);
move_if_possible(cur[y][x+1], 'R', cars, cur, nxt, moves);
move_if_possible(cur[y][x+1], 'L', cars, cur, nxt, moves);
}
move_or_stay(cur[y][x+1], 'D', cars, cur, nxt, moves);
move_if_possible(cur[y][x], 'U', cars, cur, nxt, moves);
if (cur[y][x] >= 0 && y%2 == 0)
move_or_stay(cur[y][x], 'L', cars, cur, nxt, moves);
else
move_or_stay(cur[y][x], 'U', cars, cur, nxt, moves);
move_if_possible(cur[y][x+2], 'U', cars, cur, nxt, moves);
if (cur[y][x+2] >= 0 && y%2 == 1)
move_or_stay(cur[y][x+2], 'R', cars, cur, nxt, moves);
else
move_or_stay(cur[y][x+2], 'U', cars, cur, nxt, moves);
}
}
if (c == K) {
phase = PHASE_FINISH;
} if (c == n) {
target_y --;
if (target_y%3 == 0) {
bool found = false;
for (int x=0; !found && x<W; x++)
if (cur[target_y-3][x] >= 0)
found = true;
if (!found) {
for (int i=0; i<K; i++)
if (my[i] <= target_y || (my[i] > target_y && my[i] > cars[i].ty))
my[i]--;
target_y --;
}
}
cerr << "target: " << target_y << endl;
}
} else if (phase == PHASE_FINISH) {
int c = 0;
for (int y=0; y<H; y++)
for (int x=0; x<W; x++) {
int id = cur[y][x];
if (id >= 0) {
if (cars[id].finished()) {
move_or_stay(id, '-', cars, cur, nxt, moves);
c++;
} else if (cars[id].y < cars[id].ty) {
move_or_stay(id, 'D', cars, cur, nxt, moves);
} else {
move_or_stay(id, 'U', cars, cur, nxt, moves);
}
}
}
if (c == K)
phase = PHASE_DONE;
} else if (phase == PHASE_DONE) {
break;
}
sol.push_back(moves);
cur = nxt;
for (auto& tmp : nxt) { fill(tmp.begin(), tmp.end(), -1); }
double sc = score_function(t, cars);
if (best_t < 0 || sc >= best_score) {
cerr << "turn: " << t << " " << sc << endl;
best_score = sc;
best_t = t;
}
}
finished:
if (phase != PHASE_DONE)
best_t = sol.size()-1;
sol.resize(best_t+1);
return sol;
}
int main()
{
cin >> H >> W >> K >> T;
assert(H == 30);
assert(W == 30);
assert(K == 450);
assert(T == 10000);
vector<car_t> cars(K);
for (int i=0; i<K; i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
car_t car(i, a, b, c, d);
cars[i] = car;
}
auto sol = solve_greedy(cars);
cout << sol.size() << endl;
for (int i=0; i<sol.size(); i++) {
cout << sol[i] << endl;
}
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
yowa |
Language |
C++14 (GCC 5.4.1) |
Score |
493233 |
Code Size |
17274 Byte |
Status |
RE |
Exec Time |
219 ms |
Memory |
9600 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 |
30732 / 50000 |
94 / 50000 |
30121 / 50000 |
30960 / 50000 |
0 / 50000 |
30694 / 50000 |
0 / 50000 |
0 / 50000 |
119 / 50000 |
30751 / 50000 |
31018 / 50000 |
109 / 50000 |
0 / 50000 |
105 / 50000 |
31095 / 50000 |
0 / 50000 |
30903 / 50000 |
108 / 50000 |
0 / 50000 |
30694 / 50000 |
30865 / 50000 |
0 / 50000 |
31506 / 50000 |
30770 / 50000 |
94 / 50000 |
30451 / 50000 |
0 / 50000 |
30619 / 50000 |
31231 / 50000 |
30194 / 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 |
17 ms |
896 KB |
subtask_01_02.txt |
AC |
218 ms |
9600 KB |
subtask_01_03.txt |
AC |
17 ms |
896 KB |
subtask_01_04.txt |
AC |
16 ms |
896 KB |
subtask_01_05.txt |
RE |
111 ms |
640 KB |
subtask_01_06.txt |
AC |
16 ms |
896 KB |
subtask_01_07.txt |
RE |
111 ms |
640 KB |
subtask_01_08.txt |
RE |
110 ms |
640 KB |
subtask_01_09.txt |
AC |
219 ms |
9600 KB |
subtask_01_10.txt |
AC |
16 ms |
896 KB |
subtask_01_11.txt |
AC |
16 ms |
896 KB |
subtask_01_12.txt |
AC |
216 ms |
9600 KB |
subtask_01_13.txt |
RE |
109 ms |
512 KB |
subtask_01_14.txt |
AC |
216 ms |
9600 KB |
subtask_01_15.txt |
AC |
16 ms |
896 KB |
subtask_01_16.txt |
RE |
112 ms |
640 KB |
subtask_01_17.txt |
AC |
16 ms |
896 KB |
subtask_01_18.txt |
AC |
217 ms |
9600 KB |
subtask_01_19.txt |
RE |
111 ms |
640 KB |
subtask_01_20.txt |
AC |
16 ms |
896 KB |
subtask_01_21.txt |
AC |
16 ms |
896 KB |
subtask_01_22.txt |
RE |
112 ms |
640 KB |
subtask_01_23.txt |
AC |
16 ms |
896 KB |
subtask_01_24.txt |
AC |
16 ms |
896 KB |
subtask_01_25.txt |
AC |
219 ms |
9600 KB |
subtask_01_26.txt |
AC |
16 ms |
896 KB |
subtask_01_27.txt |
RE |
112 ms |
640 KB |
subtask_01_28.txt |
AC |
17 ms |
896 KB |
subtask_01_29.txt |
AC |
16 ms |
896 KB |
subtask_01_30.txt |
AC |
17 ms |
896 KB |