Contest Duration: ~ (local time) (150 minutes) Back to Home

Submission #4482224

Source Code Expand

Copy
```#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << setw(10) << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

ll gcd(ll a,ll b){
if(b == 0) return a;
return gcd(b,a%b);
}

bool can_eternal(ll A, ll B, ll C, ll D){
// 最初から在庫足りてない
if(A<B){
return false;
}

// 補充より消費が速い
if(B>D){
return false;
}

// 以降、A>=B, B<=D

// AからBをギリギリまで引いた状態
ll start = A % B;
ll step = D-B;

// 次の飲みで終わる
if(start>C){
return false;
}

if(step==0){
if(start<=C){
return true;
}else{
return false;
}
}

// 危険ゾーンがない場合とは
if(B-C<=1){
return true;
}

if(step==1){
return false;
}

ll left = C+1;
ll right = B; // 含まない

// 幅が広いので踏む
if(right - left >= step){
return false;
}

step = gcd(step, B);

// 幅が広くなくても踏むときは踏む
// leftの直前まで移動
ll diff = left - start;
ll n = diff / step;
n -= 3; // ちょっと引く・・・
if(n>0){
start += step * n;
}

// 危険ゾーンの直前まで来た
while(start < right){
start += step;
if(left <= start && start < right){
return false;
}
}

return true;
}

int main(){
cin.tie(0);
ios::sync_with_stdio(false);

// input
ll T;
cin >> T;

FOR(i, 0, T){
ll A, B, C, D;
cin >> A >> B >> C >> D;

bool can = can_eternal(A, B, C, D);
if(can){
p_yes();
}else{
p_no();
}
}

return 0;
}```

#### Submission Info

Submission Time 2019-03-06 06:23:24+0900 B - rng_10s peroon C++14 (GCC 5.4.1) 600 2301 Byte AC 2 ms 256 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
 AC × 2
 AC × 5
Set Name Test Cases
Sample example_0, example_1
All example_0, example_1, multi_0, multi_1, multi_2
Case Name Status Exec Time Memory
example_0 1 ms 256 KB
example_1 1 ms 256 KB
multi_0 2 ms 256 KB
multi_1 2 ms 256 KB
multi_2 2 ms 256 KB