Submission #1135960
Source Code Expand
/+ dub.sdl:
name "F"
dependency "dcomp" version=">=0.6.0"
+/
import std.stdio, std.range, std.conv, std.algorithm;
import std.math;
// import dcomp.foundation;
// import dcomp.scanner;
// import dcomp.array;
// import dcomp.algorithm;
// import dcomp.graph.scc;
// import dcomp.twosat;
import core.bitop : bsr;
immutable INF = 10^^9 + 10^^7;
int n;
int[] pos;
//md より大きくは出来ない
bool solve(int md) {
int[2][] v;
foreach (int i, d; pos) {
v ~= [d, i];
}
v = v.sort!((l, r) => cmp(l[], r[]) == -1).array;
int m = v.length.to!int;
int lg = m.bsr;
if ((2^^lg) < m) lg++;
m = 1<<lg;
int getI(int i, int x) {
return binSearch!(idx => cmp(v[idx][], [x, i].fixed[]) != -1)(-1, v.length.to!int);
}
auto sat = TwoSat(2*n + 2*m);
foreach (i; 0..n) {
// exactly 1 true
sat.addCond(2*i, true, 2*i+1, true);
sat.addCond(2*i, false, 2*i+1, false);
}
//make segtree
foreach (i; 1..m) {
sat.addCond(2*n+2*i, false, 2*n+i, true);
sat.addCond(2*n+2*i+1, false, 2*n+i, true);
}
void query(int a, int b, int i, int l = 0, int r = m, int k = 1) {
if (b <= l || r <= a) return;
if (a <= l && r <= b) {
sat.addCond(i, false, 2*n+k, false);
return;
}
int md = (l+r)/2;
query(a, b, i, l, md, 2*k);
query(a, b, i, md, r, 2*k+1);
}
foreach (int i, x; pos) {
int idx = getI(i, x);
query(getI(-1, x-md), idx, i);
query(idx+1, getI(INF, x+md), i);
sat.addCond(i, false, 2*n + m + idx, true);
}
return sat.exec() == false;
}
int main() {
auto sc = new Scanner(stdin);
sc.read(n);
pos = new int[2*n];
pos.each!((ref x) => sc.read(x));
writeln(binSearch!(md => solve(md))(-1, INF/(n-1)));
return 0;
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/array.d */
// module dcomp.array;
T[N] fixed(T, int N)(T[N] a) {return a;}
//this is not reference type!(please attention to copy)
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;
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 clear() {
len = 0;
}
T[] data() {
return (_data) ? _data[0..len] : null;
}
}
unittest {
import std.stdio, std.algorithm;
auto u = FastAppender!(int[])();
u ~= 4; u ~= 5;
assert(equal(u.data, [4, 5]));
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/twosat.d */
// module dcomp.twosat;
// import dcomp.graph.scc;
// import dcomp.array;
struct TwoSat {
bool[] res;
struct Edge {int to;}
FastAppender!(Edge[])[] g;
// add ((a == aExp) || (b == bExp))
void addCond(int a, bool aExp, int b, bool bExp) {
g[2*a+(aExp?0:1)] ~= Edge(2*b+(bExp?1:0));
g[2*b+(bExp?0:1)] ~= Edge(2*a+(aExp?1:0));
}
bool exec() {
import std.array : array;
import std.algorithm : map;
import std.conv : to;
int n = res.length.to!int;
auto sccInfo = scc(g.map!(v => v.data).array);
for (int i = 0; i < n; i++) {
if (sccInfo.id[2*i] == sccInfo.id[2*i+1]) return false;
res[i] = sccInfo.id[2*i] < sccInfo.id[2*i+1];
}
return true;
}
this(int n) {
res = new bool[n];
g = new FastAppender!(Edge[])[](2*n);
}
}
unittest {
import std.algorithm, std.conv, std.stdio, std.range;
import std.random;
import std.typecons;
import std.datetime;
struct E {int to;}
writeln("TwoSat Random10000");
void f() {
int n = uniform(1, 50);
int m = uniform(1, 100);
auto ans = new bool[n];
auto sat = TwoSat(n);
ans.each!((ref x) => x = uniform(0, 2) == 1);
struct N {int i; bool expect;}
N[2][] conds;
foreach (i; 0..m) {
int x = uniform(0, n);
int y = uniform(0, n);
while (true) {
bool f = uniform(0, 2) == 1;
bool g = uniform(0, 2) == 1;
if (ans[x] != f && ans[y] != g) continue;
sat.addCond(x, f, y, g);
conds ~= [N(x, f), N(y, g)];
break;
}
}
assert(sat.exec());
auto res = sat.res;
foreach (cond; conds) {
int x = cond[0].i;
bool f = cond[0].expect;
int y = cond[1].i;
bool g = cond[1].expect;
assert(res[x] == f || res[y] == g);
}
}
auto ti = benchmark!(f)(10000);
writeln(ti[0].msecs, "ms");
}
/* IMPORT /Users/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;
}
string[] buf;
private bool succ() {
while (!buf.length) {
if (f.eof) return false;
buf = f.readln.split;
}
return true;
}
private bool readSingle(T)(ref T x) {
if (!succ()) return false;
static if (isArray!T) {
alias E = ElementType!T;
static if (isSomeChar!E) {
//string or char[10] etc
x = buf.front;
buf.popFront;
} else {
static if (isStaticArray!T) {
//static
assert(buf.length == T.length);
}
x = buf.map!(to!E).array;
buf.length = 0;
}
} else {
x = buf.front.to!T;
buf.popFront;
}
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);
}
}
}
unittest {
import std.path : buildPath;
import std.file : tempDir;
import std.algorithm : equal;
import std.stdio : File;
string fileName = buildPath(tempDir, "kyuridenanmaida.txt");
auto fout = File(fileName, "w");
fout.writeln("1 2 3");
fout.writeln("ab cde");
fout.writeln("1.0 1.0 2.0");
fout.close;
Scanner sc = new Scanner(File(fileName, "r"));
int a;
int[2] b;
char[2] c;
string d;
double e;
double[] f;
sc.read(a, b, c, d, e, f);
assert(a == 1);
assert(equal(b[], [2, 3]));
assert(equal(c[], "ab"));
assert(equal(d, "cde"));
assert(e == 1.0);
assert(equal(f, [1.0, 2.0]));
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/algorithm.d */
// module dcomp.algorithm;
import std.range.primitives;
import std.traits : isFloatingPoint, isIntegral;
//[0,0,0,...,1,1,1]で、初めて1となる場所を探す。pred(l) == 0, pred(r) == 1と仮定
T binSearch(alias pred, T)(T l, T r) if (isIntegral!T) {
while (r-l > 1) {
T md = (l+r)/2;
if (!pred(md)) l = md;
else r = md;
}
return r;
}
T binSearch(alias pred, T)(T l, T r, int cnt = 60) if (isFloatingPoint!T) {
foreach (i; 0..cnt) {
T md = (l+r)/2;
if (!pred(md)) l = md;
else r = md;
}
return r;
}
Rotator!Range rotator(Range)(Range r) {
return Rotator!Range(r);
}
struct Rotator(Range)
if (isForwardRange!Range && hasLength!Range) {
size_t cnt;
Range start, now;
this(Range r) {
cnt = 0;
start = r.save;
now = r.save;
}
this(this) {
start = start.save;
now = now.save;
}
@property bool empty() {
return now.empty;
}
@property auto front() {
assert(!now.empty);
import std.range : take, chain;
return chain(now, start.take(cnt));
}
@property Rotator!Range save() {
return this;
}
void popFront() {
cnt++;
now.popFront;
}
}
E minimum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed)
if (isInputRange!Range && !isInfinite!Range) {
import std.algorithm, std.functional;
return reduce!((a, b) => binaryFun!pred(a, b) ? a : b)(seed, range);
}
ElementType!Range minimum(alias pred = "a < b", Range)(Range range) {
assert(!range.empty, "range must not empty");
auto e = range.front; range.popFront;
return minimum!pred(range, e);
}
E maximum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed)
if (isInputRange!Range && !isInfinite!Range) {
import std.algorithm, std.functional;
return reduce!((a, b) => binaryFun!pred(a, b) ? b : a)(seed, range);
}
ElementType!Range maximum(alias pred = "a < b", Range)(Range range) {
assert(!range.empty, "range must not empty");
auto e = range.front; range.popFront;
return maximum!pred(range, e);
}
unittest {
assert(minimum([2, 1, 3]) == 1);
assert(minimum!"a > b"([2, 1, 3]) == 3);
assert(minimum([2, 1, 3], -1) == -1);
assert(minimum!"a > b"([2, 1, 3], 100) == 100);
assert(maximum([2, 1, 3]) == 3);
assert(maximum!"a > b"([2, 1, 3]) == 1);
assert(maximum([2, 1, 3], 100) == 100);
assert(maximum!"a > b"([2, 1, 3], -1) == -1);
}
bool[ElementType!Range] toMap(Range)(Range r) {
import std.algorithm : each;
bool[ElementType!Range] res;
r.each!(a => res[a] = true);
return res;
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/foundation.d */
// module dcomp.foundation;
//fold(for old compiler)
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);
}
}
}
unittest {
import std.stdio;
auto l = [1, 2, 3, 4, 5];
assert(l.fold!"a+b"(10) == 25);
}
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/graph/scc.d */
// module dcomp.graph.scc;
struct SCC {
int[] id; // vertex id -> scc id
int[][] groups; // scc id -> scc vertexs
int count; // scc count
this(int n) {
id = new int[n];
}
}
// import dcomp.array;
SCC scc(T)(T g) {
import std.array : appender;
import std.range;
import std.algorithm : each, map;
import std.conv : to;
int n = g.length.to!int;
//make reverse graph
struct Edge {int to;}
FastAppender!(Edge[])[] rg_buf = new FastAppender!(Edge[])[](n);
g.each!((i, v) => v.each!(e => rg_buf[e.to] ~= Edge(i.to!int)));
auto rg = rg_buf.map!(v => v.data).array;
auto sccInfo = SCC(n);
with (sccInfo) {
auto used = new bool[n];
//make backorder list
auto vs = appender!(int[])();
void dfs(int v) {
used[v] = true;
foreach (e; g[v]) {
if (used[e.to]) continue;
dfs(e.to);
}
vs ~= v;
}
foreach (i; 0..n) {
if (used[i]) continue;
dfs(i);
}
used[] = false;
count = 0;
auto buf = appender!(int[])();
void rdfs(int v) {
used[v] = true;
id[v] = count;
buf ~= v;
foreach (e; rg[v]) {
if (used[e.to]) continue;
rdfs(e.to);
}
}
auto groups_buf = appender!(int[][])();
foreach_reverse (i; vs.data) {
if (used[i]) continue;
rdfs(i);
groups_buf ~= buf.data.dup;
buf.clear();
count++;
}
groups = groups_buf.data;
}
return sccInfo;
}
unittest {
import std.algorithm, std.conv, std.stdio, std.range;
import std.random;
import std.typecons;
import std.datetime;
struct E {int to;}
writeln("SCC Random1000");
void f() {
int n = uniform(1, 50);
int p = uniform(1, 50);
E[][] g = new E[][n];
bool[][] naive = new bool[][](n, n);
foreach (i; 0..n) {
foreach (j; 0..n) {
if (i == j) continue;
if (uniform(0, 100) < p) {
g[i] ~= E(j);
naive[i][j] = true;
}
}
}
auto sccInfo = scc(g);
foreach (k; 0..n) {
foreach (i; 0..n) {
foreach (j; 0..n) {
naive[i][j] |= naive[i][k] && naive[k][j];
}
}
}
foreach (i; 0..n) {
foreach (j; i+1..n) {
bool same = sccInfo.id[i] == sccInfo.id[j];
if (same) {
assert(naive[i][j] && naive[j][i]);
} else {
assert(!naive[i][j] || !naive[j][i]);
if (sccInfo.id[i] < sccInfo.id[j]) {
assert(!naive[j][i]);
} else {
assert(!naive[i][j]);
}
}
}
}
}
auto ti = benchmark!(f)(1000);
writeln(ti[0].msecs, "ms");
}
Submission Info
Submission Time |
|
Task |
F - Flags |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
1200 |
Code Size |
14480 Byte |
Status |
AC |
Exec Time |
1789 ms |
Memory |
139900 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1200 / 1200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
All |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt, 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt |
Case Name |
Status |
Exec Time |
Memory |
00_example_01.txt |
AC |
1 ms |
508 KB |
00_example_02.txt |
AC |
2 ms |
636 KB |
00_example_03.txt |
AC |
4 ms |
3836 KB |
01.txt |
AC |
45 ms |
4988 KB |
02.txt |
AC |
20 ms |
4860 KB |
03.txt |
AC |
7 ms |
2940 KB |
04.txt |
AC |
10 ms |
3580 KB |
05.txt |
AC |
11 ms |
5116 KB |
06.txt |
AC |
1110 ms |
86988 KB |
07.txt |
AC |
1221 ms |
74672 KB |
08.txt |
AC |
1136 ms |
75116 KB |
09.txt |
AC |
42 ms |
4604 KB |
10.txt |
AC |
20 ms |
4732 KB |
11.txt |
AC |
8 ms |
5116 KB |
12.txt |
AC |
10 ms |
4988 KB |
13.txt |
AC |
11 ms |
4860 KB |
14.txt |
AC |
1027 ms |
70772 KB |
15.txt |
AC |
1104 ms |
60868 KB |
16.txt |
AC |
1098 ms |
70184 KB |
17.txt |
AC |
48 ms |
3324 KB |
18.txt |
AC |
21 ms |
3452 KB |
19.txt |
AC |
1174 ms |
81804 KB |
20.txt |
AC |
1195 ms |
80092 KB |
21.txt |
AC |
1479 ms |
84208 KB |
22.txt |
AC |
1506 ms |
84452 KB |
23.txt |
AC |
1789 ms |
139900 KB |
24.txt |
AC |
1420 ms |
95468 KB |
25.txt |
AC |
1512 ms |
107516 KB |
26.txt |
AC |
1202 ms |
88500 KB |
27.txt |
AC |
1 ms |
380 KB |