Submission #1628271
Source Code Expand
/+ dub.sdl:
name "B"
dependency "dcomp" version=">=0.6.0"
+/
import std.stdio, std.algorithm, std.range, std.conv;
// import dcomp.foundation, dcomp.scanner;
// import dcomp.graph.maxflow;
int main() {
Scanner sc = new Scanner(stdin);
int n;
int[] u, d, l, r;
sc.read(n, u, d, l, r);
int[] ud = new int[n]; ud[] = u[] + d[];
int[] lr = new int[n]; lr[] = l[] + r[];
if (ud.count!(a => a>n) || lr.count!(a => a>n)) {
writeln("NO");
return 0;
}
struct E { int to, cap; int rev; }
E[][] g = new E[][2*n + 2];
void add(int from, int to, int cap) {
// writeln("add ", from, " ", to, " ", cap);
g[from] ~= E(to, cap, g[to].length.to!int);
g[to] ~= E(from, 0, g[from].length.to!int-1);
}
int sv = 2*n, tv = sv+1;
foreach (i; 0..n) {
add(sv, i, ud[i]);
add(n+i, tv, n-lr[i]);
}
foreach (y; 0..n) {
foreach (x; 0..n) {
add(x, y+n, 1);
}
}
auto mf = maxFlow!(int, 0)(g, sv, tv);
if (mf.flow != ud.sum()) {
writeln("NO");
return 0;
}
// if (50 <= n) return 0;
int[][] dir = new int[][](n, n);
foreach (x; 0..n) {
int[] yv;
foreach (e; g[x]) {
if (e.to == sv) continue;
if (e.cap == 1) continue;
yv ~= e.to - n;
}
foreach (i, y; yv) {
if (i < u[x]) {
dir[y][x] = 0;
} else {
dir[y][x] = 1;
}
}
}
foreach (y; 0..n) {
int[] xv;
foreach (e; g[n+y]) {
if (e.to == tv) continue;
if (e.cap == 1) continue;
xv ~= e.to;
}
foreach (i, x; xv) {
if (i < l[y]) {
dir[y][x] = 2;
} else {
dir[y][x] = 3;
}
}
}
bool[][] used = new bool[][](n, n);
int usedc;
int[][4] cnt = new int[][4];
foreach (i; 0..4) cnt[i] = new int[n];
cnt[1][] = n-1;
cnt[3][] = n-1;
int[2] mv(int x, int y) {
int d = dir[y][x];
if (d == 0 || d == 1) return [x, cnt[d][x]];
else return [cnt[d][y], y];
}
bool update;
void put(int x, int y) {
assert(!used[y][x]);
update = true;
used[y][x] = true;
int d = dir[y][x];
int p = (d < 2 ? x : y) + 1;
writeln("UDLR"[d], p);
while (cnt[0][x] < n && used[cnt[0][x]][x]) cnt[0][x]++;
while (cnt[1][x] >= 0 && used[cnt[1][x]][x]) cnt[1][x]--;
while (cnt[2][y] < n && used[y][cnt[2][y]]) cnt[2][y]++;
while (cnt[3][y] >= 0 && used[y][cnt[3][y]]) cnt[3][y]--;
}
int[][] mp = new int[][](n, n);
while (true) {
update = false;
// writeln("ST");
// foreach (v; dir) writeln(v);
void dfs(int[2] st) {
static int ph = 114514; ph++;
if (st[0] < 0 || n <= st[0]) return;
if (st[1] < 0 || n <= st[1]) return;
while (mp[st[1]][st[0]] != ph) {
mp[st[1]][st[0]] = ph;
st = mv(st[0], st[1]);
}
if (mv(st[0], st[1]) == st) {
put(st[0], st[1]);
return;
}
int[2] ed = st;
int bd = dir[st[1]][st[0]];
while (true) {
auto nx = mv(st[0], st[1]);
swap(bd, dir[st[1]][st[0]]);
st = nx;
if (st == ed) break;
}
dir[ed[1]][ed[0]] = bd;
}
foreach (i; 0..n) {
dfs([i, cnt[0][i]]);
}
foreach (i; 0..n) {
dfs([i, cnt[1][i]]);
}
foreach (i; 0..n) {
dfs([cnt[2][i], i]);
}
foreach (i; 0..n) {
dfs([cnt[3][i], i]);
}
if (!update) break;
}
return 0;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/graph/maxflow.d */
// module dcomp.graph.maxflow;
// import dcomp.container.deque, dcomp.array;
struct MaxFlowInfo(C) {
C flow;
bool[] dual;
}
MaxFlowInfo!(C) maxFlow(C, C EPS, T)(T g, int s, int t) {
assert(s != t);
import std.algorithm : map;
import std.range : array;
import std.conv : to;
int n = g.length.to!int;
int[] level = new int[n];
int[] iter = new int[n];
void bfs() {
level[] = -1; level[s] = 0;
auto que = FastAppender!(int[])();
que ~= s;
while (!que.empty) {
int v = que.back; que.removeBack;
foreach (e; g[v]) {
if (e.cap <= EPS) continue;
if (level[e.to] < 0) {
level[e.to] = level[v] + 1;
que.insertBack(e.to);
}
}
}
}
C dfs(int v, C f) {
import std.algorithm : min;
if (v == t) return f;
C res = 0;
auto edgeList = g[v][iter[v]..$];
foreach (ref e; edgeList) {
if (e.cap <= EPS) continue;
if (level[v] >= level[e.to]) continue;
C d = dfs(e.to, min(f, e.cap));
e.cap -= d;
g[e.to][e.rev].cap += d;
res += d;
f -= d;
if (f == 0) break;
iter[v]++;
}
return res;
}
C flow = 0;
while (true) {
bfs();
if (level[t] < 0) break;
iter[] = 0;
while (true) {
C f = dfs(s, C.max);
if (!f) break;
flow += f;
}
}
auto mfInfo = MaxFlowInfo!C();
mfInfo.flow = flow;
mfInfo.dual = level.map!"a == -1".array;
return mfInfo;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */
// module dcomp.foundation;
static if (__VERSION__ <= 2070) {
template fold(fun...) if (fun.length >= 1) {
auto fold(R, S...)(R r, S seed) {
import std.algorithm : reduce;
static if (S.length < 2) {
return reduce!fun(seed, r);
} else {
import std.typecons : tuple;
return reduce!fun(tuple(seed), r);
}
}
}
}
version (X86) static if (__VERSION__ < 2071) {
import core.bitop : bsf, bsr, popcnt;
int bsf(ulong v) {
foreach (i; 0..64) {
if (v & (1UL << i)) return i;
}
return -1;
}
int bsr(ulong v) {
foreach_reverse (i; 0..64) {
if (v & (1UL << i)) return i;
}
return -1;
}
int popcnt(ulong v) {
int c = 0;
foreach (i; 0..64) {
if (v & (1UL << i)) c++;
}
return c;
}
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/container/deque.d */
// module dcomp.container.deque;
struct DequePayload(T) {
import core.exception : RangeError;
import core.memory : GC;
import std.range : ElementType, isInputRange;
import std.traits : isImplicitlyConvertible;
T *d;
size_t st, length, cap;
@property bool empty() const { return length == 0; }
alias opDollar = length;
ref inout(T) opIndex(size_t i) inout {
version(assert) if (length <= i) throw new RangeError();
return d[(st+i >= cap) ? (st+i-cap) : st+i];
}
private void expand() {
import std.algorithm : max;
assert(length == cap);
auto nc = max(size_t(4), 2*cap);
T* nd = cast(T*)GC.malloc(nc * T.sizeof);
foreach (i; 0..length) {
nd[i] = this[i];
}
d = nd; st = 0; cap = nc;
}
void clear() {
st = length = 0;
}
void insertFront(T v) {
if (length == cap) expand();
if (st == 0) st += cap;
st--; length++;
this[0] = v;
}
void insertBack(T v) {
if (length == cap) expand();
length++;
this[length-1] = v;
}
void removeFront() {
assert(!empty, "Deque.removeFront: Deque is empty");
st++; length--;
if (st == cap) st = 0;
}
void removeBack() {
assert(!empty, "Deque.removeBack: Deque is empty");
length--;
}
ref inout(T) front() inout { return this[0]; }
ref inout(T) back() inout { return this[$-1]; }
Range opSlice() {return Range(&this, 0, length); }
alias Range = RangeT!(DequePayload!T);
alias ConstRange = RangeT!(const DequePayload!T);
alias ImmutableRange = RangeT!(immutable DequePayload!T);
static struct RangeT(A) {
import std.traits : CopyTypeQualifiers;
alias E = CopyTypeQualifiers!(A, T);
A *p;
size_t a, b;
@property bool empty() const { return b <= a; }
@property size_t length() const { return b-a; }
@property RangeT save() { return RangeT(p, a, b); }
@property RangeT!(const A) save() const {
return typeof(return)(p, a, b);
}
alias opDollar = length;
@property ref inout(E) front() inout { return (*p)[a]; }
@property ref inout(E) back() inout { return (*p)[b-1]; }
void popFront() {
version(assert) if (empty) throw new RangeError();
a++;
}
void popBack() {
version(assert) if (empty) throw new RangeError();
b--;
}
ref inout(E) opIndex(size_t i) inout { return (*p)[i]; }
RangeT opSlice() { return this.save; }
RangeT opSlice(size_t i, size_t j) {
version(assert) if (i > j || a + j > b) throw new RangeError();
return typeof(return)(p, a+i, a+j);
}
RangeT!(const A) opSlice() const { return this.save; }
RangeT!(const A) opSlice(size_t i, size_t j) const {
version(assert) if (i > j || a + j > b) throw new RangeError();
return typeof(return)(p, a+i, a+j);
}
}
}
struct Deque(T, bool mayNull = true) {
import core.exception : RangeError;
import core.memory : GC;
import std.range : ElementType, isInputRange;
import std.traits : isImplicitlyConvertible;
alias Payload = DequePayload!T;
alias Range = Payload.Range;
alias ConstRange = Payload.ConstRange;
alias ImmutableRange = Payload.ImmutableRange;
Payload* p;
private void I() { if (mayNull && !p) p = new Payload(); }
private void C() const {
version(assert) if (mayNull && !p) throw new RangeError();
}
static if (!mayNull) {
@disable this();
}
private this(Payload* p) {
this.p = p;
}
this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) {
p = new Payload();
foreach (v; values) {
insertBack(v);
}
}
this(Range)(Range r)
if (isInputRange!Range &&
isImplicitlyConvertible!(ElementType!Range, T) &&
!is(Range == T[])) {
p = new Payload();
foreach (v; r) {
insertBack(v);
}
}
static Deque make() { return Deque(new Payload()); }
@property bool havePayload() const { return (!mayNull || p); }
@property bool empty() const { return (!havePayload || p.empty); }
@property size_t length() const { return (havePayload ? p.length : 0); }
alias opDollar = length;
ref inout(T) opIndex(size_t i) inout {C; return (*p)[i]; }
ref inout(T) front() inout {C; return (*p)[0]; }
ref inout(T) back() inout {C; return (*p)[$-1]; }
void clear() { if (p) p.clear(); }
void insertFront(T v) {I; p.insertFront(v); }
void insertBack(T v) {I; p.insertBack(v); }
alias stableInsertBack = insertBack;
void removeFront() {C; p.removeFront(); }
void removeBack() {C; p.removeBack(); }
Range opSlice() {I; return Range(p, 0, length); }
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;
class Scanner {
import std.stdio : File;
import std.conv : to;
import std.range : front, popFront, array, ElementType;
import std.array : split;
import std.traits : isSomeChar, isStaticArray, isArray;
import std.algorithm : map;
File f;
this(File f) {
this.f = f;
}
char[512] lineBuf;
char[] line;
private bool succ() {
import std.range.primitives : empty, front, popFront;
import std.ascii : isWhite;
while (true) {
while (!line.empty && line.front.isWhite) {
line.popFront;
}
if (!line.empty) break;
if (f.eof) return false;
line = lineBuf[];
f.readln(line);
}
return true;
}
private bool readSingle(T)(ref T x) {
import std.algorithm : findSplitBefore;
import std.string : strip;
import std.conv : parse;
if (!succ()) return false;
static if (isArray!T) {
alias E = ElementType!T;
static if (isSomeChar!E) {
auto r = line.findSplitBefore(" ");
x = r[0].strip.dup;
line = r[1];
} else {
auto buf = line.split.map!(to!E).array;
static if (isStaticArray!T) {
assert(buf.length == T.length);
}
x = buf;
line.length = 0;
}
} else {
x = line.parse!T;
}
return true;
}
int read(T, Args...)(ref T x, auto ref Args args) {
if (!readSingle(x)) return 0;
static if (args.length == 0) {
return 1;
} else {
return 1 + read(args);
}
}
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/array.d */
// module dcomp.array;
T[N] fixed(T, size_t N)(T[N] a) {return a;}
struct FastAppender(A) {
import std.algorithm : max;
import std.range.primitives : ElementEncodingType;
import core.stdc.string : memcpy;
private alias T = ElementEncodingType!A;
private T* _data;
private size_t len, cap;
@property size_t length() {return len;}
void reserve(size_t nlen) {
import core.memory : GC;
if (nlen <= cap) return;
void* nx = GC.malloc(nlen * T.sizeof);
cap = nlen;
if (len) memcpy(nx, _data, len * T.sizeof);
_data = cast(T*)(nx);
}
void opOpAssign(string op : "~")(T item) {
if (len == cap) {
reserve(max(4, cap*2));
}
_data[len++] = item;
}
void insertBack(T item) {
this ~= item;
}
void removeBack() {
len--;
}
void clear() {
len = 0;
}
bool empty() const { return len == 0; }
ref inout(T) back() inout { assert(len); return _data[len-1]; }
T[] data() {
return (_data) ? _data[0..len] : null;
}
}
Submission Info
Submission Time |
|
Task |
J - Neue Spiel |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
2100 |
Code Size |
15584 Byte |
Status |
AC |
Exec Time |
102 ms |
Memory |
10492 KB |
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
2000 / 2000 |
100 / 100 |
Status |
|
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt |
dataset1 |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt |
dataset2 |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, 01-31.txt, 01-32.txt, 01-33.txt, 01-34.txt, 01-35.txt, 01-36.txt, 01-37.txt, 01-38.txt, 01-39.txt, 01-40.txt, 01-41.txt, 01-42.txt, 01-43.txt, 01-44.txt, 01-45.txt, 01-46.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
1 ms |
256 KB |
01-02.txt |
AC |
1 ms |
256 KB |
01-03.txt |
AC |
1 ms |
256 KB |
01-04.txt |
AC |
1 ms |
256 KB |
01-05.txt |
AC |
1 ms |
256 KB |
01-06.txt |
AC |
1 ms |
380 KB |
01-07.txt |
AC |
2 ms |
380 KB |
01-08.txt |
AC |
2 ms |
380 KB |
01-09.txt |
AC |
1 ms |
256 KB |
01-10.txt |
AC |
2 ms |
380 KB |
01-11.txt |
AC |
2 ms |
380 KB |
01-12.txt |
AC |
2 ms |
380 KB |
01-13.txt |
AC |
2 ms |
380 KB |
01-14.txt |
AC |
1 ms |
256 KB |
01-15.txt |
AC |
2 ms |
380 KB |
01-16.txt |
AC |
2 ms |
380 KB |
01-17.txt |
AC |
2 ms |
380 KB |
01-18.txt |
AC |
2 ms |
380 KB |
01-19.txt |
AC |
1 ms |
256 KB |
01-20.txt |
AC |
2 ms |
380 KB |
01-21.txt |
AC |
2 ms |
380 KB |
01-22.txt |
AC |
1 ms |
256 KB |
01-23.txt |
AC |
1 ms |
256 KB |
01-24.txt |
AC |
2 ms |
380 KB |
01-25.txt |
AC |
2 ms |
380 KB |
01-26.txt |
AC |
1 ms |
256 KB |
01-27.txt |
AC |
1 ms |
380 KB |
01-28.txt |
AC |
2 ms |
380 KB |
01-29.txt |
AC |
2 ms |
380 KB |
01-30.txt |
AC |
2 ms |
380 KB |
01-31.txt |
AC |
1 ms |
256 KB |
01-32.txt |
AC |
2 ms |
380 KB |
01-33.txt |
AC |
1 ms |
256 KB |
01-34.txt |
AC |
2 ms |
380 KB |
01-35.txt |
AC |
2 ms |
380 KB |
01-36.txt |
AC |
2 ms |
380 KB |
01-37.txt |
AC |
1 ms |
256 KB |
01-38.txt |
AC |
2 ms |
380 KB |
01-39.txt |
AC |
2 ms |
380 KB |
01-40.txt |
AC |
2 ms |
380 KB |
01-41.txt |
AC |
2 ms |
380 KB |
01-42.txt |
AC |
2 ms |
380 KB |
01-43.txt |
AC |
2 ms |
380 KB |
01-44.txt |
AC |
2 ms |
380 KB |
01-45.txt |
AC |
2 ms |
380 KB |
01-46.txt |
AC |
2 ms |
380 KB |
02-01.txt |
AC |
87 ms |
8444 KB |
02-02.txt |
AC |
91 ms |
10492 KB |
02-03.txt |
AC |
102 ms |
7548 KB |
02-04.txt |
AC |
95 ms |
8572 KB |
02-05.txt |
AC |
1 ms |
380 KB |
02-06.txt |
AC |
1 ms |
380 KB |
02-07.txt |
AC |
43 ms |
7548 KB |
02-08.txt |
AC |
46 ms |
8956 KB |
02-09.txt |
AC |
43 ms |
10236 KB |
02-10.txt |
AC |
48 ms |
7676 KB |
02-11.txt |
AC |
43 ms |
8700 KB |
02-12.txt |
AC |
48 ms |
8060 KB |
sample-01.txt |
AC |
1 ms |
256 KB |
sample-02.txt |
AC |
1 ms |
256 KB |