QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#603539 | #7781. Sheep Eat Wolves | orz_z | AC ✓ | 26ms | 3804kb | C++14 | 3.8kb | 2024-10-01 17:07:44 | 2024-10-01 17:07:44 |
Judging History
answer
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize("Ofast,fast-math")
//#pragma GCC target("avx,avx2")
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;
#define F(i, a, b) for(int i = a; i <= (b); ++i)
#define F2(i, a, b) for(int i = a; i < (b); ++i)
#define dF(i, a, b) for(int i = a; i >= (b); --i)
template<typename T> void debug(string s, T x) {
cerr << "[" << s << "] = [" << x << "]\n";
}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {
for (int i = 0, b = 0; i < (int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++;
else if (s[i] == ')' || s[i] == '}') b--;
else if (s[i] == ',' && b == 0) {
cerr << "[" << s.substr(0, i) << "] = [" << x << "] | ";
debug(s.substr(s.find_first_not_of(' ', i + 1)), args...);
break;
}
}
#ifdef ONLINE_JUDGE
#define Debug(...)
#else
#define Debug(...) debug(#__VA_ARGS__, __VA_ARGS__)
#endif
#define pb push_back
#define fi first
#define se second
#define Mry fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0)
#define Try cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
typedef long long ll;
// namespace Fread {const int SIZE = 1 << 17; char buf[SIZE], *S, *T; inline char getchar() {if (S == T) {T = (S = buf) + fread(buf, 1, SIZE, stdin); if (S == T) return '\n';} return *S++;}}
// namespace Fwrite {const int SIZE = 1 << 17; char buf[SIZE], *S = buf, *T = buf + SIZE; inline void flush() {fwrite(buf, 1, S - buf, stdout), S = buf;} inline void putchar(char c) {*S++ = c;if (S == T) flush();} struct NTR {~NTR() {flush();}} ztr;}
// #ifdef ONLINE_JUDGE
// #define getchar Fread::getchar
// #define putchar Fwrite::putchar
// #endif
inline int ri() {
int x = 0;
bool t = 0;
char c = getchar();
while (c < '0' || c > '9') t |= c == '-', c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return t ? -x : x;
}
inline void wi(int x) {
if (x < 0) {
putchar('-'), x = -x;
}
if (x > 9) wi(x / 10);
putchar(x % 10 + 48);
}
inline void wi(int x, char s) {
wi(x), putchar(s);
}
bool Mbe;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3f;
const int _ = 2e5 + 5;
int f[105][105][2], x, y, P, q;
bool Med;
signed main() {
// Mry;
x = ri(), y = ri(), P = ri(), q = ri();
memset(f, 0x3f, sizeof f);
f[x][y][0] = 0;
int ans = inf;
auto work = [&]() -> void {
F(t, 1, 100) {
dF(i, x, 0) dF(j, y, 0) F(p, 0, 1) if(f[i][j][p] != inf) {
// Debug(t, i, j, p, f[i][j][p]);
if(p == 0) { // 在左侧
F(yx, 0, i) F(yy, 0, min(j, P - yx)) if(yx + yy <= P){ // 运多少
int shengx = i - yx, shengy = j - yy;
// int youx = x - shengx, youy = y - shengy;
// Debug("11", yx, yy, i,j,shengx, shengy);
if(shengx + q >= shengy || !shengx) {
// Debug(shengx, shengy);
f[shengx][shengy][1] = min(f[shengx][shengy][1], f[i][j][p] + 1);
}
}
} else {
if(!i) {
ans = min(ans, f[i][j][p]);
Debug(t, i, j, p);
return;
}
int youx = x - i, youy = y - j;
F(yx, 0, youx) F(yy, 0, min(youy, P - yx)) if(yx + yy <= P){
int zoux = x - (youx - yx), zouy = y - (youy - yy);
if((youx - yx) + q >= (youy-yy) || !(youx-yx)) {
f[zoux][zouy][0] = min(f[zoux][zouy][0], f[i][j][p] + 1);
}
}
}
}
}
};
work();
F(i, 0, 3) F(j, 0, 3) F(p, 0, 1) {
Debug(i, j, p, f[i][j][p]);
}
Debug(f[2][3][1]);
cout << (ans == inf ? -1 : ans) <<'\n';
// Try;
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
input:
4 4 3 1
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 5 2 0
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
2 5 1 1
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
1 1 1 0
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
3 3 1 1
output:
7
result:
ok 1 number(s): "7"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
3 3 2 1
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
10 9 1 10
output:
19
result:
ok 1 number(s): "19"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
15 20 2 5
output:
27
result:
ok 1 number(s): "27"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
18 40 16 7
output:
5
result:
ok 1 number(s): "5"
Test #10:
score: 0
Accepted
time: 2ms
memory: 3648kb
input:
60 60 8 1
output:
27
result:
ok 1 number(s): "27"
Test #11:
score: 0
Accepted
time: 2ms
memory: 3732kb
input:
60 60 8 4
output:
27
result:
ok 1 number(s): "27"
Test #12:
score: 0
Accepted
time: 2ms
memory: 3656kb
input:
60 60 8 8
output:
25
result:
ok 1 number(s): "25"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
60 60 16 1
output:
13
result:
ok 1 number(s): "13"
Test #14:
score: 0
Accepted
time: 2ms
memory: 3772kb
input:
60 60 16 8
output:
11
result:
ok 1 number(s): "11"
Test #15:
score: 0
Accepted
time: 3ms
memory: 3792kb
input:
60 60 16 16
output:
11
result:
ok 1 number(s): "11"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
60 60 16 24
output:
9
result:
ok 1 number(s): "9"
Test #17:
score: 0
Accepted
time: 7ms
memory: 3776kb
input:
75 15 1 1
output:
175
result:
ok 1 number(s): "175"
Test #18:
score: 0
Accepted
time: 2ms
memory: 3628kb
input:
50 100 1 0
output:
-1
result:
ok 1 number(s): "-1"
Test #19:
score: 0
Accepted
time: 5ms
memory: 3656kb
input:
100 100 10 10
output:
35
result:
ok 1 number(s): "35"
Test #20:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
100 100 10 1
output:
37
result:
ok 1 number(s): "37"
Test #21:
score: 0
Accepted
time: 12ms
memory: 3652kb
input:
100 100 10 20
output:
33
result:
ok 1 number(s): "33"
Test #22:
score: 0
Accepted
time: 11ms
memory: 3652kb
input:
100 100 10 30
output:
31
result:
ok 1 number(s): "31"
Test #23:
score: 0
Accepted
time: 7ms
memory: 3800kb
input:
100 100 10 80
output:
21
result:
ok 1 number(s): "21"
Test #24:
score: 0
Accepted
time: 26ms
memory: 3712kb
input:
100 100 1 100
output:
199
result:
ok 1 number(s): "199"
Test #25:
score: 0
Accepted
time: 5ms
memory: 3656kb
input:
100 100 5 0
output:
95
result:
ok 1 number(s): "95"
Test #26:
score: 0
Accepted
time: 5ms
memory: 3716kb
input:
100 100 25 3
output:
13
result:
ok 1 number(s): "13"
Test #27:
score: 0
Accepted
time: 11ms
memory: 3656kb
input:
100 100 30 4
output:
11
result:
ok 1 number(s): "11"
Test #28:
score: 0
Accepted
time: 5ms
memory: 3720kb
input:
95 100 3 3
output:
125
result:
ok 1 number(s): "125"
Test #29:
score: 0
Accepted
time: 11ms
memory: 3792kb
input:
98 99 50 6
output:
5
result:
ok 1 number(s): "5"
Test #30:
score: 0
Accepted
time: 15ms
memory: 3648kb
input:
100 100 45 4
output:
7
result:
ok 1 number(s): "7"
Test #31:
score: 0
Accepted
time: 20ms
memory: 3656kb
input:
100 100 40 39
output:
7
result:
ok 1 number(s): "7"
Test #32:
score: 0
Accepted
time: 22ms
memory: 3712kb
input:
100 100 45 19
output:
7
result:
ok 1 number(s): "7"
Test #33:
score: 0
Accepted
time: 21ms
memory: 3720kb
input:
100 100 49 99
output:
5
result:
ok 1 number(s): "5"
Test #34:
score: 0
Accepted
time: 21ms
memory: 3696kb
input:
100 100 49 100
output:
5
result:
ok 1 number(s): "5"
Test #35:
score: 0
Accepted
time: 21ms
memory: 3720kb
input:
100 100 49 98
output:
5
result:
ok 1 number(s): "5"
Test #36:
score: 0
Accepted
time: 21ms
memory: 3644kb
input:
100 100 49 97
output:
5
result:
ok 1 number(s): "5"
Test #37:
score: 0
Accepted
time: 21ms
memory: 3776kb
input:
100 100 49 96
output:
5
result:
ok 1 number(s): "5"
Test #38:
score: 0
Accepted
time: 21ms
memory: 3680kb
input:
100 100 49 95
output:
5
result:
ok 1 number(s): "5"
Test #39:
score: 0
Accepted
time: 3ms
memory: 3648kb
input:
100 100 100 0
output:
1
result:
ok 1 number(s): "1"
Test #40:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1 100 1 0
output:
1
result:
ok 1 number(s): "1"
Test #41:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
90 100 5 5
output:
87
result:
ok 1 number(s): "87"
Test #42:
score: 0
Accepted
time: 2ms
memory: 3728kb
input:
100 1 1 0
output:
199
result:
ok 1 number(s): "199"
Test #43:
score: 0
Accepted
time: 6ms
memory: 3716kb
input:
94 61 22 35
output:
9
result:
ok 1 number(s): "9"
Test #44:
score: 0
Accepted
time: 3ms
memory: 3776kb
input:
61 92 36 6
output:
7
result:
ok 1 number(s): "7"
Test #45:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
73 89 12 4
output:
57
result:
ok 1 number(s): "57"
Test #46:
score: 0
Accepted
time: 2ms
memory: 3700kb
input:
71 80 4 3
output:
-1
result:
ok 1 number(s): "-1"
Test #47:
score: 0
Accepted
time: 3ms
memory: 3732kb
input:
44 75 2 31
output:
85
result:
ok 1 number(s): "85"
Test #48:
score: 0
Accepted
time: 2ms
memory: 3772kb
input:
48 62 5 18
output:
35
result:
ok 1 number(s): "35"
Test #49:
score: 0
Accepted
time: 5ms
memory: 3660kb
input:
73 100 22 49
output:
9
result:
ok 1 number(s): "9"
Extra Test:
score: 0
Extra Test Passed