Submission #1052614
Source Code Expand
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.3.2"
lflags "-stack_size" "100000000"
+/
import std.algorithm, std.conv, std.range, std.stdio;
// import dcomp.scanner;
// import dcomp.algorithm;
// import dcomp.container.deque;
int main(string[] argv) {
auto sc = new Scanner();
int n;
string s, t;
sc.read(n, s, t);
//first check
if (s == t) {
writeln(0);
return 0;
}
if (s[0] != t[0]) {
writeln(-1);
return 0;
}
int[][26] pos;
foreach (i; 1..n) {
int id = s[i] - 'a';
pos[id] ~= i;
}
int[2][] node;
int ba = n;
foreach_reverse (i; 1..n) {
if (t[i-1] == t[i]) continue;
int id = t[i] - 'a';
int r = min(ba-1, i);
//check t[i], search id, [1, r]
int lt = binSearch!(i => pos[id][i] > r)(-1, pos[id].length.to!int)-1;
if (lt == -1) {
writeln(-1);
return 0;
}
int nw = pos[id][lt];
node ~= [i, nw];
ba = nw;
}
reverse(node);
int ma = 0;
Deque!(int[2]) q; // value, pos
q.insertBack([-(10^^9), -1]);
foreach (int co, nd; node) {
int i = nd[0];
int x = nd[1];
while (q.length && q.back[0] >= i-co) {
q.removeBack;
}
q.insertBack([i-co, co]);
int lt = binSearch!(i => q[i][0] >= x+1-co)(-1, q.length.to!int)-1;
ma = max(ma, co-q[lt][1]);
}
writeln(ma+1);
return 0;
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/container/deque.d */
// module dcomp.container.deque;
struct Deque(T) {
import core.exception : RangeError;
import core.memory : GC;
import std.range : ElementType, isInputRange;
import std.traits : isImplicitlyConvertible;
struct Payload {
T *d;
size_t st, length, cap;
@property bool empty() const { return length == 0; }
alias opDollar = length;
ref inout(T) opIndex(size_t i) inout {
version(assert) if (length <= i) throw new RangeError();
return d[(st+i >= cap) ? (st+i-cap) : st+i];
}
private void expand() {
import std.algorithm : max;
assert(length == cap);
auto nc = max(4L, 2*cap);
T* nd = cast(T*)GC.malloc(nc * T.sizeof);
foreach (i; 0..length) {
nd[i] = this[i];
}
d = nd; st = 0; cap = nc;
}
void insertFront(T v) {
if (length == cap) expand();
if (st == 0) st += cap;
st--; length++;
this[0] = v;
}
void insertBack(T v) {
if (length == cap) expand();
length++;
this[length-1] = v;
}
void removeFront() {
assert(!empty, "Deque.removeFront: Deque is empty");
st++; length--;
if (st == cap) st = 0;
}
void removeBack() {
assert(!empty, "Deque.removeBack: Deque is empty");
length--;
}
}
struct RangeT(A) {
alias T = typeof(*(A.p));
alias E = typeof(A.p.d[0]);
T *p;
size_t a, b;
@property bool empty() const { return b <= a; }
@property size_t length() const { return b-a; }
@property RangeT save() { return RangeT(p, a, b); }
@property RangeT!(const A) save() const {
return typeof(return)(p, a, b);
}
alias opDollar = length;
@property ref inout(E) front() inout { return (*p)[a]; }
@property ref inout(E) back() inout { return (*p)[b-1]; }
void popFront() {
version(assert) if (empty) throw new RangeError();
a++;
}
void popBack() {
version(assert) if (empty) throw new RangeError();
b--;
}
ref inout(E) opIndex(size_t i) inout { return (*p)[i]; }
RangeT opSlice() { return this.save; }
RangeT opSlice(size_t i, size_t j) {
version(assert) if (i > j || a + j > b) throw new RangeError();
return typeof(return)(p, a+i, a+j);
}
RangeT!(const A) opSlice() const { return this.save; }
RangeT!(const A) opSlice(size_t i, size_t j) const {
version(assert) if (i > j || a + j > b) throw new RangeError();
return typeof(return)(p, a+i, a+j);
}
}
alias Range = RangeT!Deque;
alias ConstRange = RangeT!(const Deque);
alias ImmutableRange = RangeT!(immutable Deque);
Payload *p;
private void I() { if (!p) p = new Payload(); }
private void C() const { assert(p, "this deque is not init"); }
//some value
this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) {I;
p = new Payload();
foreach (v; values) {
insertBack(v);
}
}
//range
this(Range)(Range r)
if (isInputRange!Range &&
isImplicitlyConvertible!(ElementType!Range, T) &&
!is(Range == T[])) {I;
p = new Payload();
foreach (v; r) {
insertBack(v);
}
}
@property bool empty() const { return (!p || p.empty); }
@property size_t length() const { return (p ? p.length : 0); }
alias opDollar = length;
ref inout(T) opIndex(size_t i) inout {C; return (*p)[i]; }
ref inout(T) front() inout {C; return (*p)[0]; }
ref inout(T) back() inout {C; return (*p)[$-1]; }
void insertFront(T v) {I; p.insertFront(v); }
void insertBack(T v) {I; p.insertBack(v); }
void removeFront() {C; p.removeFront(); }
void removeBack() {C; p.removeBack(); }
Range opSlice() {I; return Range(p, 0, length); }
}
unittest {
import std.algorithm : equal;
import std.range.primitives : isRandomAccessRange;
import std.container.util : make;
auto q = make!(Deque!int);
assert(isRandomAccessRange!(typeof(q[])));
//insert,remove
assert(equal(q[], new int[](0)));
q.insertBack(1);
assert(equal(q[], [1]));
q.insertBack(2);
assert(equal(q[], [1, 2]));
q.insertFront(3);
assert(equal(q[], [3, 1, 2]) && q.front == 3);
q.removeFront;
assert(equal(q[], [1, 2]) && q.length == 2);
q.insertBack(4);
assert(equal(q[], [1, 2, 4]) && q.front == 1 && q.back == 4 && q[$-1] == 4);
q.insertFront(5);
assert(equal(q[], [5, 1, 2, 4]));
//range
assert(equal(q[][1..3], [1, 2]));
assert(equal(q[][][][], q[]));
//const range
const auto rng = q[];
assert(rng.front == 5 && rng.back == 4);
//reference type
auto q2 = q;
q2.insertBack(6);
q2.insertFront(7);
assert(equal(q[], q2[]) && q.length == q2.length);
//construct with make
auto a = make!(Deque!int)(1, 2, 3);
auto b = make!(Deque!int)([1, 2, 3]);
assert(equal(a[], b[]));
}
unittest {
Deque!int a;
Deque!int b;
a.insertFront(2);
assert(b.length == 0);
}
unittest {
import std.algorithm : equal;
import std.range : iota;
Deque!int a;
foreach (i; 0..100) {
a.insertBack(i);
}
assert(equal(a[], iota(100)));
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/scanner.d */
// module dcomp.scanner;
class Scanner {
import std.stdio : File, stdin;
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 = stdin) {
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;
}
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);
}
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);
}
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 - Shik and Copying String |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
1500 |
Code Size |
11832 Byte |
Status |
AC |
Exec Time |
337 ms |
Memory |
22996 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1500 / 1500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0.txt, example1.txt, example2.txt, example3.txt |
All |
000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, example0.txt, example1.txt, example2.txt, example3.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
AC |
2 ms |
256 KB |
001.txt |
AC |
2 ms |
256 KB |
002.txt |
AC |
2 ms |
256 KB |
003.txt |
AC |
2 ms |
256 KB |
004.txt |
AC |
2 ms |
256 KB |
005.txt |
AC |
2 ms |
256 KB |
006.txt |
AC |
2 ms |
256 KB |
007.txt |
AC |
2 ms |
256 KB |
008.txt |
AC |
2 ms |
256 KB |
009.txt |
AC |
2 ms |
256 KB |
010.txt |
AC |
3 ms |
256 KB |
011.txt |
AC |
3 ms |
256 KB |
012.txt |
AC |
3 ms |
256 KB |
013.txt |
AC |
3 ms |
256 KB |
014.txt |
AC |
3 ms |
256 KB |
015.txt |
AC |
3 ms |
256 KB |
016.txt |
AC |
3 ms |
256 KB |
017.txt |
AC |
3 ms |
256 KB |
018.txt |
AC |
3 ms |
256 KB |
019.txt |
AC |
3 ms |
256 KB |
020.txt |
AC |
3 ms |
256 KB |
021.txt |
AC |
3 ms |
256 KB |
022.txt |
AC |
3 ms |
256 KB |
023.txt |
AC |
3 ms |
256 KB |
024.txt |
AC |
3 ms |
256 KB |
025.txt |
AC |
24 ms |
4136 KB |
026.txt |
AC |
267 ms |
19668 KB |
027.txt |
AC |
197 ms |
15828 KB |
028.txt |
AC |
288 ms |
22868 KB |
029.txt |
AC |
291 ms |
22996 KB |
030.txt |
AC |
103 ms |
12756 KB |
031.txt |
AC |
107 ms |
13396 KB |
032.txt |
AC |
115 ms |
12756 KB |
033.txt |
AC |
119 ms |
13268 KB |
034.txt |
AC |
127 ms |
14548 KB |
035.txt |
AC |
125 ms |
13268 KB |
036.txt |
AC |
127 ms |
12500 KB |
037.txt |
AC |
127 ms |
12500 KB |
038.txt |
AC |
126 ms |
11988 KB |
039.txt |
AC |
126 ms |
11988 KB |
040.txt |
AC |
243 ms |
17492 KB |
041.txt |
AC |
281 ms |
18260 KB |
042.txt |
AC |
317 ms |
19412 KB |
043.txt |
AC |
317 ms |
19540 KB |
044.txt |
AC |
308 ms |
19668 KB |
045.txt |
AC |
301 ms |
19668 KB |
046.txt |
AC |
337 ms |
19668 KB |
047.txt |
AC |
283 ms |
19668 KB |
048.txt |
AC |
272 ms |
19796 KB |
049.txt |
AC |
270 ms |
19668 KB |
050.txt |
AC |
24 ms |
4136 KB |
051.txt |
AC |
24 ms |
4136 KB |
052.txt |
AC |
24 ms |
4136 KB |
053.txt |
AC |
217 ms |
15828 KB |
054.txt |
AC |
212 ms |
15828 KB |
055.txt |
AC |
206 ms |
15828 KB |
056.txt |
AC |
204 ms |
15956 KB |
057.txt |
AC |
199 ms |
15956 KB |
058.txt |
AC |
199 ms |
15828 KB |
example0.txt |
AC |
2 ms |
256 KB |
example1.txt |
AC |
2 ms |
256 KB |
example2.txt |
AC |
2 ms |
256 KB |
example3.txt |
AC |
2 ms |
256 KB |