Submission #1180485
Source Code Expand
#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <functional>
#include <set>
#include <ctime>
#include <random>
#include <chrono>
#include <cassert>
#include <tuple>
#include <utility>
using namespace std;
namespace {
using Integer = long long; //__int128;
template<class T, class S> istream& operator >> (istream& is, pair<T,S>& p){return is >> p.first >> p.second;}
template<class T> istream& operator >> (istream& is, vector<T>& vec){for(T& val: vec) is >> val; return is;}
template<class T> istream& operator , (istream& is, T& val){ return is >> val;}
template<class T, class S> ostream& operator << (ostream& os, const pair<T,S>& p){return os << p.first << " " << p.second;}
template<class T> ostream& operator << (ostream& os, const vector<T>& vec){for(size_t i=0; i<vec.size(); i++) os << vec[i] << (i==vec.size()-1?"":" "); return os;}
template<class T> ostream& operator , (ostream& os, const T& val){ return os << " " << val;}
template<class H> void print(const H& head){ cout << head; }
template<class H, class ... T> void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); }
template<class ... T> void println(const T& ... values){ print(values...); cout << endl; }
template<class H> void eprint(const H& head){ cerr << head; }
template<class H, class ... T> void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); }
template<class ... T> void eprintln(const T& ... values){ eprint(values...); cerr << endl; }
class range{ Integer start_, end_, step_; public: struct range_iterator{ Integer val, step_; range_iterator(Integer v, Integer step) : val(v), step_(step) {} Integer operator * (){return val;} void operator ++ (){val += step_;} bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;} }; range(Integer len) : start_(0), end_(len), step_(1) {} range(Integer start, Integer end) : start_(start), end_(end), step_(1) {} range(Integer start, Integer end, Integer step) : start_(start), end_(end), step_(step) {} range_iterator begin(){ return range_iterator(start_, step_); } range_iterator end(){ return range_iterator( end_, step_); } };
inline string operator "" _s (const char* str, size_t size){ return move(string(str)); }
constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);}
constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);}
constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); }
inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed
template<class T> string join(const vector<T>& v, const string& sep){ stringstream ss; for(size_t i=0; i<v.size(); i++){ if(i>0) ss << sep; ss << v[i]; } return ss.str(); }
inline string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; }
}
constexpr long long mod = 9_ten + 7;
class XorShift{
public:
uint32_t x;
uint32_t y;
uint32_t z;
uint32_t w;
XorShift(){
x = 123456789;
y = 362436069;
z = 521288629;
w = 88675123;
}
XorShift(uint32_t seed){
x = 123456789;
y = 362436069;
z = 521288629;
w = seed;
for(int i=0; i<100; i++){
(*this)();
}
}
uint32_t operator () () {
uint32_t t = x ^ (x << 11);
x = y; y = z; z = w;
return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
};
template<class T>
class Min_Cost_Flow{
public:
struct edge{
int to;
int cap;
T cost;
int rev;
bool is_rev;
};
const T INF;
vector<vector<edge>> G;
Min_Cost_Flow(int n, T inf) : G(n), INF(inf){
}
void add_edge(int from, int to, int cap, T cost){
G[from].push_back((edge){to, cap, cost, (int)G[to].size(), false});
G[to].push_back((edge){from, 0, -cost, (int)G[from].size()-1, true});
}
//min cost : s->t (flow:f)
T min_cost_flow(int s, int t, int f){
const int N = G.size();
T cost = 0;
vector<int> prev_v(N,-1);
vector<int> prev_e(N,-1);
vector<T> potantial(N, 0);
while(f>0){
//min distance(cost based) search with SPFA
vector<T> dist(N, INF);
vector<int> cnt(dist.size(), 0);
dist[s] = 0;
prev_v[s] = s;
queue<int> Q;
auto my_push = [&](int node){
Q.push(node);
cnt[node]++;
};
auto my_pop = [&]() -> int{
int ret = Q.front();
cnt[ret]--;
Q.pop();
return ret;
};
my_push(s);
while(!Q.empty()){
int pos = my_pop();
for(int i=0; i<G[pos].size(); i++){
edge& E = G[pos][i];
T new_dist = dist[pos] + E.cost + potantial[E.to] - potantial[pos];
if(dist[E.to] > new_dist && E.cap > 0){
dist[E.to] = new_dist;
prev_v[ E.to ] = pos;
prev_e[ E.to ] = i;
if(cnt[ E.to ] == 0){
my_push( E.to );
}
}
}
}
for(int i=0; i<N; i++){
dist[i] = potantial[i] + dist[i];
}
//cannot achieved to "t" return -1
if(dist[t]>=INF) return -1;
//add cost of s->t with flow=d
int pos=t;
int d=f;
while(pos!=s){
int i=prev_v[pos];
int j=prev_e[pos];
pos = i;
d = min(d, G[i][j].cap);
}
pos = t;
//cout << t ;
while(pos!=s){
int i=prev_v[pos];
int j=prev_e[pos];
G[i][j].cap -= d;
G[ G[i][j].to ][ G[i][j].rev ].cap += d;
//cost += G[i][j].cost * d;
pos = i;
//cout << " <- " << pos;
}
//cout << endl;
cost += d * dist[t];
f -= d;
//f==0 then end
}
return cost;
}
};
constexpr int H = 30, W = 30;
constexpr int K = 450;
constexpr unsigned long long seed_mt = 1145148931919ll;
constexpr unsigned int seed_xor = 1919893;
mt19937_64 mt(seed_mt);
XorShift xrand(seed_xor);
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};
tuple<vector<pair<int,int>>, vector<string>> make_checker(vector<pair<int,int>> s){
const int inf = 1e8;
vector<string> res;
while(true){
Min_Cost_Flow<int> f(H*W+2, inf);
int source = H*W;
int sink = H*W + 1;
vector<vector<int>> cell(H, vector<int>(W, -1));
for(int i : range(K)){
int r,c;
tie(r,c) = s[i];
f.add_edge( source, r*W+c, 1, 0 );
cell[r][c] = i;
}
for(int r : range(H)) for(int c : range(W)){
if( ((r+c)&1) == 0 ) f.add_edge( r*W+c, sink, 1, 0 );
for(int k : range(4)){
int rr = r + dy[k];
int cc = c + dx[k];
if( rr<0 || rr>=H || cc<0 || cc>=W ) continue;
f.add_edge( r*W+c, rr*W+cc, 1000, 1 );
}
}
int cost = f.min_cost_flow(source, sink, K);
if( cost == 0 ) break;
string movement(K, '-');
for(int i : range(K)){
int r,c;
tie(r,c) = s[i];
for(auto e : f.G[r*W+c]){
if( e.is_rev || e.to == source || e.to == sink || e.cap == 1000 ) continue;
int rr = e.to/W;
int cc = e.to%W;
if( cell[rr][cc] != -1 ) continue;
cell[rr][cc] = -2;
if( rr != r ) movement[i] = rr<r ? 'U' : 'D';
if( cc != c ) movement[i] = cc<c ? 'L' : 'R';
s[i] = {rr,cc};
break;
}
}
res.push_back( movement );
}
return make_tuple( s, res );
}
vector<string> get_next(vector<pair<int,int>>& s, vector<pair<int,int>>& target){
const int inf = 1e8;
vector<string> res;
vector<int> order_s(K), order_r(H), order_c(W), order_adj(4);
iota(order_s.begin(), order_s.end(), 0);
iota(order_r.begin(), order_r.end(), 0);
iota(order_c.begin(), order_c.end(), 0);
iota(order_adj.begin(), order_adj.end(), 0);
for(int t : range(2)){
Min_Cost_Flow<int> f(H*W+2, inf);
int source = H*W;
int sink = H*W + 1;
string movement(K, '-');
vector<vector<int>> cell(H, vector<int>(W, -1));
shuffle(order_s.begin(), order_s.end(), mt);
for(int i : order_s){
int r,c;
tie(r,c) = s[i];
f.add_edge( source, r*W+c, 1, 0 );
cell[r][c] = i;
}
shuffle(order_r.begin(), order_r.end(), mt);
shuffle(order_c.begin(), order_c.end(), mt);
for(int r : order_r) for(int c : order_c){
if( cell[r][c] == -1){
f.add_edge( r*W+c, sink, 1, 0 );
}else{
int i = cell[r][c];
shuffle(order_adj.begin(), order_adj.end(), mt);
for(int k : order_adj){
int rr = r + dy[k];
int cc = c + dx[k];
if( rr<0 || rr>=H || cc<0 || cc>=W ) continue;
int prev_score = abs( r - target[i].first ) + abs( c - target[i].second );
int next_score = abs( rr- target[i].first ) + abs( cc- target[i].second );
f.add_edge( r*W+c, rr*W+cc, 1000, min(1, (next_score-prev_score)*prev_score) );
}
}
}
int cost = f.min_cost_flow(source, sink, K);
if( cost == 0 ) break;
for(int i : order_s){
int r,c;
tie(r,c) = s[i];
for(auto e : f.G[r*W+c]){
if( e.is_rev || e.to == source || e.to == sink || e.cap == 1000 ) continue;
int rr = e.to/W;
int cc = e.to%W;
if( cell[rr][cc] != -1 ) continue;
cell[rr][cc] = i;
if( rr != r ) movement[i] = rr<r ? 'U' : 'D';
if( cc != c ) movement[i] = cc<c ? 'L' : 'R';
s[i] = {rr,cc};
break;
}
}
res.push_back( movement );
}
return res;
}
int main(){
int h_,w_,k_,t_;
cin >> h_,w_,k_,t_;
vector<pair<int,int>> initial(K),target(K);
for(auto i : range(K) ){
int ri, ci;
cin >> ri, ci;
initial[i] = {ri-1, ci-1};
int rt, ct;
cin >> rt, ct;
target[i] = {rt-1, ct-1};
}
auto initial_checker = make_checker( initial );
auto target_checker = make_checker( target );
auto s = get<0>( initial_checker );
auto t = get<0>( target_checker );
vector<string> res = get<1>( initial_checker );
for(int i=0; i<200; i++){
auto prev = s;
auto res_ = get_next(s, t);
if(prev == s){
//eprintln("same");
continue;
}
for(auto m : res_){
res.push_back(m);
}
if(s == t) break;
}
auto res_ = get<1>(target_checker);
for(auto& m : res_){
for(auto& c : m){
if( c == 'U' ) c = 'D';
else if( c == 'D' ) c = 'U';
else if( c == 'L' ) c = 'R';
else if( c == 'R' ) c = 'L';
}
}
reverse(res_.begin(), res_.end());
if(s == t){
for(auto& m : res_){
res.push_back(m);
}
}
println(res.size());
println(join(res, "\n"));
return 0;
}
Submission Info
Submission Time |
|
Task |
B - 日本橋大渋滞 |
User |
koyumeishi |
Language |
C++14 (GCC 5.4.1) |
Score |
1330975 |
Code Size |
11284 Byte |
Status |
TLE |
Exec Time |
4203 ms |
Memory |
700 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 |
46254 / 50000 |
45872 / 50000 |
45621 / 50000 |
46383 / 50000 |
45872 / 50000 |
45999 / 50000 |
45999 / 50000 |
46297 / 50000 |
45999 / 50000 |
45373 / 50000 |
45956 / 50000 |
46340 / 50000 |
46083 / 50000 |
45830 / 50000 |
45872 / 50000 |
46254 / 50000 |
46041 / 50000 |
45621 / 50000 |
45704 / 50000 |
45999 / 50000 |
46126 / 50000 |
45788 / 50000 |
45704 / 50000 |
45290 / 50000 |
45788 / 50000 |
46169 / 50000 |
0 / 50000 |
45538 / 50000 |
45830 / 50000 |
45373 / 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 |
1938 ms |
608 KB |
subtask_01_02.txt |
AC |
2520 ms |
620 KB |
subtask_01_03.txt |
AC |
2720 ms |
592 KB |
subtask_01_04.txt |
AC |
1888 ms |
644 KB |
subtask_01_05.txt |
AC |
2412 ms |
680 KB |
subtask_01_06.txt |
AC |
2220 ms |
688 KB |
subtask_01_07.txt |
AC |
2143 ms |
624 KB |
subtask_01_08.txt |
AC |
1932 ms |
608 KB |
subtask_01_09.txt |
AC |
2094 ms |
600 KB |
subtask_01_10.txt |
AC |
2956 ms |
636 KB |
subtask_01_11.txt |
AC |
2645 ms |
652 KB |
subtask_01_12.txt |
AC |
2004 ms |
624 KB |
subtask_01_13.txt |
AC |
2176 ms |
632 KB |
subtask_01_14.txt |
AC |
2256 ms |
664 KB |
subtask_01_15.txt |
AC |
2368 ms |
616 KB |
subtask_01_16.txt |
AC |
2001 ms |
612 KB |
subtask_01_17.txt |
AC |
2114 ms |
608 KB |
subtask_01_18.txt |
AC |
2572 ms |
664 KB |
subtask_01_19.txt |
AC |
2383 ms |
632 KB |
subtask_01_20.txt |
AC |
2369 ms |
624 KB |
subtask_01_21.txt |
AC |
2321 ms |
656 KB |
subtask_01_22.txt |
AC |
2443 ms |
620 KB |
subtask_01_23.txt |
AC |
2627 ms |
612 KB |
subtask_01_24.txt |
AC |
2508 ms |
608 KB |
subtask_01_25.txt |
AC |
2525 ms |
600 KB |
subtask_01_26.txt |
AC |
2450 ms |
608 KB |
subtask_01_27.txt |
TLE |
4203 ms |
604 KB |
subtask_01_28.txt |
AC |
2622 ms |
612 KB |
subtask_01_29.txt |
AC |
2198 ms |
628 KB |
subtask_01_30.txt |
AC |
2483 ms |
700 KB |