Submission #1274349
Source Code Expand
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.6.0"
+/
import std.stdio, std.algorithm, std.range, std.conv;
import std.numeric, std.math;
// import dcomp.foundation, dcomp.scanner;
// import dcomp.algorithm;
immutable B = 400;
int n, m;
int[] a;
int calc() {
int R = 0;
int[] h = new int[2*n+10000];
int ma = -1;
long cnt = 0;
int[] rb = new int[B];
foreach (p; a) {
ma = max(ma, p);
h[p] = 10^^9;
int getR(int x) {
while (h[rb[x]] > x) rb[x]++;
return rb[x];
}
void succ() {
cnt++;
if (R <= p) return;
int q = binSearch!(q => h[p+q] <= q)(-1, min(2*n+8-p, h[p+1]));
h[p+q] = q;
p += q;
}
if (p < R) {
//first succ
int q = binSearch!(q => h[p+q] <= q)(0, 2*n+8-p);
h[p+q] = q;
p += q;
}
//big step
while (p < R && B <= h[p+1]) {
succ();
}
//small step
while (p < R) {
// int same_l = binSearch!(q => h[p+q] != h[p+1])(1, 2*n+8-p)-1;
// assert(same_l == getR(h[p+1]-1)-1-p);
int same_l = getR(h[p+1]-1)-1-p;
p += same_l / h[p+1] * h[p+1];
succ();
}
R = p;
}
return R;
}
int solve(int[] p) {
n = p.length.to!int;
int[] ma = new int[n];
ma[] = -1;
a = new int[n];
foreach (d; p) {
auto idx = binSearch!(i => d >= ma[i])(-1, n);
ma[idx] = d;
a[d] = idx;
}
m = a.maximum + 1;
reverse(a);
return calc();
}
int naive(int[] pp) {
int[] p = pp.dup;
n = p.length.to!int;
int cnt = 0;
bool[] used = new bool[n];
int[] buf = new int[n];
while (true) {
if (equal(p, iota(n))) break;
cnt++;
int ma = -1;
foreach (i, d; p) {
used[i] = ma < d;
ma = max(ma, d);
}
int c = 0;
foreach (i; 0..n) {
if (used[i]) continue;
buf[c] = p[i]; c++;
}
foreach (i; 0..n) {
if (!used[i]) continue;
buf[c] = p[i]; c++;
}
swap(p, buf);
}
return cnt;
}
void test(int n) {
import std.random;
auto a = iota(n).array;
a.randomShuffle;
writeln(solve(a));
/* int x = solve(a);
int y = naive(a);
if (x != y) {
writeln(a);
writeln(x, " ", y);
}
*/
}
int main() {
auto sc = new Scanner(stdin);
int dummy;
int[] p;
sc.read(dummy, p);
p[] -= 1;
writeln(solve(p));
// test(200000);
/* foreach (i; 0..10000) {
import std.random;
int n = uniform(4, 30);
auto a = iota(n).array;
a.randomShuffle;
int x = solve(a);
int y = naive(a);
if (x != y) {
writeln(a);
writeln(x, " ", y);
}
}*/
return 0;
}
/* 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) {
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/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/algorithm.d */
// module dcomp.algorithm;
import std.range.primitives;
import std.traits : isFloatingPoint, isIntegral;
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);
}
bool[ElementType!Range] toMap(Range)(Range r) {
import std.algorithm : each;
bool[ElementType!Range] res;
r.each!(a => res[a] = true);
return res;
}
Submission Info
Submission Time |
|
Task |
F - Strange Sorting |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
2400 |
Code Size |
8513 Byte |
Status |
AC |
Exec Time |
850 ms |
Memory |
11536 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
2400 / 2400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
All |
sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
AC |
846 ms |
11024 KB |
in10.txt |
AC |
850 ms |
11024 KB |
in11.txt |
AC |
848 ms |
11408 KB |
in12.txt |
AC |
820 ms |
11024 KB |
in13.txt |
AC |
824 ms |
11024 KB |
in14.txt |
AC |
833 ms |
11024 KB |
in15.txt |
AC |
838 ms |
11024 KB |
in16.txt |
AC |
838 ms |
11024 KB |
in17.txt |
AC |
837 ms |
11536 KB |
in18.txt |
AC |
826 ms |
11152 KB |
in19.txt |
AC |
829 ms |
11280 KB |
in2.txt |
AC |
798 ms |
11024 KB |
in20.txt |
AC |
807 ms |
11152 KB |
in21.txt |
AC |
44 ms |
11024 KB |
in22.txt |
AC |
46 ms |
11024 KB |
in23.txt |
AC |
1 ms |
256 KB |
in3.txt |
AC |
843 ms |
11024 KB |
in4.txt |
AC |
838 ms |
11024 KB |
in5.txt |
AC |
835 ms |
11024 KB |
in6.txt |
AC |
831 ms |
11536 KB |
in7.txt |
AC |
832 ms |
11280 KB |
in8.txt |
AC |
835 ms |
11152 KB |
in9.txt |
AC |
832 ms |
11024 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
1 ms |
256 KB |