QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#280175#7781. Sheep Eat Wolvesucup-team2010#AC ✓32ms4152kbC++174.3kb2023-12-09 14:16:322024-10-14 07:46:25

Judging History

你现在查看的是最新测评结果

  • [2024-10-14 07:46:25]
  • 管理员手动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:32ms
  • 内存:4152kb
  • [2024-09-05 08:34:25]
  • hack成功,自动添加数据
  • (/hack/803)
  • [2024-09-05 08:23:36]
  • hack成功,自动添加数据
  • (/hack/802)
  • [2023-12-09 14:16:32]
  • 评测
  • 测评结果:100
  • 用时:29ms
  • 内存:4112kb
  • [2023-12-09 14:16:32]
  • 提交

answer

#define NDEBUG
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using std::cin, std::cout;
using ll = long long;
using db = double;
void Main(void);
int main(void)
{
	std::ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#if defined(TEXT_IO) and defined(LOCAL) and not defined(ONLINE_JUDGE)
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
#endif
	Main();
	return 0;
}
/**************************************************/
namespace my
{
#if defined(LOCAL) and not defined(ONLINE_JUDGE)
#include "D:\VScodeFile\LOCAL\debug.h"
#define DBG(x) std::cerr << "! " #x " = " << (x) << std::endl
#else
#define dbg(...) ((void)0)
#define DBG(...) ((void)0)
#endif
#define VE std::vector
#define STR std::string
#define HEAP std::priority_queue
#define PLL std::pair<ll, ll>
#define fi first
#define se second
#define EDL '\n'
#define WS ' '
#define SDP(x) std::fixed << std::setprecision(x)
#define SZ(x) ((ll)x.size())
#define FOR(i, l, r) for (ll i = (l); i <= (r); ++i)
#define ROF(i, r, l) for (ll i = (r); i >= (l); --i)
	constexpr int inf = 0x3f3f3f3f;
	constexpr ll INF = 0x3f3f3f3f3f3f3f3fLL;
}
using namespace my;
namespace fastIO
{
	constexpr ll BUF_SZ = 1e5 + 5;
	bool IOrun = true;
	char NC(void)
	{
		static char buf[BUF_SZ], *p = buf + BUF_SZ, *ed = buf + BUF_SZ;
		if (p != ed)
			return *p++;
		p = buf;
		ed = buf + fread(buf, 1, BUF_SZ, stdin);
		if (p == ed)
		{
			IOrun = false;
			return -1;
		}
		return *p++;
	}
	bool BLK(char c) { return c == WS or c == EDL or c == '\r' or c == '\t'; }
	template <class T>
	bool FIN(T &x)
	{
		bool sign = false;
		char c = NC();
		x = 0;
		while (BLK(c))
			c = NC();
		if (not IOrun)
			return false;
		if (c == '-')
		{
			sign = true;
			c = NC();
		}
		while ('0' <= c and c <= '9')
		{
			x = x * 10 + c - '0';
			c = NC();
		}
		if (sign)
			x = -x;
		return true;
	}
	bool FIN(db &x)
	{
		bool sign = false;
		char c = NC();
		x = 0;
		while (BLK(c))
			c = NC();
		if (not IOrun)
			return false;
		if (c == '-')
		{
			sign = true;
			c = NC();
		}
		while ('0' <= c and c <= '9')
		{
			x = x * 10 + c - '0';
			c = NC();
		}
		if (c == '.')
		{
			db w = 1.0;
			c = NC();
			while ('0' <= c and c <= '9')
			{
				w /= 10.0;
				x += w * (c - '0');
				c = NC();
			}
		}
		if (sign)
			x = -x;
		return true;
	}
	bool FIN(char &c)
	{
		c = NC();
		while (BLK(c))
			c = NC();
		if (not IOrun)
		{
			c = -1;
			return false;
		}
		return true;
	}
	bool FIN(char *s)
	{
		char c = NC();
		while (BLK(c))
			c = NC();
		if (not IOrun)
			return false;
		while (IOrun and not BLK(c))
		{
			*s++ = c;
			c = NC();
		}
		*s = 0;
		return true;
	}
	bool LIN(char *s)
	{
		char c = NC();
		while (BLK(c))
			c = NC();
		if (not IOrun)
			return false;
		while (IOrun and c != EDL)
		{
			*s++ = c;
			c = NC();
		}
		*s = 0;
		return true;
	}
	template <class T, class... Y>
	bool FIN(T &x, Y &...o) { return FIN(x) and FIN(o...); }
	void FIN(int *a, ll l, ll r)
	{
		FOR(i, l, r)
		FIN(a[i]);
		return;
	}
	void FIN(ll *a, ll l, ll r)
	{
		FOR(i, l, r)
		FIN(a[i]);
		return;
	}
	void FIN(db *a, ll l, ll r)
	{
		FOR(i, l, r)
		FIN(a[i]);
		return;
	}
	void FIN(char *a, ll l, ll r)
	{
		FOR(i, l, r)
		FIN(a[i]);
		return;
	}
}
using fastIO::FIN, fastIO::LIN;
/**************************************************/
constexpr db EPS = 1.0e-9;
constexpr ll MOD = 998244353LL;
constexpr ll SZ = 1e2 + 5;
ll x, y, p, q;
ll f[SZ][SZ][2];

struct Node
{
	ll x, y, k;
};

void Main(void)
{
	cin >> x >> y >> p >> q;
	memset(f, inf, sizeof(f));
	std::queue<Node> qu;
	f[x][y][0] = 0;
	qu.push({x, y, 0});
	while (not qu.empty())
	{
		auto [nx, ny, nk] = qu.front();
		qu.pop();
		FOR(i, 0, nx)
		{
			if (i > p)
				break;
			FOR(j, 0, ny)
			{
				if (i + j > p)
					break;
				if ((nx - i > 0) and (nx - i + q < ny - j))
					continue;
				if (f[x - (nx - i)][y - (ny - j)][1 - nk] != INF)
					continue;
				f[x - (nx - i)][y - (ny - j)][1 - nk] = f[nx][ny][nk] + 1;
				qu.push({x - (nx - i), y - (ny - j), 1 - nk});
			}
		}
	}
	ll ans = INF;
	FOR(i, 0, y)
	ans = std::min(ans, f[x][i][1]);
	if (ans == INF)
		ans = -1;
	cout << ans << EDL;
	return;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3720kb

input:

4 4 3 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 4024kb

input:

3 5 2 0

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

2 5 1 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

1 1 1 0

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

3 3 1 1

output:

7

result:

ok 1 number(s): "7"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

3 3 2 1

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3980kb

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: 1ms
memory: 3728kb

input:

18 40 16 7

output:

5

result:

ok 1 number(s): "5"

Test #10:

score: 0
Accepted
time: 1ms
memory: 4028kb

input:

60 60 8 1

output:

27

result:

ok 1 number(s): "27"

Test #11:

score: 0
Accepted
time: 1ms
memory: 3984kb

input:

60 60 8 4

output:

27

result:

ok 1 number(s): "27"

Test #12:

score: 0
Accepted
time: 1ms
memory: 3764kb

input:

60 60 8 8

output:

25

result:

ok 1 number(s): "25"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

60 60 16 1

output:

13

result:

ok 1 number(s): "13"

Test #14:

score: 0
Accepted
time: 1ms
memory: 3964kb

input:

60 60 16 8

output:

11

result:

ok 1 number(s): "11"

Test #15:

score: 0
Accepted
time: 2ms
memory: 3740kb

input:

60 60 16 16

output:

11

result:

ok 1 number(s): "11"

Test #16:

score: 0
Accepted
time: 0ms
memory: 3804kb

input:

60 60 16 24

output:

9

result:

ok 1 number(s): "9"

Test #17:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

75 15 1 1

output:

175

result:

ok 1 number(s): "175"

Test #18:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

50 100 1 0

output:

-1

result:

ok 1 number(s): "-1"

Test #19:

score: 0
Accepted
time: 1ms
memory: 3732kb

input:

100 100 10 10

output:

35

result:

ok 1 number(s): "35"

Test #20:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

100 100 10 1

output:

37

result:

ok 1 number(s): "37"

Test #21:

score: 0
Accepted
time: 2ms
memory: 3832kb

input:

100 100 10 20

output:

33

result:

ok 1 number(s): "33"

Test #22:

score: 0
Accepted
time: 2ms
memory: 3800kb

input:

100 100 10 30

output:

31

result:

ok 1 number(s): "31"

Test #23:

score: 0
Accepted
time: 3ms
memory: 3844kb

input:

100 100 10 80

output:

21

result:

ok 1 number(s): "21"

Test #24:

score: 0
Accepted
time: 1ms
memory: 3716kb

input:

100 100 1 100

output:

199

result:

ok 1 number(s): "199"

Test #25:

score: 0
Accepted
time: 1ms
memory: 4024kb

input:

100 100 5 0

output:

95

result:

ok 1 number(s): "95"

Test #26:

score: 0
Accepted
time: 3ms
memory: 4036kb

input:

100 100 25 3

output:

13

result:

ok 1 number(s): "13"

Test #27:

score: 0
Accepted
time: 5ms
memory: 4024kb

input:

100 100 30 4

output:

11

result:

ok 1 number(s): "11"

Test #28:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

95 100 3 3

output:

125

result:

ok 1 number(s): "125"

Test #29:

score: 0
Accepted
time: 12ms
memory: 3860kb

input:

98 99 50 6

output:

5

result:

ok 1 number(s): "5"

Test #30:

score: 0
Accepted
time: 10ms
memory: 4096kb

input:

100 100 45 4

output:

7

result:

ok 1 number(s): "7"

Test #31:

score: 0
Accepted
time: 18ms
memory: 4092kb

input:

100 100 40 39

output:

7

result:

ok 1 number(s): "7"

Test #32:

score: 0
Accepted
time: 15ms
memory: 4092kb

input:

100 100 45 19

output:

7

result:

ok 1 number(s): "7"

Test #33:

score: 0
Accepted
time: 31ms
memory: 3908kb

input:

100 100 49 99

output:

5

result:

ok 1 number(s): "5"

Test #34:

score: 0
Accepted
time: 31ms
memory: 3852kb

input:

100 100 49 100

output:

5

result:

ok 1 number(s): "5"

Test #35:

score: 0
Accepted
time: 32ms
memory: 4068kb

input:

100 100 49 98

output:

5

result:

ok 1 number(s): "5"

Test #36:

score: 0
Accepted
time: 30ms
memory: 3796kb

input:

100 100 49 97

output:

5

result:

ok 1 number(s): "5"

Test #37:

score: 0
Accepted
time: 31ms
memory: 3908kb

input:

100 100 49 96

output:

5

result:

ok 1 number(s): "5"

Test #38:

score: 0
Accepted
time: 31ms
memory: 4152kb

input:

100 100 49 95

output:

5

result:

ok 1 number(s): "5"

Test #39:

score: 0
Accepted
time: 26ms
memory: 3748kb

input:

100 100 100 0

output:

1

result:

ok 1 number(s): "1"

Test #40:

score: 0
Accepted
time: 1ms
memory: 3976kb

input:

1 100 1 0

output:

1

result:

ok 1 number(s): "1"

Test #41:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

90 100 5 5

output:

87

result:

ok 1 number(s): "87"

Test #42:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

100 1 1 0

output:

199

result:

ok 1 number(s): "199"

Test #43:

score: 0
Accepted
time: 5ms
memory: 3824kb

input:

94 61 22 35

output:

9

result:

ok 1 number(s): "9"

Test #44:

score: 0
Accepted
time: 3ms
memory: 3860kb

input:

61 92 36 6

output:

7

result:

ok 1 number(s): "7"

Test #45:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

73 89 12 4

output:

57

result:

ok 1 number(s): "57"

Test #46:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

71 80 4 3

output:

-1

result:

ok 1 number(s): "-1"

Test #47:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

44 75 2 31

output:

85

result:

ok 1 number(s): "85"

Test #48:

score: 0
Accepted
time: 1ms
memory: 4032kb

input:

48 62 5 18

output:

35

result:

ok 1 number(s): "35"

Test #49:

score: 0
Accepted
time: 5ms
memory: 3760kb

input:

73 100 22 49

output:

9

result:

ok 1 number(s): "9"

Extra Test:

score: 0
Extra Test Passed