QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#169806#7178. Bishopsucup-team1477#AC ✓186ms25904kbC++141.4kb2023-09-09 14:04:302023-09-09 14:04:30

Judging History

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

  • [2023-09-09 14:04:30]
  • 评测
  • 测评结果:AC
  • 用时:186ms
  • 内存:25904kb
  • [2023-09-09 14:04:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
set<int>se;
struct qj
{
	int wz,l,r;
}q[200005];
int cnt;
bool bi(struct qj x,struct qj y)
{
	return x.r<y.r;
} 
int qx[200005],qy[200005],tmp;
int main()
{
	int n,m;
	n=read();
	m=read();
	cnt=0;
	for(int i=2;i<=n+m;i+=2)
	{
		int minx=max(1,i-m),maxx=min(n,i-1);
		q[++cnt].wz=i;
		q[cnt].l=minx-i/2;
		q[cnt].r=maxx-i/2;
	}
	sort(q+1,q+cnt+1,bi);
	for(int i=-(n+m);i<=(n+m);i++)se.insert(i);
	for(int i=1;i<=cnt;i++)
	{
		set<int>::iterator it=se.lower_bound(q[i].l);
		if(it==se.end()||(*it)>q[i].r)continue;
		int sth=(*it),nx=sth+q[i].wz/2,ny=q[i].wz-nx;
		se.erase(it);
		qx[++tmp]=nx;
		qy[tmp]=ny;
	}
	cnt=0;
	for(int i=3;i<=n+m;i+=2)
	{
		int minx=max(1,i-m),maxx=min(n,i-1);
		q[++cnt].wz=i;
		q[cnt].l=minx-i/2;
		q[cnt].r=maxx-i/2;
	}
	sort(q+1,q+cnt+1,bi);
	se.clear();
	for(int i=-(n+m);i<=(n+m);i++)se.insert(i);
	for(int i=1;i<=cnt;i++)
	{
		set<int>::iterator it=se.lower_bound(q[i].l);
		if(it==se.end()||(*it)>q[i].r)continue;
		int sth=(*it),nx=sth+q[i].wz/2,ny=q[i].wz-nx;
		se.erase(it);
		qx[++tmp]=nx;
		qy[tmp]=ny;
	}
	printf("%d\n",tmp);
	for(int i=1;i<=tmp;i++)printf("%d %d\n",qx[i],qy[i]);
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5948kb

input:

2 5

output:

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

result:

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

Test #2:

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

input:

5 5

output:

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

result:

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

Test #3:

score: 0
Accepted
time: 181ms
memory: 25904kb

input:

100000 100000

output:

199998
1 1
1 3
100000 99998
1 5
100000 99996
1 7
100000 99994
1 9
100000 99992
1 11
100000 99990
1 13
100000 99988
1 15
100000 99986
1 17
100000 99984
1 19
100000 99982
1 21
100000 99980
1 23
100000 99978
1 25
100000 99976
1 27
100000 99974
99972 100000
29 1
1 31
100000 99970
1 33
100000 99968
1 35
...

result:

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

Test #4:

score: 0
Accepted
time: 182ms
memory: 25304kb

input:

100000 99999

output:

199998
1 1
1 3
100000 99998
1 5
100000 99996
1 7
100000 99994
1 9
100000 99992
1 11
100000 99990
1 13
100000 99988
1 15
100000 99986
1 17
100000 99984
1 19
100000 99982
1 21
100000 99980
1 23
100000 99978
1 25
100000 99976
1 27
100000 99974
1 29
100000 99972
100000 99970
1 31
1 33
100000 99968
1 35
...

result:

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

Test #5:

score: 0
Accepted
time: 130ms
memory: 21208kb

input:

100000 50000

output:

149998
1 1
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 113
1 115
...

result:

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

Test #6:

score: 0
Accepted
time: 74ms
memory: 15716kb

input:

1 100000

output:

100000
1 99999
1 99997
1 99995
1 99993
1 99991
1 99989
1 99987
1 99985
1 99983
1 99981
1 99979
1 99977
1 99975
1 99973
1 99971
1 99969
1 99967
1 99965
1 99963
1 99961
1 99959
1 99957
1 99955
1 99953
1 99951
1 99949
1 99947
1 99945
1 99943
1 99941
1 99939
1 99937
1 99935
1 99933
1 99931
1 99929
1 999...

result:

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

Test #7:

score: 0
Accepted
time: 125ms
memory: 19508kb

input:

34535 99889

output:

134423
34535 99889
34533 99889
34531 99889
34529 99889
34527 99889
34525 99889
34523 99889
34521 99889
34519 99889
34517 99889
34515 99889
34513 99889
34511 99889
34509 99889
34507 99889
34505 99889
34503 99889
34501 99889
34499 99889
34497 99889
34495 99889
34493 99889
34491 99889
34489 99889
34487...

result:

ok n: 34535, m: 99889, bishops: 134423

Test #8:

score: 0
Accepted
time: 94ms
memory: 16412kb

input:

12231 97889

output:

110119
12231 97889
12229 97889
12227 97889
12225 97889
12223 97889
12221 97889
12219 97889
12217 97889
12215 97889
12213 97889
12211 97889
12209 97889
12207 97889
12205 97889
12203 97889
12201 97889
12199 97889
12197 97889
12195 97889
12193 97889
12191 97889
12189 97889
12187 97889
12185 97889
12183...

result:

ok n: 12231, m: 97889, bishops: 110119

Test #9:

score: 0
Accepted
time: 86ms
memory: 16984kb

input:

10000 100000

output:

109998
10000 100000
9998 100000
9996 100000
9994 100000
9992 100000
9990 100000
9988 100000
9986 100000
9984 100000
9982 100000
9980 100000
9978 100000
9976 100000
9974 100000
9972 100000
9970 100000
9968 100000
9966 100000
9964 100000
9962 100000
9960 100000
9958 100000
9956 100000
9954 100000
9952...

result:

ok n: 10000, m: 100000, bishops: 109998

Test #10:

score: 0
Accepted
time: 75ms
memory: 16092kb

input:

13 99999

output:

100011
13 99999
11 99999
9 99999
7 99999
5 99999
3 99999
1 99999
7 99991
7 99989
7 99987
7 99985
7 99983
7 99981
7 99979
7 99977
7 99975
7 99973
7 99971
7 99969
7 99967
7 99965
7 99963
7 99961
7 99959
7 99957
7 99955
7 99953
7 99951
7 99949
7 99947
7 99945
7 99943
7 99941
7 99939
7 99937
7 99935
7 9...

result:

ok n: 13, m: 99999, bishops: 100011

Test #11:

score: 0
Accepted
time: 71ms
memory: 15560kb

input:

21 99999

output:

100019
21 99999
19 99999
17 99999
15 99999
13 99999
11 99999
9 99999
7 99999
5 99999
3 99999
1 99999
11 99987
11 99985
11 99983
11 99981
11 99979
11 99977
11 99975
11 99973
11 99971
11 99969
11 99967
11 99965
11 99963
11 99961
11 99959
11 99957
11 99955
11 99953
11 99951
11 99949
11 99947
11 99945
1...

result:

ok n: 21, m: 99999, bishops: 100019

Test #12:

score: 0
Accepted
time: 139ms
memory: 20388kb

input:

49999 100000

output:

149998
49998 100000
49996 100000
49994 100000
49992 100000
49990 100000
49988 100000
49986 100000
49984 100000
49982 100000
49980 100000
49978 100000
49976 100000
49974 100000
49972 100000
49970 100000
49968 100000
49966 100000
49964 100000
49962 100000
49960 100000
49958 100000
49956 100000
49954 1...

result:

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

Test #13:

score: 0
Accepted
time: 111ms
memory: 18668kb

input:

33333 99999

output:

133331
33333 99999
33331 99999
33329 99999
33327 99999
33325 99999
33323 99999
33321 99999
33319 99999
33317 99999
33315 99999
33313 99999
33311 99999
33309 99999
33307 99999
33305 99999
33303 99999
33301 99999
33299 99999
33297 99999
33295 99999
33293 99999
33291 99999
33289 99999
33287 99999
33285...

result:

ok n: 33333, m: 99999, bishops: 133331

Test #14:

score: 0
Accepted
time: 104ms
memory: 18288kb

input:

23342 98876

output:

122216
23342 98876
23340 98876
23338 98876
23336 98876
23334 98876
23332 98876
23330 98876
23328 98876
23326 98876
23324 98876
23322 98876
23320 98876
23318 98876
23316 98876
23314 98876
23312 98876
23310 98876
23308 98876
23306 98876
23304 98876
23302 98876
23300 98876
23298 98876
23296 98876
23294...

result:

ok n: 23342, m: 98876, bishops: 122216

Test #15:

score: 0
Accepted
time: 126ms
memory: 20320kb

input:

56713 91234

output:

147946
56712 91234
56710 91234
56708 91234
56706 91234
56704 91234
56702 91234
56700 91234
56698 91234
56696 91234
56694 91234
56692 91234
56690 91234
56688 91234
56686 91234
56684 91234
56682 91234
56680 91234
56678 91234
56676 91234
56674 91234
56672 91234
56670 91234
56668 91234
56666 91234
56664...

result:

ok n: 56713, m: 91234, bishops: 147946

Test #16:

score: 0
Accepted
time: 186ms
memory: 25432kb

input:

99995 99995

output:

199988
1 1
1 3
99995 99993
1 5
99995 99991
1 7
99995 99989
1 9
99995 99987
1 11
99995 99985
1 13
99995 99983
1 15
99995 99981
1 17
99995 99979
1 19
99995 99977
1 21
99995 99975
1 23
99995 99973
1 25
99995 99971
1 27
99995 99969
99967 99995
29 1
1 31
99995 99965
1 33
99995 99963
1 35
99995 99961
9995...

result:

ok n: 99995, m: 99995, bishops: 199988

Test #17:

score: 0
Accepted
time: 51ms
memory: 11004kb

input:

12345 54321

output:

66665
12345 54321
12343 54321
12341 54321
12339 54321
12337 54321
12335 54321
12333 54321
12331 54321
12329 54321
12327 54321
12325 54321
12323 54321
12321 54321
12319 54321
12317 54321
12315 54321
12313 54321
12311 54321
12309 54321
12307 54321
12305 54321
12303 54321
12301 54321
12299 54321
12297 ...

result:

ok n: 12345, m: 54321, bishops: 66665

Test #18:

score: 0
Accepted
time: 155ms
memory: 24264kb

input:

90000 92000

output:

181998
90000 92000
89998 92000
89996 92000
89994 92000
89992 92000
89990 92000
89988 92000
89986 92000
89984 92000
89982 92000
89980 92000
89978 92000
89976 92000
89974 92000
89972 92000
89970 92000
89968 92000
89966 92000
89964 92000
89962 92000
89960 92000
89958 92000
89956 92000
89954 92000
89952...

result:

ok n: 90000, m: 92000, bishops: 181998

Test #19:

score: 0
Accepted
time: 68ms
memory: 14096kb

input:

10000 70000

output:

79998
10000 70000
9998 70000
9996 70000
9994 70000
9992 70000
9990 70000
9988 70000
9986 70000
9984 70000
9982 70000
9980 70000
9978 70000
9976 70000
9974 70000
9972 70000
9970 70000
9968 70000
9966 70000
9964 70000
9962 70000
9960 70000
9958 70000
9956 70000
9954 70000
9952 70000
9950 70000
9948 70...

result:

ok n: 10000, m: 70000, bishops: 79998

Test #20:

score: 0
Accepted
time: 65ms
memory: 13696kb

input:

10000 70001

output:

80000
9999 70001
9997 70001
9995 70001
9993 70001
9991 70001
9989 70001
9987 70001
9985 70001
9983 70001
9981 70001
9979 70001
9977 70001
9975 70001
9973 70001
9971 70001
9969 70001
9967 70001
9965 70001
9963 70001
9961 70001
9959 70001
9957 70001
9955 70001
9953 70001
9951 70001
9949 70001
9947 700...

result:

ok n: 10000, m: 70001, bishops: 80000

Test #21:

score: 0
Accepted
time: 72ms
memory: 15164kb

input:

10000 80000

output:

89998
10000 80000
9998 80000
9996 80000
9994 80000
9992 80000
9990 80000
9988 80000
9986 80000
9984 80000
9982 80000
9980 80000
9978 80000
9976 80000
9974 80000
9972 80000
9970 80000
9968 80000
9966 80000
9964 80000
9962 80000
9960 80000
9958 80000
9956 80000
9954 80000
9952 80000
9950 80000
9948 80...

result:

ok n: 10000, m: 80000, bishops: 89998

Test #22:

score: 0
Accepted
time: 69ms
memory: 14600kb

input:

10000 80001

output:

90000
9999 80001
9997 80001
9995 80001
9993 80001
9991 80001
9989 80001
9987 80001
9985 80001
9983 80001
9981 80001
9979 80001
9977 80001
9975 80001
9973 80001
9971 80001
9969 80001
9967 80001
9965 80001
9963 80001
9961 80001
9959 80001
9957 80001
9955 80001
9953 80001
9951 80001
9949 80001
9947 800...

result:

ok n: 10000, m: 80001, bishops: 90000

Test #23:

score: 0
Accepted
time: 78ms
memory: 14660kb

input:

10000 80002

output:

90000
10000 80002
9998 80002
9996 80002
9994 80002
9992 80002
9990 80002
9988 80002
9986 80002
9984 80002
9982 80002
9980 80002
9978 80002
9976 80002
9974 80002
9972 80002
9970 80002
9968 80002
9966 80002
9964 80002
9962 80002
9960 80002
9958 80002
9956 80002
9954 80002
9952 80002
9950 80002
9948 80...

result:

ok n: 10000, m: 80002, bishops: 90000

Test #24:

score: 0
Accepted
time: 64ms
memory: 14364kb

input:

10000 79999

output:

89998
9999 79999
9997 79999
9995 79999
9993 79999
9991 79999
9989 79999
9987 79999
9985 79999
9983 79999
9981 79999
9979 79999
9977 79999
9975 79999
9973 79999
9971 79999
9969 79999
9967 79999
9965 79999
9963 79999
9961 79999
9959 79999
9957 79999
9955 79999
9953 79999
9951 79999
9949 79999
9947 799...

result:

ok n: 10000, m: 79999, bishops: 89998

Test #25:

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

input:

10000 79998

output:

89996
10000 79998
9998 79998
9996 79998
9994 79998
9992 79998
9990 79998
9988 79998
9986 79998
9984 79998
9982 79998
9980 79998
9978 79998
9976 79998
9974 79998
9972 79998
9970 79998
9968 79998
9966 79998
9964 79998
9962 79998
9960 79998
9958 79998
9956 79998
9954 79998
9952 79998
9950 79998
9948 79...

result:

ok n: 10000, m: 79998, bishops: 89996

Test #26:

score: 0
Accepted
time: 98ms
memory: 16784kb

input:

11111 100000

output:

111110
11110 100000
11108 100000
11106 100000
11104 100000
11102 100000
11100 100000
11098 100000
11096 100000
11094 100000
11092 100000
11090 100000
11088 100000
11086 100000
11084 100000
11082 100000
11080 100000
11078 100000
11076 100000
11074 100000
11072 100000
11070 100000
11068 100000
11066 1...

result:

ok n: 11111, m: 100000, bishops: 111110

Test #27:

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

input:

1 1

output:

1
1 1

result:

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

Extra Test:

score: 0
Extra Test Passed