QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#60181#2160. CardiologyMIT01#AC ✓73ms3784kbC++171.7kb2022-11-03 10:46:262022-11-03 10:46:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-03 10:46:29]
  • 评测
  • 测评结果:AC
  • 用时:73ms
  • 内存:3784kb
  • [2022-11-03 10:46:26]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb emplace_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

template<typename T> inline bool chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

int n, m;

vector<pair<int, int> > centers;

struct answer
{
	int p, x, y, s;

	answer(): p(-1), x(0), y(0), s(0) { }
	answer(int _p, int _x, int _y, int _s): p(_p), x(_x), y(_y), s(_s) { }

	inline int dis() const
	{
		if (!~p) return oo;
		int ret = oo;
		for (auto u : centers)
			chkmin(ret, abs(x - u.x) + abs(y - u.y));
		return ret;
	}

	friend inline bool operator<(const answer &x, const answer &y)
	{
		int xd = x.dis(), yd = y.dis();
		if (xd != yd) return xd < yd;
		return x.p < y.p;
	}
};

answer work(int x)
{
	LL l = 0, r = (LL)n * m - 1; 
	for (int i = 0; ; ++i)
	{
		if (r - l == 1 && l / m != r / m) return answer();
		if (r - l == 0) return answer(x, l / m, l % m, i);
		l = l / m + (LL)x * n;
		r = r / m + (LL)x * n;
	}
}

int main()
{
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	scanf("%d%d", &n, &m);
	REP(i, (n - 1) >> 1, (n >> 1) + 1) REP(j, (m - 1) >> 1, (m >> 1) + 1)
		centers.pb(mp(i, j));
	answer ans;
	REP(i, 0, m)
	{
		answer tmp = work(i);
		chkmin(ans, tmp);
	}
	printf("%d %d %d %d\n", ans.p + 1, ans.x + 1, ans.y + 1, ans.s);
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 50ms
memory: 3744kb

input:

6666 966364

output:

473832 3269 483163 2

result:

ok single line: '473832 3269 483163 2'

Test #2:

score: 0
Accepted
time: 45ms
memory: 3620kb

input:

36 906986

output:

12598 1 453493 2

result:

ok single line: '12598 1 453493 2'

Test #3:

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

input:

704877 297616

output:

148803 352426 140980 3

result:

ok single line: '148803 352426 140980 3'

Test #4:

score: 0
Accepted
time: 45ms
memory: 3528kb

input:

1000000 1000000

output:

500000 500000 500000 2

result:

ok single line: '500000 500000 500000 2'

Test #5:

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

input:

2 2

output:

1 1 1 2

result:

ok single line: '1 1 1 2'

Test #6:

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

input:

1000000 2

output:

1 1 1 21

result:

ok single line: '1 1 1 21'

Test #7:

score: 0
Accepted
time: 56ms
memory: 3544kb

input:

2 1000000

output:

250001 1 500001 2

result:

ok single line: '250001 1 500001 2'

Test #8:

score: 0
Accepted
time: 34ms
memory: 3524kb

input:

985391 511611

output:

255806 492696 255806 3

result:

ok single line: '255806 492696 255806 3'

Test #9:

score: 0
Accepted
time: 43ms
memory: 3532kb

input:

435766 614914

output:

304739 215957 307481 2

result:

ok single line: '304739 215957 307481 2'

Test #10:

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

input:

818196 58

output:

29 401921 49 5

result:

ok single line: '29 401921 49 5'

Test #11:

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

input:

401765 19

output:

10 200883 10 6

result:

ok single line: '10 200883 10 6'

Test #12:

score: 0
Accepted
time: 45ms
memory: 3584kb

input:

95 912669

output:

456335 48 456335 2

result:

ok single line: '456335 48 456335 2'

Test #13:

score: 0
Accepted
time: 23ms
memory: 3624kb

input:

81 429950

output:

2655 1 214975 2

result:

ok single line: '2655 1 214975 2'

Test #14:

score: 0
Accepted
time: 70ms
memory: 3540kb

input:

999956 999959

output:

249991 249990 499979 3

result:

ok single line: '249991 249990 499979 3'

Test #15:

score: 0
Accepted
time: 73ms
memory: 3536kb

input:

999935 999946

output:

449976 449971 499976 3

result:

ok single line: '449976 449971 499976 3'

Test #16:

score: 0
Accepted
time: 53ms
memory: 3528kb

input:

999951 999952

output:

1 1 1 2

result:

ok single line: '1 1 1 2'

Test #17:

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

input:

106352 224337

output:

112111 53149 112993 2

result:

ok single line: '112111 53149 112993 2'

Test #18:

score: 0
Accepted
time: 52ms
memory: 3544kb

input:

651870 786333

output:

392936 325744 393775 2

result:

ok single line: '392936 325744 393775 2'

Test #19:

score: 0
Accepted
time: 67ms
memory: 3776kb

input:

838522 972888

output:

486249 419093 486853 2

result:

ok single line: '486249 419093 486853 2'