QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333972#7178. BishopsivanjWA 135ms23692kbC++141.3kb2024-02-20 22:05:302024-02-20 22:05:31

Judging History

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

  • [2024-02-20 22:05:31]
  • 评测
  • 测评结果:WA
  • 用时:135ms
  • 内存:23692kb
  • [2024-02-20 22:05:30]
  • 提交

answer

#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e5 + 5;

int n, m, flag;
vector<ii> ans;
map<int, int> d1, d2;

void add(int x, int y) {
	ans.pb({x, y});
	d1[x + y]++, d2[x - y]++;	
}

int main() {
	scanf("%d%d", &n, &m);
	if(n > m) swap(m, n), flag = 1;
	
	if(n == m) {
		for(int i = 0;i < n;i++) ans.pb({0, i});
		for(int i = 1;i < n - 1;i++) ans.pb({n - 1, i});
	} else {
		for(int i = 0;i < n;i++)
			add(i, 0), add(i, m - 1);
		
		vector<int> v10, v20, v11, v21;
		for(int i = 0;i < n + m - 1;i++)
			if(d1[i] == 0) {
				if(i & 1) v11.pb(i);
				else v10.pb(i);	
			}
	
		for(int i = -m + 1;i < n;i++)
			if(d2[i] == 0) {
				if(i & 1) v21.pb(i);
				else v20.pb(i);	
			}
		
		int N = min(v10.size(), v20.size());
		int M = min(v11.size(), v20.size());
		reverse(all(v20));
		reverse(all(v21));
		for(int i = 0;i < N;i++) 
			ans.pb({(v10[i] + v20[i]) / 2, (v10[i] - v20[i]) / 2});
		for(int i = 0;i < M;i++) 
			ans.pb({(v11[i] + v21[i]) / 2, (v11[i] - v21[i]) / 2});
	}
	
	printf("%d\n", (int)ans.size());
	for(ii p : ans)
		if(flag == 0) printf("%d %d\n", p.x + 1, p.y + 1);
		else printf("%d %d\n", p.y + 1, p.x + 1);
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 5

output:

6
1 1
1 5
2 1
2 5
1 3
2 3

result:

ok n: 2, m: 5, bishops: 6

Test #2:

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

input:

5 5

output:

8
1 1
1 2
1 3
1 4
1 5
5 2
5 3
5 4

result:

ok n: 5, m: 5, bishops: 8

Test #3:

score: 0
Accepted
time: 14ms
memory: 5312kb

input:

100000 100000

output:

199998
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 ...

result:

ok n: 100000, m: 100000, bishops: 199998

Test #4:

score: 0
Accepted
time: 135ms
memory: 23692kb

input:

100000 99999

output:

199998
1 1
100000 1
1 2
100000 2
1 3
100000 3
1 4
100000 4
1 5
100000 5
1 6
100000 6
1 7
100000 7
1 8
100000 8
1 9
100000 9
1 10
100000 10
1 11
100000 11
1 12
100000 12
1 13
100000 13
1 14
100000 14
1 15
100000 15
1 16
100000 16
1 17
100000 17
1 18
100000 18
1 19
100000 19
1 20
100000 20
1 21
100000...

result:

ok n: 100000, m: 99999, bishops: 199998

Test #5:

score: 0
Accepted
time: 88ms
memory: 19776kb

input:

100000 50000

output:

149998
1 1
100000 1
1 2
100000 2
1 3
100000 3
1 4
100000 4
1 5
100000 5
1 6
100000 6
1 7
100000 7
1 8
100000 8
1 9
100000 9
1 10
100000 10
1 11
100000 11
1 12
100000 12
1 13
100000 13
1 14
100000 14
1 15
100000 15
1 16
100000 16
1 17
100000 17
1 18
100000 18
1 19
100000 19
1 20
100000 20
1 21
100000...

result:

ok n: 100000, m: 50000, bishops: 149998

Test #6:

score: 0
Accepted
time: 25ms
memory: 14464kb

input:

1 100000

output:

100000
1 1
1 100000
1 3
1 5
1 7
1 9
1 11
1 13
1 15
1 17
1 19
1 21
1 23
1 25
1 27
1 29
1 31
1 33
1 35
1 37
1 39
1 41
1 43
1 45
1 47
1 49
1 51
1 53
1 55
1 57
1 59
1 61
1 63
1 65
1 67
1 69
1 71
1 73
1 75
1 77
1 79
1 81
1 83
1 85
1 87
1 89
1 91
1 93
1 95
1 97
1 99
1 101
1 103
1 105
1 107
1 109
1 111
1 1...

result:

ok n: 1, m: 100000, bishops: 100000

Test #7:

score: -100
Wrong Answer
time: 65ms
memory: 18428kb

input:

34535 99889

output:

134422
1 1
1 99889
2 1
2 99889
3 1
3 99889
4 1
4 99889
5 1
5 99889
6 1
6 99889
7 1
7 99889
8 1
8 99889
9 1
9 99889
10 1
10 99889
11 1
11 99889
12 1
12 99889
13 1
13 99889
14 1
14 99889
15 1
15 99889
16 1
16 99889
17 1
17 99889
18 1
18 99889
19 1
19 99889
20 1
20 99889
21 1
21 99889
22 1
22 99889
23 ...

result:

wrong answer Participant's answer is not optimal (134422 < 134423)