Submission #1060168
Source Code Expand
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.4.0"
+/
import std.algorithm, std.conv, std.range, std.stdio;
import std.typecons;
// import dcomp.scanner, dcomp.graph.dijkstra;
alias E = Tuple!(int, "to", int, "dist");
int main() {
auto sc = new Scanner(stdin);
int n;
sc.read(n);
auto g = new E[][n+1];
foreach (i; 0..20) {
int len = 2^^i;
foreach (j; 0..n-len+1) {
g[j] ~= E(j+len, 1);
g[j+len] ~= E(j, 1);
}
}
auto dijk = dijkstra!int(g, 0);
int[] p;
int nw = n;
while (nw != 0) {
p ~= nw;
nw = dijk.from[nw];
}
p ~= 0;
reverse(p);
int sm = 0;
foreach (i, unused; p[0..$-1]) {
int a = p[i], b = p[i+1];
writefln("? %d %d", min(a, b), max(a, b));
stdout.flush;
int x;
sc.read(x);
if (a < b) sm += x;
else sm -= x;
}
writefln("! %d", sm);
stdout.flush;
return 0;
}
/* 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;
//[0,0,0,...,1,1,1]で、初めて1となる場所を探す。pred(l) == 0, pred(r) == 1と仮定
T binSearch(alias pred, T)(T l, T r) {
while (r-l > 1) {
T md = (l+r)/2;
if (!pred(md)) l = md;
else r = md;
}
return r;
}
import std.range.primitives;
Rotator!Range rotator(Range)(Range r)
if (isForwardRange!Range && hasLength!Range) {
return typeof(return)(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 && !is(CommonType!(ElementType!Range, E) == void)) {
import std.functional;
while (!range.empty) {
if (binaryFun!pred(range.front, seed)) {
seed = range.front;
}
range.popFront;
}
return seed;
}
//should be use reduce?
ElementType!Range minimum(alias pred = "a < b", Range)(Range range)
if (isInputRange!Range && !isInfinite!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 && !is(CommonType!(ElementType!Range, E) == void)) {
import std.functional;
while (!range.empty) {
if (binaryFun!pred(seed, range.front)) {
seed = range.front;
}
range.popFront;
}
return seed;
}
ElementType!Range maximum(alias pred = "a < b", Range)(Range range)
if (isInputRange!Range && !isInfinite!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/graph/dijkstra.d */
// module dcomp.graph.djikstra;
// import dcomp.algorithm;
struct Dijkstra(T) {
T[] dist;
int[] from;
this(int n, T inf) {
dist = new T[n]; dist[] = inf;
from = new int[n];
}
}
Dijkstra!D dijkstra(D, T)(T g, int s, D inf = D.max) {
import std.conv : to;
import std.typecons : Tuple;
import std.container : make, Array, heapify;
int V = g.length.to!int;
auto dijk = Dijkstra!D(V, inf);
with (dijk) {
alias P = Tuple!(int, "to", D, "dist");
auto q = heapify!"a.dist>b.dist"(make!(Array!P)([P(s, D(0))]));
dist[s] = D(0);
from[s] = -1;
while (!q.empty) {
P p = q.front; q.popFront();
if (dist[p.to] < p.dist) continue;
foreach (e; g[p.to]) {
if (p.dist+e.dist < dist[e.to]) {
dist[e.to] = p.dist+e.dist;
from[e.to] = p.to;
q.insert(P(e.to, dist[e.to]));
}
}
}
}
return dijk;
}
Dijkstra!D dijkstraDense(D, T)(T g, int s, D inf = D.max) {
import std.conv : to;
import std.typecons : Tuple;
import std.container : make, Array, heapify;
import std.range : enumerate;
import std.algorithm : filter;
int V = g.length.to!int;
auto dijk = Dijkstra!D(V, inf);
with (dijk) {
alias P = Tuple!(int, "to", D, "dist");
bool[] used = new bool[](V);
dist[s] = D(0);
from[s] = -1;
while (true) {
//todo can optimize
auto rng = dist.enumerate.filter!(a => !used[a.index]);
if (rng.empty) break;
auto nx = rng.minimum!"a.value < b.value";
used[nx.index] = true;
P p = P(nx.index, nx.value);
if (dist[p.to] < p.dist) continue;
foreach (e; g[p.to]) {
if (p.dist+e.dist < dist[e.to]) {
dist[e.to] = p.dist+e.dist;
from[e.to] = p.to!int;
}
}
}
}
return dijk;
}
Submission Info
Submission Time |
|
Task |
A - Array Sum |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
100 |
Code Size |
8508 Byte |
Status |
AC |
Exec Time |
436 ms |
Memory |
54224 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
7 ms |
596 KB |
01-02.txt |
AC |
7 ms |
596 KB |
01-03.txt |
AC |
7 ms |
596 KB |
01-04.txt |
AC |
7 ms |
596 KB |
01-05.txt |
AC |
204 ms |
21580 KB |
01-06.txt |
AC |
210 ms |
21580 KB |
01-07.txt |
AC |
212 ms |
21696 KB |
01-08.txt |
AC |
214 ms |
21696 KB |
01-09.txt |
AC |
213 ms |
21696 KB |
01-10.txt |
AC |
239 ms |
24904 KB |
01-11.txt |
AC |
240 ms |
25016 KB |
01-12.txt |
AC |
354 ms |
43064 KB |
01-13.txt |
AC |
359 ms |
43064 KB |
01-14.txt |
AC |
432 ms |
53968 KB |
01-15.txt |
AC |
388 ms |
52152 KB |
01-16.txt |
AC |
424 ms |
53560 KB |
01-17.txt |
AC |
431 ms |
54224 KB |
01-18.txt |
AC |
436 ms |
54224 KB |
01-19.txt |
AC |
93 ms |
10700 KB |
01-20.txt |
AC |
173 ms |
21196 KB |
01-21.txt |
AC |
364 ms |
45368 KB |
01-22.txt |
AC |
201 ms |
21580 KB |
01-23.txt |
AC |
215 ms |
21704 KB |
01-24.txt |
AC |
385 ms |
51508 KB |