Submission #1317697
Source Code Expand
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <numeric>
#include <cctype>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcount
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define df(x) int x = in()
#define dame { puts("-1"); return 0;}
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,vector<T>,greater<T> >
#define bn(x) ((1<<x)-1)
#define newline puts("")
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const vector<T>&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,const vector<T>&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
const int MX = 100005, INF = 1001001001;
const ll LINF = 1e18;
const double eps = 1e-10;
// Mod int
const int mod = 1000000007;
struct mint {
ll x;
mint():x(0){}
mint(ll x):x((x%mod+mod)%mod){}
// mint(ll x):x(x){}
mint& fix() { x = (x%mod+mod)%mod; return *this;}
mint& operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}
mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}
mint& operator*=(const mint& a){ (x*=a.x)%=mod; return *this;}
mint& operator/=(const mint& a){ (x*=a.ex(mod-2).x)%=mod; return *this;}
mint operator+(const mint& a)const{ return mint(*this) += a;}
mint operator-(const mint& a)const{ return mint(*this) -= a;}
mint operator*(const mint& a)const{ return mint(*this) *= a;}
mint operator/(const mint& a)const{ return mint(*this) /= a;}
mint ex(ll t) const {
if(!t) return 1;
mint res = ex(t/2);
res *= res;
return (t&1)?res*x:res;
}
bool operator<(const mint& a)const{ return x < a.x;}
bool operator==(const mint& a)const{ return x == a.x;}
};
mint ex(mint x, ll t) { return x.ex(t);}
istream& operator>>(istream&i,mint&a){i>>a.x;return i;}
ostream& operator<<(ostream&o,const mint&a){o<<a.x;return o;}
typedef vector<mint> vm;
struct comb {
vm f, g;
comb(){}
comb(int mx):f(mx+1),g(mx+1) {
f[0] = 1;
rrep(i,mx) f[i] = f[i-1]*i;
g[mx] = f[mx].ex(mod-2);
for(int i=mx;i>0;i--) g[i-1] = g[i]*i;
}
mint c(int a, int b) {
if (a < b) return 0;
return f[a]*g[b]*g[a-b];
}
};
//
int n;
vl a;
int ft(ll x) {
for (int i = n-1; i >= 0; --i) {
if (a[i] <= x) return i;
}
return 0;
}
ll ax, ay;
bool ok;
mint f(ll x, ll y, int t) {
if (y > ax) {
ok = false;
return 0;
}
if (t == 1) {
ok = (ay-x) >= y;
return (ay-x)/y;
}
if (x*a[t-2]+y*a[t-1] > ax || x*a[t-1]+y*a[t] > ay) {
ok = false;
return 0;
}
mint res = 0;
ok = true;
while (ok) {
x += y;
res += f(y,x,t-1);
}
ok = true;
return res;
}
int main() {
a.pb(1);
a.pb(1);
while (a.back() < LINF) {
a.pb(a[sz(a)-2]+a.back());
}
n = sz(a);
int q;
scanf("%d",&q);
rep(qi,q) {
ll x,y;
scanf("%lld%lld",&x,&y);
if (x > y) swap(x,y);
if (y == 1) {
printf("%d %d\n",1,1);
continue;
}
int t = min(ft(x),ft(y)-1);
if (t == 1) {
printf("%d %lld\n",1,x*y%mod);
continue;
}
ax = x; ay = y;
mint ans = f(1,1,t);
ay = ax;
ans += f(1,1,t);
printf("%d %lld\n",t,ans.x);
}
return 0;
}
Submission Info
Submission Time
2017-05-30 11:12:16+0900
Task
F - Kenus the Ancient Greek
User
snuke
Language
C++14 (GCC 5.4.1)
Score
1700
Code Size
4850 Byte
Status
AC
Exec Time
4629 ms
Memory
3968 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:157:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
^
./Main.cpp:160:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&x,&y);
^
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
1319 ms
3328 KB
02.txt
AC
1315 ms
3200 KB
03.txt
AC
1310 ms
3200 KB
04.txt
AC
1314 ms
3200 KB
05.txt
AC
1312 ms
3200 KB
06.txt
AC
1313 ms
3200 KB
07.txt
AC
1309 ms
3200 KB
08.txt
AC
1316 ms
3200 KB
09.txt
AC
1312 ms
3200 KB
10.txt
AC
1320 ms
3200 KB
11.txt
AC
2622 ms
1920 KB
12.txt
AC
2600 ms
1920 KB
13.txt
AC
352 ms
1792 KB
14.txt
AC
394 ms
1792 KB
15.txt
AC
360 ms
3968 KB
16.txt
AC
361 ms
3968 KB
17.txt
AC
155 ms
3712 KB
18.txt
AC
155 ms
3712 KB
19.txt
AC
4629 ms
3456 KB
20.txt
AC
4471 ms
3456 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