Submission #2409099
Source Code Expand
import std.stdio;
import std.string;
import std.format;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;
import std.concurrency;
import std.traits;
import std.uni;
import core.bitop : popcnt;
alias Generator = std.concurrency.Generator;
enum long INF = long.max/3;
enum long MOD = 10L^^9+7;
void main() {
long N;
scanln(N);
long[] as = readln.split.to!(long[]);
if (as.all!"a<0") {
as.maxElement.writeln;
(N-1).writeln;
long i = as.enumerate.maxElement!"a.value".index;
foreach_reverse(j; i+1..N) {
writeln(j+1);
}
foreach(j; 0..i) {
writeln(0+1);
}
return;
}
long[] xs = as.enumerate.filter!"a.value>=0".map!"a.index".filter!"a%2==0".array.to!(long[]);
long[] ys = as.enumerate.filter!"a.value>=0".map!"a.index".filter!"a%2==1".array.to!(long[]);
if (xs.map!(x => as[x]).sum < ys.map!(y => as[y]).sum) {
xs = ys;
}
assert(!xs.empty);
long[] ts;
long[][] uss;
foreach(i; 0..N) {
if (i==xs.front) break;
ts ~= i;
}
foreach_reverse(i; 0..N) {
if (i==xs.back) break;
ts ~= i;
}
foreach(i; 1..xs.length) {
long x = xs[i-1];
long y = xs[i];
uss ~= iota(x, (x+y)/2).map!"a+1".retro.array;
}
xs.map!(x => as[x]).sum.writeln;
writeln(ts.length + uss.map!"a.length".sum);
long[] bs = N.iota.array;
foreach(t; ts) {
long i = bs.countUntil(t);
assert(i >= 0);
writeln(i+1);
if (i==0 || i==bs.length-1) {
bs = bs[0..i] ~ bs[i+1..$];
}
}
foreach(us; uss) {
long i = bs.countUntil(us.front);
assert(i >= us.length);
foreach_reverse(j; i+1-us.length..i+1) {
writeln(j+1);
bs = bs[0..i-1] ~ bs[i..i+1] ~ bs[i+2..$];
}
}
}
// ----------------------------------------------
mixin template Constructor() {
import std.traits : FieldNameTuple;
this(Args...)(Args args) {
// static foreach(i, v; args) {
foreach(i, v; args) {
mixin("this." ~ FieldNameTuple!(typeof(this))[i]) = v;
}
}
}
void scanln(Args...)(auto ref Args args) {
import std.meta;
template getFormat(T) {
static if (isIntegral!T) {
enum getFormat = "%d";
} else static if (isFloatingPoint!T) {
enum getFormat = "%g";
} else static if (isSomeString!T || isSomeChar!T) {
enum getFormat = "%s";
} else {
static assert(false);
}
}
enum string str = [staticMap!(getFormat, Args)].join(" ") ~ "\n";
// readf!str(args);
mixin("str.readf(" ~ Args.length.iota.map!(i => "&args[%d]".format(i)).join(", ") ~ ");");
}
void times(alias fun)(long n) {
// n.iota.each!(i => fun());
foreach(i; 0..n) fun();
}
auto rep(alias fun, T = typeof(fun()))(long n) {
// return n.iota.map!(i => fun()).array;
T[] res = new T[n];
foreach(ref e; res) e = fun();
return res;
}
T ceil(T)(T x, T y) if (isIntegral!T || is(T == BigInt)) {
// `(x+y-1)/y` will only work for positive numbers ...
T t = x / y;
if (t * y < x) t++;
return t;
}
T floor(T)(T x, T y) if (isIntegral!T || is(T == BigInt)) {
T t = x / y;
if (t * y > x) t--;
return t;
}
// fold was added in D 2.071.0
static if (__VERSION__ < 2071) {
template fold(fun...) if (fun.length >= 1) {
auto fold(R, S...)(R r, S seed) {
static if (S.length < 2) {
return reduce!fun(seed, r);
} else {
return reduce!fun(tuple(seed), r);
}
}
}
}
// cumulativeFold was added in D 2.072.0
static if (__VERSION__ < 2072) {
template cumulativeFold(fun...)
if (fun.length >= 1)
{
import std.meta : staticMap;
private alias binfuns = staticMap!(binaryFun, fun);
auto cumulativeFold(R)(R range)
if (isInputRange!(Unqual!R))
{
return cumulativeFoldImpl(range);
}
auto cumulativeFold(R, S)(R range, S seed)
if (isInputRange!(Unqual!R))
{
static if (fun.length == 1)
return cumulativeFoldImpl(range, seed);
else
return cumulativeFoldImpl(range, seed.expand);
}
private auto cumulativeFoldImpl(R, Args...)(R range, ref Args args)
{
import std.algorithm.internal : algoFormat;
static assert(Args.length == 0 || Args.length == fun.length,
algoFormat("Seed %s does not have the correct amount of fields (should be %s)",
Args.stringof, fun.length));
static if (args.length)
alias State = staticMap!(Unqual, Args);
else
alias State = staticMap!(ReduceSeedType!(ElementType!R), binfuns);
foreach (i, f; binfuns)
{
static assert(!__traits(compiles, f(args[i], e)) || __traits(compiles,
{ args[i] = f(args[i], e); }()),
algoFormat("Incompatible function/seed/element: %s/%s/%s",
fullyQualifiedName!f, Args[i].stringof, E.stringof));
}
static struct Result
{
private:
R source;
State state;
this(R range, ref Args args)
{
source = range;
if (source.empty)
return;
foreach (i, f; binfuns)
{
static if (args.length)
state[i] = f(args[i], source.front);
else
state[i] = source.front;
}
}
public:
@property bool empty()
{
return source.empty;
}
@property auto front()
{
assert(!empty, "Attempting to fetch the front of an empty cumulativeFold.");
static if (fun.length > 1)
{
import std.typecons : tuple;
return tuple(state);
}
else
{
return state[0];
}
}
void popFront()
{
assert(!empty, "Attempting to popFront an empty cumulativeFold.");
source.popFront;
if (source.empty)
return;
foreach (i, f; binfuns)
state[i] = f(state[i], source.front);
}
static if (isForwardRange!R)
{
@property auto save()
{
auto result = this;
result.source = source.save;
return result;
}
}
static if (hasLength!R)
{
@property size_t length()
{
return source.length;
}
}
}
return Result(range, args);
}
}
}
// minElement/maxElement was added in D 2.072.0
static if (__VERSION__ < 2072) {
private auto extremum(alias map, alias selector = "a < b", Range)(Range r)
if (isInputRange!Range && !isInfinite!Range &&
is(typeof(unaryFun!map(ElementType!(Range).init))))
in
{
assert(!r.empty, "r is an empty range");
}
body
{
alias Element = ElementType!Range;
Unqual!Element seed = r.front;
r.popFront();
return extremum!(map, selector)(r, seed);
}
private auto extremum(alias map, alias selector = "a < b", Range,
RangeElementType = ElementType!Range)
(Range r, RangeElementType seedElement)
if (isInputRange!Range && !isInfinite!Range &&
!is(CommonType!(ElementType!Range, RangeElementType) == void) &&
is(typeof(unaryFun!map(ElementType!(Range).init))))
{
alias mapFun = unaryFun!map;
alias selectorFun = binaryFun!selector;
alias Element = ElementType!Range;
alias CommonElement = CommonType!(Element, RangeElementType);
Unqual!CommonElement extremeElement = seedElement;
alias MapType = Unqual!(typeof(mapFun(CommonElement.init)));
MapType extremeElementMapped = mapFun(extremeElement);
// direct access via a random access range is faster
static if (isRandomAccessRange!Range)
{
foreach (const i; 0 .. r.length)
{
MapType mapElement = mapFun(r[i]);
if (selectorFun(mapElement, extremeElementMapped))
{
extremeElement = r[i];
extremeElementMapped = mapElement;
}
}
}
else
{
while (!r.empty)
{
MapType mapElement = mapFun(r.front);
if (selectorFun(mapElement, extremeElementMapped))
{
extremeElement = r.front;
extremeElementMapped = mapElement;
}
r.popFront();
}
}
return extremeElement;
}
private auto extremum(alias selector = "a < b", Range)(Range r)
if (isInputRange!Range && !isInfinite!Range &&
!is(typeof(unaryFun!selector(ElementType!(Range).init))))
{
alias Element = ElementType!Range;
Unqual!Element seed = r.front;
r.popFront();
return extremum!selector(r, seed);
}
private auto extremum(alias selector = "a < b", Range,
RangeElementType = ElementType!Range)
(Range r, RangeElementType seedElement)
if (isInputRange!Range && !isInfinite!Range &&
!is(CommonType!(ElementType!Range, RangeElementType) == void) &&
!is(typeof(unaryFun!selector(ElementType!(Range).init))))
{
alias Element = ElementType!Range;
alias CommonElement = CommonType!(Element, RangeElementType);
Unqual!CommonElement extremeElement = seedElement;
alias selectorFun = binaryFun!selector;
// direct access via a random access range is faster
static if (isRandomAccessRange!Range)
{
foreach (const i; 0 .. r.length)
{
if (selectorFun(r[i], extremeElement))
{
extremeElement = r[i];
}
}
}
else
{
while (!r.empty)
{
if (selectorFun(r.front, extremeElement))
{
extremeElement = r.front;
}
r.popFront();
}
}
return extremeElement;
}
auto minElement(Range)(Range r)
if (isInputRange!Range && !isInfinite!Range)
{
return extremum(r);
}
auto minElement(alias map, Range, RangeElementType = ElementType!Range)
(Range r, RangeElementType seed)
if (isInputRange!Range && !isInfinite!Range &&
!is(CommonType!(ElementType!Range, RangeElementType) == void))
{
return extremum!map(r, seed);
}
auto minElement(Range, RangeElementType = ElementType!Range)
(Range r, RangeElementType seed)
if (isInputRange!Range && !isInfinite!Range &&
!is(CommonType!(ElementType!Range, RangeElementType) == void))
{
return extremum(r, seed);
}
auto maxElement(alias map, Range)(Range r)
if (isInputRange!Range && !isInfinite!Range)
{
return extremum!(map, "a > b")(r);
}
auto maxElement(Range)(Range r)
if (isInputRange!Range && !isInfinite!Range)
{
return extremum!`a > b`(r);
}
auto maxElement(alias map, Range, RangeElementType = ElementType!Range)
(Range r, RangeElementType seed)
if (isInputRange!Range && !isInfinite!Range &&
!is(CommonType!(ElementType!Range, RangeElementType) == void))
{
return extremum!(map, "a > b")(r, seed);
}
auto maxElement(Range, RangeElementType = ElementType!Range)
(Range r, RangeElementType seed)
if (isInputRange!Range && !isInfinite!Range &&
!is(CommonType!(ElementType!Range, RangeElementType) == void))
{
return extremum!`a > b`(r, seed);
}
}
Submission Info
Submission Time |
|
Task |
E - Both Sides Merger |
User |
arkark |
Language |
D (LDC 0.17.0) |
Score |
0 |
Code Size |
13384 Byte |
Status |
RE |
Exec Time |
3 ms |
Memory |
4348 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example_0, example_1, example_2, example_3 |
All |
allneg_0, allneg_1, allneg_2, bigans_0, bigans_1, bigans_2, bigans_3, bigans_4, bigans_5, bigans_6, bigans_7, bigans_8, bigans_9, example_0, example_1, example_2, example_3, maxrand_0, maxrand_1, maxrand_10, maxrand_11, maxrand_12, maxrand_13, maxrand_14, maxrand_15, maxrand_16, maxrand_17, maxrand_18, maxrand_19, maxrand_2, maxrand_20, maxrand_21, maxrand_22, maxrand_23, maxrand_24, maxrand_25, maxrand_26, maxrand_27, maxrand_28, maxrand_29, maxrand_3, maxrand_4, maxrand_5, maxrand_6, maxrand_7, maxrand_8, maxrand_9, rand_0, rand_1, rand_2, rand_3, rand_4, rand_5, rand_6, rand_7, rand_8, rand_9 |
Case Name |
Status |
Exec Time |
Memory |
allneg_0 |
AC |
1 ms |
380 KB |
allneg_1 |
AC |
1 ms |
380 KB |
allneg_2 |
AC |
1 ms |
380 KB |
bigans_0 |
WA |
3 ms |
4220 KB |
bigans_1 |
WA |
2 ms |
2940 KB |
bigans_2 |
WA |
2 ms |
2940 KB |
bigans_3 |
WA |
2 ms |
3068 KB |
bigans_4 |
WA |
3 ms |
4220 KB |
bigans_5 |
WA |
2 ms |
3324 KB |
bigans_6 |
WA |
2 ms |
2940 KB |
bigans_7 |
WA |
2 ms |
2940 KB |
bigans_8 |
WA |
2 ms |
3196 KB |
bigans_9 |
WA |
3 ms |
3964 KB |
example_0 |
AC |
1 ms |
256 KB |
example_1 |
AC |
1 ms |
256 KB |
example_2 |
AC |
1 ms |
256 KB |
example_3 |
AC |
1 ms |
256 KB |
maxrand_0 |
RE |
2 ms |
2940 KB |
maxrand_1 |
WA |
3 ms |
4092 KB |
maxrand_10 |
RE |
2 ms |
3452 KB |
maxrand_11 |
WA |
3 ms |
4348 KB |
maxrand_12 |
RE |
3 ms |
4220 KB |
maxrand_13 |
RE |
2 ms |
2940 KB |
maxrand_14 |
WA |
2 ms |
2940 KB |
maxrand_15 |
WA |
2 ms |
3580 KB |
maxrand_16 |
RE |
2 ms |
3324 KB |
maxrand_17 |
WA |
2 ms |
2940 KB |
maxrand_18 |
WA |
2 ms |
3580 KB |
maxrand_19 |
WA |
3 ms |
3836 KB |
maxrand_2 |
WA |
2 ms |
2940 KB |
maxrand_20 |
WA |
2 ms |
2940 KB |
maxrand_21 |
WA |
2 ms |
3068 KB |
maxrand_22 |
WA |
2 ms |
3708 KB |
maxrand_23 |
WA |
3 ms |
4092 KB |
maxrand_24 |
RE |
2 ms |
2940 KB |
maxrand_25 |
WA |
2 ms |
3964 KB |
maxrand_26 |
RE |
3 ms |
3836 KB |
maxrand_27 |
WA |
2 ms |
3068 KB |
maxrand_28 |
RE |
3 ms |
3964 KB |
maxrand_29 |
WA |
3 ms |
4220 KB |
maxrand_3 |
WA |
2 ms |
2940 KB |
maxrand_4 |
RE |
2 ms |
3580 KB |
maxrand_5 |
RE |
3 ms |
3708 KB |
maxrand_6 |
RE |
2 ms |
3580 KB |
maxrand_7 |
RE |
3 ms |
4220 KB |
maxrand_8 |
WA |
2 ms |
2940 KB |
maxrand_9 |
WA |
2 ms |
2812 KB |
rand_0 |
RE |
2 ms |
1276 KB |
rand_1 |
WA |
1 ms |
508 KB |
rand_2 |
RE |
1 ms |
256 KB |
rand_3 |
RE |
2 ms |
892 KB |
rand_4 |
RE |
2 ms |
3708 KB |
rand_5 |
RE |
1 ms |
764 KB |
rand_6 |
RE |
2 ms |
3068 KB |
rand_7 |
RE |
1 ms |
764 KB |
rand_8 |
WA |
2 ms |
2940 KB |
rand_9 |
WA |
2 ms |
2812 KB |