Submission #1356047
Source Code Expand
/+ dub.sdl:
name "F"
dependency "dcomp" version=">=0.6.0"
+/
import std.stdio, std.algorithm, std.range, std.conv;
// import dcomp.foundation, dcomp.scanner;
// import dcomp.array;
immutable long MD = 10^^9 + 7;
int main() {
auto sc = new Scanner(stdin);
int q;
sc.read(q);
long[2][] base = [[1L, 1L].fixed];
while (base.back[1] < 10L^^18) {
auto u = base.back;
base ~= [u[1], u[0]+u[1]];
}
foreach (i; 0..q) {
long x, y;
sc.read(x, y);
if (x > y) swap(x, y);
if (x == 1 && y == 1) {
//corner case
writeln("1 1");
continue;
}
int ans = (){
foreach (int i, u; base) {
if (x < u[0] || y < u[1]) {
return i-1;
}
}
assert(false);
}();
long cnt(long x, long y) {
long last(long a, long b) {
if (x < b) return 0;
if (y < a+b) return 0;
return ((y-a)/b) % MD;
}
long sm = last(base[ans-1][0], base[ans-1][1]);
long[2] freq = [0L, 1L];
foreach_reverse (ph; 0..ans-1) {
//use to ph
long bb = base[ph][1];
long na = base[ans-1][0] + freq[0]*bb;
long nb = base[ans-1][1] + freq[1]*bb;
sm += last(na, nb); sm %= MD;
freq = [freq[1], freq[0]+freq[1]];
}
return sm;
}
long sm = cnt(x, y);
if (base[ans-1][1] <= x) sm += cnt(x, x);
if (ans == 1) sm += min(x, y);
sm %= MD;
writeln(ans, " ", sm);
}
return 0;
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */
// module dcomp.foundation;
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);
}
}
}
}
version (X86) static if (__VERSION__ < 2071) {
import core.bitop : bsf, bsr, popcnt;
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) {
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) {
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);
}
}
}
/* IMPORT /home/yosupo/Program/dcomp/source/dcomp/array.d */
// module dcomp.array;
T[N] fixed(T, size_t N)(T[N] a) {return a;}
struct FastAppender(A) {
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;
@property size_t length() {return len;}
void reserve(size_t nlen) {
import core.memory : GC;
if (nlen <= cap) return;
void* 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;
}
}
Submission Info
Submission Time |
|
Task |
F - Kenus the Ancient Greek |
User |
yosupo |
Language |
D (LDC 0.17.0) |
Score |
1700 |
Code Size |
5877 Byte |
Status |
AC |
Exec Time |
485 ms |
Memory |
4092 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1700 / 1700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, s1.txt, s2.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
276 ms |
3196 KB |
02.txt |
AC |
280 ms |
3196 KB |
03.txt |
AC |
276 ms |
3196 KB |
04.txt |
AC |
275 ms |
3196 KB |
05.txt |
AC |
275 ms |
3324 KB |
06.txt |
AC |
282 ms |
3196 KB |
07.txt |
AC |
275 ms |
3196 KB |
08.txt |
AC |
275 ms |
3196 KB |
09.txt |
AC |
277 ms |
3196 KB |
10.txt |
AC |
280 ms |
3196 KB |
11.txt |
AC |
479 ms |
1916 KB |
12.txt |
AC |
481 ms |
1916 KB |
13.txt |
AC |
169 ms |
1888 KB |
14.txt |
AC |
170 ms |
1888 KB |
15.txt |
AC |
211 ms |
4092 KB |
16.txt |
AC |
211 ms |
4092 KB |
17.txt |
AC |
127 ms |
3708 KB |
18.txt |
AC |
126 ms |
3708 KB |
19.txt |
AC |
485 ms |
3580 KB |
20.txt |
AC |
479 ms |
3580 KB |
21.txt |
AC |
1 ms |
256 KB |
22.txt |
AC |
1 ms |
256 KB |
23.txt |
AC |
1 ms |
256 KB |
24.txt |
AC |
1 ms |
256 KB |
s1.txt |
AC |
1 ms |
256 KB |
s2.txt |
AC |
1 ms |
256 KB |