QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#196869 | #7178. Bishops | wxhtzdy | AC ✓ | 107ms | 25040kb | C++14 | 2.0kb | 2023-10-02 02:00:23 | 2023-10-02 02:00:24 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int readint(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m;
bool swp;
int main(){
scanf("%d%d",&n,&m);
if(n==m){
if(n==1){
printf("1\n1 1\n");
return 0;
}
vector<pii> ans;
for(int i=2;i<n;i++) ans.pb(mp(1,i));
for(int i=1;i<=n;i++) ans.pb(mp(n,i));
printf("%d\n",ans.size());
for(int i=0;i<(int)ans.size();i++) printf("%d %d\n",ans[i].fi,ans[i].se);
return 0;
}
if(n==1||m==1) {
printf("%d\n",n*m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%d %d\n",i,j);
}
}
return 0;
}
if(n<m) swp=true,swap(n,m);
if (m%2==1){
vector<pii> ans;
map<int,bool> d1,d2;
for(int i=1;i<=m;i++){
ans.pb(mp(1,i));
d1[1-i]=true;
d2[1+i]=true;
ans.pb(mp(n,i));
d1[n-i]=true;
d2[n+i]=true;
}
for(int i=1;i<=n;i++){
if(!d1[i-(m+1)/2]&&!d2[i+(m+1)/2]){
d1[i-(m+1)/2]=true;
d2[i+(m+1)/2]=true;
ans.pb(mp(i,(m+1)/2));
}
}
if(swp) for(int i=0;i<(int)ans.size();i++) swap(ans[i].fi,ans[i].se);
printf("%d\n",ans.size());
for(int i=0;i<(int)ans.size();i++) printf("%d %d\n",ans[i].fi,ans[i].se);
return 0;
}
vector<pii> pts;
for(int i=1;i<=m;i++) pts.pb(mp(1,i));
for(int i=1;i<=m;i++) pts.pb(mp(n,i));
for(int i=1;i<=n;i++){
pts.pb(mp(i,m/2));
pts.pb(mp(i,m/2+1));
}
vector<pii> ans;
map<int,bool> d1,d2;
for(auto&p:pts){
int x=p.fi,y=p.se;
if(!d1[x-y]&&!d2[x+y]){
ans.pb(mp(x,y));
d1[x-y]=true;
d2[x+y]=true;
}
}
if(swp) for(int i=0;i<(int)ans.size();i++) swap(ans[i].fi,ans[i].se);
printf("%d\n",ans.size());
for(int i=0;i<(int)ans.size();i++) printf("%d %d\n",ans[i].fi,ans[i].se);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3772kb
input:
2 5
output:
6 1 1 2 1 1 5 2 5 1 3 2 3
result:
ok n: 2, m: 5, bishops: 6
Test #2:
score: 0
Accepted
time: 0ms
memory: 4116kb
input:
5 5
output:
8 1 2 1 3 1 4 5 1 5 2 5 3 5 4 5 5
result:
ok n: 5, m: 5, bishops: 8
Test #3:
score: 0
Accepted
time: 17ms
memory: 5216kb
input:
100000 100000
output:
199998 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 61 1...
result:
ok n: 100000, m: 100000, bishops: 199998
Test #4:
score: 0
Accepted
time: 95ms
memory: 23676kb
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: 103ms
memory: 21288kb
input:
100000 50000
output:
149998 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: 50000, bishops: 149998
Test #6:
score: 0
Accepted
time: 9ms
memory: 3824kb
input:
1 100000
output:
100000 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: 1, m: 100000, bishops: 100000
Test #7:
score: 0
Accepted
time: 66ms
memory: 17664kb
input:
34535 99889
output:
134423 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:
ok n: 34535, m: 99889, bishops: 134423
Test #8:
score: 0
Accepted
time: 60ms
memory: 14528kb
input:
12231 97889
output:
110119 1 1 1 97889 2 1 2 97889 3 1 3 97889 4 1 4 97889 5 1 5 97889 6 1 6 97889 7 1 7 97889 8 1 8 97889 9 1 9 97889 10 1 10 97889 11 1 11 97889 12 1 12 97889 13 1 13 97889 14 1 14 97889 15 1 15 97889 16 1 16 97889 17 1 17 97889 18 1 18 97889 19 1 19 97889 20 1 20 97889 21 1 21 97889 22 1 22 97889 23 ...
result:
ok n: 12231, m: 97889, bishops: 110119
Test #9:
score: 0
Accepted
time: 78ms
memory: 16044kb
input:
10000 100000
output:
109998 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 61...
result:
ok n: 10000, m: 100000, bishops: 109998
Test #10:
score: 0
Accepted
time: 58ms
memory: 13356kb
input:
13 99999
output:
100011 1 1 1 99999 2 1 2 99999 3 1 3 99999 4 1 4 99999 5 1 5 99999 6 1 6 99999 7 1 7 99999 8 1 8 99999 9 1 9 99999 10 1 10 99999 11 1 11 99999 12 1 12 99999 13 1 13 99999 7 8 7 9 7 10 7 11 7 12 7 13 7 14 7 15 7 16 7 17 7 18 7 19 7 20 7 21 7 22 7 23 7 24 7 25 7 26 7 27 7 28 7 29 7 30 7 31 7 32 7 33 7...
result:
ok n: 13, m: 99999, bishops: 100011
Test #11:
score: 0
Accepted
time: 57ms
memory: 13676kb
input:
21 99999
output:
100019 1 1 1 99999 2 1 2 99999 3 1 3 99999 4 1 4 99999 5 1 5 99999 6 1 6 99999 7 1 7 99999 8 1 8 99999 9 1 9 99999 10 1 10 99999 11 1 11 99999 12 1 12 99999 13 1 13 99999 14 1 14 99999 15 1 15 99999 16 1 16 99999 17 1 17 99999 18 1 18 99999 19 1 19 99999 20 1 20 99999 21 1 21 99999 11 12 11 13 11 14...
result:
ok n: 21, m: 99999, bishops: 100019
Test #12:
score: 0
Accepted
time: 75ms
memory: 18436kb
input:
49999 100000
output:
149998 1 1 1 100000 2 1 2 100000 3 1 3 100000 4 1 4 100000 5 1 5 100000 6 1 6 100000 7 1 7 100000 8 1 8 100000 9 1 9 100000 10 1 10 100000 11 1 11 100000 12 1 12 100000 13 1 13 100000 14 1 14 100000 15 1 15 100000 16 1 16 100000 17 1 17 100000 18 1 18 100000 19 1 19 100000 20 1 20 100000 21 1 21 100...
result:
ok n: 49999, m: 100000, bishops: 149998
Test #13:
score: 0
Accepted
time: 70ms
memory: 17692kb
input:
33333 99999
output:
133331 1 1 1 99999 2 1 2 99999 3 1 3 99999 4 1 4 99999 5 1 5 99999 6 1 6 99999 7 1 7 99999 8 1 8 99999 9 1 9 99999 10 1 10 99999 11 1 11 99999 12 1 12 99999 13 1 13 99999 14 1 14 99999 15 1 15 99999 16 1 16 99999 17 1 17 99999 18 1 18 99999 19 1 19 99999 20 1 20 99999 21 1 21 99999 22 1 22 99999 23 ...
result:
ok n: 33333, m: 99999, bishops: 133331
Test #14:
score: 0
Accepted
time: 77ms
memory: 17672kb
input:
23342 98876
output:
122216 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 61...
result:
ok n: 23342, m: 98876, bishops: 122216
Test #15:
score: 0
Accepted
time: 67ms
memory: 18280kb
input:
56713 91234
output:
147946 1 1 1 91234 2 1 2 91234 3 1 3 91234 4 1 4 91234 5 1 5 91234 6 1 6 91234 7 1 7 91234 8 1 8 91234 9 1 9 91234 10 1 10 91234 11 1 11 91234 12 1 12 91234 13 1 13 91234 14 1 14 91234 15 1 15 91234 16 1 16 91234 17 1 17 91234 18 1 18 91234 19 1 19 91234 20 1 20 91234 21 1 21 91234 22 1 22 91234 23 ...
result:
ok n: 56713, m: 91234, bishops: 147946
Test #16:
score: 0
Accepted
time: 16ms
memory: 5324kb
input:
99995 99995
output:
199988 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 61 1...
result:
ok n: 99995, m: 99995, bishops: 199988
Test #17:
score: 0
Accepted
time: 33ms
memory: 10416kb
input:
12345 54321
output:
66665 1 1 1 54321 2 1 2 54321 3 1 3 54321 4 1 4 54321 5 1 5 54321 6 1 6 54321 7 1 7 54321 8 1 8 54321 9 1 9 54321 10 1 10 54321 11 1 11 54321 12 1 12 54321 13 1 13 54321 14 1 14 54321 15 1 15 54321 16 1 16 54321 17 1 17 54321 18 1 18 54321 19 1 19 54321 20 1 20 54321 21 1 21 54321 22 1 22 54321 23 1...
result:
ok n: 12345, m: 54321, bishops: 66665
Test #18:
score: 0
Accepted
time: 107ms
memory: 25040kb
input:
90000 92000
output:
181998 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 61...
result:
ok n: 90000, m: 92000, bishops: 181998
Test #19:
score: 0
Accepted
time: 50ms
memory: 12712kb
input:
10000 70000
output:
79998 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 61 ...
result:
ok n: 10000, m: 70000, bishops: 79998
Test #20:
score: 0
Accepted
time: 52ms
memory: 12720kb
input:
10000 70001
output:
80000 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 61 ...
result:
ok n: 10000, m: 70001, bishops: 80000
Test #21:
score: 0
Accepted
time: 60ms
memory: 13980kb
input:
10000 80000
output:
89998 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 61 ...
result:
ok n: 10000, m: 80000, bishops: 89998
Test #22:
score: 0
Accepted
time: 58ms
memory: 13744kb
input:
10000 80001
output:
90000 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 61 ...
result:
ok n: 10000, m: 80001, bishops: 90000
Test #23:
score: 0
Accepted
time: 59ms
memory: 13724kb
input:
10000 80002
output:
90000 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 61 ...
result:
ok n: 10000, m: 80002, bishops: 90000
Test #24:
score: 0
Accepted
time: 62ms
memory: 13772kb
input:
10000 79999
output:
89998 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 61 ...
result:
ok n: 10000, m: 79999, bishops: 89998
Test #25:
score: 0
Accepted
time: 62ms
memory: 13912kb
input:
10000 79998
output:
89996 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 61 ...
result:
ok n: 10000, m: 79998, bishops: 89996
Test #26:
score: 0
Accepted
time: 50ms
memory: 14520kb
input:
11111 100000
output:
111110 1 1 1 100000 2 1 2 100000 3 1 3 100000 4 1 4 100000 5 1 5 100000 6 1 6 100000 7 1 7 100000 8 1 8 100000 9 1 9 100000 10 1 10 100000 11 1 11 100000 12 1 12 100000 13 1 13 100000 14 1 14 100000 15 1 15 100000 16 1 16 100000 17 1 17 100000 18 1 18 100000 19 1 19 100000 20 1 20 100000 21 1 21 100...
result:
ok n: 11111, m: 100000, bishops: 111110
Test #27:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
1 1
output:
1 1 1
result:
ok n: 1, m: 1, bishops: 1
Extra Test:
score: 0
Extra Test Passed