Submission #1069854
Source Code Expand
/+ dub.sdl:
name "A"
dependency "dcomp" version=">=0.4.0"
+/
import std.stdio, std.range, std.algorithm, std.conv;
// import dcomp.scanner, dcomp.algorithm, dcomp.array;
int[2][] shrink(int[2][] a) {
auto xv = a.map!"a[0]".array;
auto yv = a.map!"a[1]".array;
xv = sort(xv).uniq.array;
yv = sort(yv).uniq.array;
foreach (ref v; a) {
v[0] = binSearch!(i => xv[i] >= v[0])(-1, xv.length.to!int);
v[1] = binSearch!(i => yv[i] >= v[1])(-1, yv.length.to!int);
}
return a;
}
int[2][] solve(int[] a) {
int n = a.length.to!int;
if (n == 4) {
return [[0, 0], [1, 0], [1, 1], [0, 1]];
}
int rt = iota(n).find!(i => a[i] == -1 && a[(i+1)%n] == 1).front;
bringToFront(a[0..rt], a[rt..$]);
auto ch = solve(a[2..$]).map!(x => [x[0]*2, x[1]*2].fixed).array;
int[2][] fr = new int[2][](2);
if (ch[0][0] == ch[$-1][0]) {
int ny = (ch[0][1]+ch[$-1][1])/2;
fr[0] = [ch[0][0], ny];
fr[1] = [ch[0][0]+1, ny];
ch[0][0]++;
} else {
int nx = (ch[0][0]+ch[$-1][0])/2;
fr[0] = [nx, ch[0][1]];
fr[1] = [nx, ch[0][1]+1];
ch[0][1]++;
}
fr ~= ch;
bringToFront(fr[0..$-rt], fr[$-rt..$]);
return fr.shrink;
}
int main() {
auto sc = new Scanner(stdin);
int n;
sc.read(n);
int[] a = new int[n];
a.each!((ref x) => sc.read(x));
sc.read(a);
a = a.map!(x => (x == 90 ? 1 : -1)).array;
// writeln(a);
if (a.sum != 4) {
writeln(-1);
return 0;
}
writeln(solve(a).map!(x => x[].map!(to!string).join(" ")).join("\n"));
return 0;
}
/* IMPORT /Users/yosupo/Program/dcomp/source/dcomp/array.d */
// module dcomp.array;
// import dcomp.memory;
struct FastAppender(A, bool useMyPool = false) {
@disable this(this); //this is not reference type(don't copy!)
import std.algorithm : max;
import std.range.primitives : ElementEncodingType;
import core.stdc.string : memcpy;
private alias T = ElementEncodingType!A;
private T* _data;
private size_t len, cap;
this(T[]* arr) {
_data = (*arr).ptr;
len = (*arr).length;
cap = (*arr).length;
}
void reserve(size_t nlen) {
import core.memory : GC;
if (nlen <= cap) return;
void* nx;
static if (useMyPool) {
nx = nowPool.malloc(nlen * T.sizeof);
} else {
nx = GC.malloc(nlen * T.sizeof);
}
cap = nlen;
if (len) memcpy(nx, _data, len * T.sizeof);
_data = cast(T*)(nx);
}
void opOpAssign(string op : "~")(T item) {
if (len == cap) {
reserve(max(4, cap*2));
}
_data[len++] = item;
}
void clear() {
len = 0;
}
T[] data() {
return (_data) ? _data[0..len] : null;
}
}
T[N] fixed(T, int N)(T[N] a) {return a;}
/* 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/memory.d */
// module dcomp.memory;
MemoryPool _nowPool;
@property void nowPool(MemoryPool newPool) {
_nowPool = newPool;
}
@property MemoryPool nowPool() {
return _nowPool;
}
class MemoryPool {
import core.memory : GC;
import std.algorithm : max;
static immutable Allign = 16;
static immutable BIG = 2^^20;
GC.BlkInfo[] blks;
size_t e, idx, pos;
this(size_t e) {
this.e = e;
idx = pos = 0;
}
void assign(size_t sz) {
blks ~= GC.qalloc(sz);
}
void* malloc(size_t sz) {
if (BIG < sz) {
return GC.malloc(sz);
}
sz = (sz + Allign-1) / Allign * Allign;
while (idx < blks.length && blks[idx].size < pos + sz) {
idx++; pos = 0;
}
if (idx == blks.length) {
assign(max(e, sz)); pos = 0;
}
pos += sz;
assert(pos <= blks[idx].size);
return cast(void *)(cast(byte *)(blks[idx].base) + pos - sz);
}
void allFree() {
idx = pos = 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;
}
Submission Info
Submission Time |
|
Task |
I - 90 and 270 |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
0 |
Code Size |
9425 Byte |
Status |
WA |
Exec Time |
54 ms |
Memory |
4732 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 1500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0.txt, example1.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, example0.txt, example1.txt |
Case Name |
Status |
Exec Time |
Memory |
000.txt |
AC |
3 ms |
380 KB |
001.txt |
AC |
3 ms |
256 KB |
002.txt |
AC |
3 ms |
256 KB |
003.txt |
WA |
21 ms |
2940 KB |
004.txt |
WA |
6 ms |
1020 KB |
005.txt |
WA |
9 ms |
1532 KB |
006.txt |
WA |
16 ms |
2684 KB |
007.txt |
WA |
7 ms |
1148 KB |
008.txt |
WA |
4 ms |
636 KB |
009.txt |
WA |
8 ms |
1404 KB |
010.txt |
WA |
27 ms |
3964 KB |
011.txt |
WA |
3 ms |
380 KB |
012.txt |
WA |
12 ms |
2172 KB |
013.txt |
WA |
12 ms |
2172 KB |
014.txt |
WA |
3 ms |
508 KB |
015.txt |
WA |
5 ms |
892 KB |
016.txt |
WA |
16 ms |
2940 KB |
017.txt |
WA |
2 ms |
256 KB |
018.txt |
WA |
14 ms |
2172 KB |
019.txt |
WA |
7 ms |
1276 KB |
020.txt |
WA |
38 ms |
4604 KB |
021.txt |
WA |
2 ms |
256 KB |
022.txt |
WA |
40 ms |
4604 KB |
023.txt |
WA |
45 ms |
4732 KB |
024.txt |
WA |
45 ms |
4732 KB |
025.txt |
WA |
43 ms |
4732 KB |
026.txt |
WA |
42 ms |
4732 KB |
027.txt |
WA |
42 ms |
4732 KB |
028.txt |
WA |
40 ms |
4732 KB |
029.txt |
WA |
54 ms |
4732 KB |
030.txt |
WA |
40 ms |
4732 KB |
031.txt |
WA |
42 ms |
4732 KB |
032.txt |
WA |
41 ms |
4732 KB |
033.txt |
WA |
40 ms |
4732 KB |
034.txt |
WA |
41 ms |
4732 KB |
035.txt |
WA |
41 ms |
4732 KB |
036.txt |
WA |
41 ms |
4732 KB |
037.txt |
WA |
41 ms |
4732 KB |
038.txt |
WA |
41 ms |
4732 KB |
039.txt |
WA |
41 ms |
4732 KB |
040.txt |
WA |
42 ms |
4732 KB |
041.txt |
WA |
43 ms |
4732 KB |
042.txt |
WA |
49 ms |
4732 KB |
043.txt |
AC |
2 ms |
256 KB |
example0.txt |
WA |
2 ms |
256 KB |
example1.txt |
AC |
2 ms |
256 KB |