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
AC × 3
AC × 29
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