Submission #1227561
Source Code Expand
/+ dub.sdl: name "A" dependency "dcomp" version=">=0.6.0" +/ import std.stdio, std.algorithm, std.range, std.conv; import std.typecons; import std.bigint; // import dcomp.foundation, dcomp.scanner; int main() { auto sc = new Scanner(stdin); long n, m; sc.read(n, m); long[][] a_buf = new long[][](n, m); foreach (i; 0..n) { sc.read(a_buf[i]); if (i && a_buf[i-1][0] > a_buf[i][0]) { writeln(-1); return 0; } } // writeln(a); BigInt[][] a = new BigInt[][](n, m); foreach (i; 0..n) { foreach (j; 0..m) { a[i][j] = a_buf[i][j]; } } long co = 0; foreach (i; 1..n) { while (cmp(a[i-1], a[i]) != -1) { co++; foreach (j; 1..m) { a[i][j] += a[i][j-1]; } } } writeln(co); return 0; } /* IMPORT /home/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); } } 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) { //string or char[10] etc //todo optimize 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) { //static 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); } } } 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])); } unittest { import std.path : buildPath; import std.file : tempDir; import std.algorithm : equal; import std.stdio : File, writeln; import std.datetime; string fileName = buildPath(tempDir, "kyuridenanmaida.txt"); auto fout = File(fileName, "w"); foreach (i; 0..1_000_000) { fout.writeln(3*i, " ", 3*i+1, " ", 3*i+2); } fout.close; writeln("Scanner Speed Test(3*1,000,000 int)"); StopWatch sw; sw.start; Scanner sc = new Scanner(File(fileName, "r")); foreach (i; 0..500_000) { int a, b, c; sc.read(a, b, c); assert(a == 3*i); assert(b == 3*i+1); assert(c == 3*i+2); } foreach (i; 500_000..700_000) { int[3] d; sc.read(d); int a = d[0], b = d[1], c = d[2]; assert(a == 3*i); assert(b == 3*i+1); assert(c == 3*i+2); } foreach (i; 700_000..1_000_000) { int[] d; sc.read(d); assert(d.length == 3); int a = d[0], b = d[1], c = d[2]; assert(a == 3*i); assert(b == 3*i+1); assert(c == 3*i+2); } writeln(sw.peek.msecs, "ms"); }
Submission Info
Submission Time | |
---|---|
Task | B - Takahashi the Magician |
User | yosupo |
Language | D (LDC 0.17.0) |
Score | 200 |
Code Size | 6004 Byte |
Status | TLE |
Exec Time | 2105 ms |
Memory | 110460 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 0 / 800 | 0 / 200 | ||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_1.txt, sample_2.txt, sample_3.txt |
subtask1 | sample_1.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 | sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt |
All | sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, sample_1.txt, sample_2.txt, sample_3.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
hack_1.txt | AC | 1 ms | 256 KB |
hack_2.txt | AC | 1 ms | 256 KB |
hack_3.txt | AC | 1 ms | 256 KB |
hack_4.txt | AC | 1 ms | 256 KB |
hack_5.txt | AC | 1 ms | 256 KB |
sample_1.txt | AC | 1 ms | 256 KB |
sample_2.txt | AC | 1 ms | 256 KB |
sample_3.txt | AC | 1 ms | 256 KB |
subtask_1_1.txt | AC | 2 ms | 508 KB |
subtask_1_10.txt | AC | 2 ms | 508 KB |
subtask_1_11.txt | AC | 276 ms | 59004 KB |
subtask_1_12.txt | AC | 2 ms | 636 KB |
subtask_1_13.txt | AC | 3 ms | 636 KB |
subtask_1_14.txt | AC | 1 ms | 256 KB |
subtask_1_15.txt | AC | 276 ms | 58620 KB |
subtask_1_16.txt | AC | 268 ms | 56572 KB |
subtask_1_17.txt | AC | 268 ms | 55036 KB |
subtask_1_18.txt | AC | 269 ms | 58620 KB |
subtask_1_19.txt | AC | 1 ms | 256 KB |
subtask_1_2.txt | AC | 1 ms | 256 KB |
subtask_1_20.txt | AC | 2 ms | 380 KB |
subtask_1_3.txt | AC | 2 ms | 380 KB |
subtask_1_4.txt | AC | 2 ms | 636 KB |
subtask_1_5.txt | AC | 5 ms | 1148 KB |
subtask_1_6.txt | AC | 9 ms | 1276 KB |
subtask_1_7.txt | AC | 9 ms | 1276 KB |
subtask_1_8.txt | AC | 275 ms | 58876 KB |
subtask_1_9.txt | AC | 86 ms | 28284 KB |
subtask_2_1.txt | AC | 448 ms | 23292 KB |
subtask_2_10.txt | AC | 351 ms | 28924 KB |
subtask_2_11.txt | TLE | 2104 ms | 109564 KB |
subtask_2_12.txt | TLE | 2104 ms | 110204 KB |
subtask_2_13.txt | TLE | 2104 ms | 83068 KB |
subtask_2_14.txt | TLE | 2105 ms | 108412 KB |
subtask_2_15.txt | AC | 35 ms | 6652 KB |
subtask_2_16.txt | AC | 5 ms | 10364 KB |
subtask_2_17.txt | AC | 4 ms | 8956 KB |
subtask_2_18.txt | TLE | 2104 ms | 108668 KB |
subtask_2_19.txt | TLE | 2103 ms | 380 KB |
subtask_2_2.txt | TLE | 2105 ms | 108668 KB |
subtask_2_20.txt | AC | 6 ms | 892 KB |
subtask_2_21.txt | AC | 6 ms | 1148 KB |
subtask_2_22.txt | AC | 12 ms | 1276 KB |
subtask_2_23.txt | AC | 7 ms | 1276 KB |
subtask_2_24.txt | AC | 12 ms | 1276 KB |
subtask_2_25.txt | AC | 2 ms | 508 KB |
subtask_2_26.txt | AC | 19 ms | 3708 KB |
subtask_2_27.txt | AC | 24 ms | 3964 KB |
subtask_2_3.txt | TLE | 2104 ms | 108924 KB |
subtask_2_4.txt | TLE | 2104 ms | 71420 KB |
subtask_2_5.txt | TLE | 2105 ms | 109052 KB |
subtask_2_6.txt | TLE | 2105 ms | 110460 KB |
subtask_2_7.txt | AC | 886 ms | 51452 KB |
subtask_2_8.txt | AC | 72 ms | 12412 KB |
subtask_2_9.txt | AC | 529 ms | 36860 KB |
subtask_3_1.txt | AC | 10 ms | 1276 KB |
subtask_3_10.txt | TLE | 2105 ms | 109564 KB |
subtask_3_11.txt | TLE | 2105 ms | 110460 KB |
subtask_3_12.txt | AC | 5 ms | 9724 KB |
subtask_3_13.txt | AC | 42 ms | 7036 KB |
subtask_3_14.txt | TLE | 2103 ms | 380 KB |
subtask_3_2.txt | AC | 17 ms | 4476 KB |
subtask_3_3.txt | TLE | 2105 ms | 110076 KB |
subtask_3_4.txt | TLE | 2104 ms | 82684 KB |
subtask_3_5.txt | TLE | 2104 ms | 83196 KB |
subtask_3_6.txt | TLE | 2105 ms | 110332 KB |
subtask_3_7.txt | TLE | 2104 ms | 84220 KB |
subtask_3_8.txt | TLE | 2105 ms | 109692 KB |
subtask_3_9.txt | TLE | 2104 ms | 83708 KB |