QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#673156 | #7781. Sheep Eat Wolves | yeah14# | WA | 2ms | 7972kb | C++17 | 1.9kb | 2024-10-24 20:48:43 | 2024-10-24 20:48:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
// a[32];
using PII = pair<int, int>;
const int INF = 0x3f3f3f3f3f3f;
map<string, vector<PII>>mp;
map<int, string>mpp;
int a[N];
int ans[N];
int ww[N];
int st[N],top=0;
const int mod = 998244353;
bool cmp(PII a, PII b) {
return a.first > b.first;
}
bool cmp2(int a, int b) {
return a > b;
}
int __gcd(int x, int y) {
if (y == 0)return x;
else return __gcd(y, x % y);
}
int fp(int a, int x) {
int ans = 1;
while (x) {
if (x & 1)ans *= a;
ans %= mod;
a *= a;
a %= mod;
x >>= 1;
}
return ans%mod;
}
vector<int>p[N];
void solve() {
int x, y, p, q;
cin >> x >> y >> p >> q;
int x2=0, y2 = 0;
int nx=0, ny = 0;
if (p >= x) {
cout << 1 << endl;
return;
}
int ans = 0;
int cnt = 0;
while (x) {
//cnt++;
//cout << cnt << endl;
//cout << x << " " << y << endl;
bool flag = 0;
if (x == nx && y == ny) {
cout << -1 << endl;
return;
}
else if(flag)
nx = x, ny = y;
if (x + q < y - p) {
cout << -1 << endl;
return;
}
int s = y - (x + q);
y -= max(s, 0LL);
if (x <= p) {
ans++;
break;
}
for (int i = p-max(0LL,s); i >= 0; i--) {
if (x - i + q >= y- (p - max(0LL, s)-i)) {
x -= i;
if (x + q < y) {
int pp = y - (x + q);
y-=pp;
y2 += pp;
}
else if (i == 0) {
y -= q;
y2 += q;
}
x2 += i;
ans++;
flag = 1;
break;
}
}
y2 += max(s,0LL);
int t = y2 - (x2 + q);
if (x2 == 0)t = 0;
if (t > p) {
cout << -1 << endl;
break;
}
if (x2 + q < y2 - p) {
cout << -1 << endl;
return;
}
ans++;
y2 -= max(t, 0LL);
y += max(t, 0LL);
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int t=1;
//cin >> t;
while (t--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7160kb
input:
4 4 3 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 6480kb
input:
3 5 2 0
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7972kb
input:
2 5 1 1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 7544kb
input:
1 1 1 0
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 7252kb
input:
3 3 1 1
output:
7
result:
ok 1 number(s): "7"
Test #6:
score: 0
Accepted
time: 1ms
memory: 7776kb
input:
3 3 2 1
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 0ms
memory: 6500kb
input:
10 9 1 10
output:
19
result:
ok 1 number(s): "19"
Test #8:
score: 0
Accepted
time: 1ms
memory: 7352kb
input:
15 20 2 5
output:
27
result:
ok 1 number(s): "27"
Test #9:
score: 0
Accepted
time: 1ms
memory: 7628kb
input:
18 40 16 7
output:
5
result:
ok 1 number(s): "5"
Test #10:
score: 0
Accepted
time: 1ms
memory: 6380kb
input:
60 60 8 1
output:
27
result:
ok 1 number(s): "27"
Test #11:
score: 0
Accepted
time: 1ms
memory: 6228kb
input:
60 60 8 4
output:
27
result:
ok 1 number(s): "27"
Test #12:
score: 0
Accepted
time: 0ms
memory: 7280kb
input:
60 60 8 8
output:
25
result:
ok 1 number(s): "25"
Test #13:
score: 0
Accepted
time: 1ms
memory: 7640kb
input:
60 60 16 1
output:
13
result:
ok 1 number(s): "13"
Test #14:
score: 0
Accepted
time: 1ms
memory: 7916kb
input:
60 60 16 8
output:
11
result:
ok 1 number(s): "11"
Test #15:
score: 0
Accepted
time: 1ms
memory: 7440kb
input:
60 60 16 16
output:
11
result:
ok 1 number(s): "11"
Test #16:
score: 0
Accepted
time: 1ms
memory: 6656kb
input:
60 60 16 24
output:
9
result:
ok 1 number(s): "9"
Test #17:
score: 0
Accepted
time: 1ms
memory: 7748kb
input:
75 15 1 1
output:
175
result:
ok 1 number(s): "175"
Test #18:
score: 0
Accepted
time: 0ms
memory: 6124kb
input:
50 100 1 0
output:
-1
result:
ok 1 number(s): "-1"
Test #19:
score: 0
Accepted
time: 0ms
memory: 6308kb
input:
100 100 10 10
output:
35
result:
ok 1 number(s): "35"
Test #20:
score: 0
Accepted
time: 1ms
memory: 6928kb
input:
100 100 10 1
output:
37
result:
ok 1 number(s): "37"
Test #21:
score: 0
Accepted
time: 0ms
memory: 6680kb
input:
100 100 10 20
output:
33
result:
ok 1 number(s): "33"
Test #22:
score: 0
Accepted
time: 1ms
memory: 6768kb
input:
100 100 10 30
output:
31
result:
ok 1 number(s): "31"
Test #23:
score: 0
Accepted
time: 1ms
memory: 7264kb
input:
100 100 10 80
output:
21
result:
ok 1 number(s): "21"
Test #24:
score: 0
Accepted
time: 1ms
memory: 6952kb
input:
100 100 1 100
output:
199
result:
ok 1 number(s): "199"
Test #25:
score: -100
Wrong Answer
time: 1ms
memory: 7656kb
input:
100 100 5 0
output:
97
result:
wrong answer 1st numbers differ - expected: '95', found: '97'