QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#173637 | #7178. Bishops | ucup-team139# | AC ✓ | 22ms | 5288kb | C++23 | 1.9kb | 2023-09-10 00:49:52 | 2023-09-10 00:49:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> sol;
int n,m;
void check(int n,bool flg){
bool tolto=false;
if(n%2==0)n--,tolto=true;
for(int i=1;i<=n;i+=2){
sol.push_back({i+flg,1});
}
for(int i=1+(m%2==0);i<=n;i+=2){
if((i!=1 && i!=n) || n!=m){
sol.push_back({i+flg,m});
}
}
int tmp = (n+1)/2;
if(n%4==1){
int last = (m%2==1 ? m-tmp+1 : m-tmp+1+1);
if(m%2==0){
if(flg && n+1!=m){
sol.push_back({1,m});
last=min(last,m-tmp);
}
if(tolto && n>=0 && n+1!=m){
sol.push_back({n+1+flg,m});
last=min(last,m-tmp);
}
}
for(int i=tmp+2;i<last;i+=2){
sol.push_back({tmp+flg,i});
}
}else{
int last = (m%2==1 ? m-tmp+1 : m-tmp+1+1);
if(m%2==0){
if(flg && n+1!=m){
sol.push_back({1,m});
last=min(last,m-tmp);
}
if(tolto && n>=0 && n+1!=m){
sol.push_back({n+1+flg,m});
last=min(last,m-tmp);
}
}
for(int i=tmp+2;i<last;i+=2){
sol.push_back({tmp+flg,i});
}
}
}
void solve(int t){
cin>>n>>m;
bool inv = false;
if(n>m){
swap(n,m);
inv=true;
}
check(n,false);
check(n-1,true);
//assert((n==1 && m==1) || sol.size()==n+m-1 || (n==m && sol.size()==n+m-2));
cout<<sol.size()<<"\n";
for(auto [x,y] : sol){
if(inv)swap(x,y);
cout<<x<<" "<<y<<"\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
//cin>>t;
for(int i=1;i<=t;i++)solve(i);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3668kb
input:
2 5
output:
6 1 1 1 5 1 3 2 1 2 5 2 3
result:
ok n: 2, m: 5, bishops: 6
Test #2:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
5 5
output:
8 1 1 3 1 5 1 3 5 2 1 4 1 2 5 4 5
result:
ok n: 5, m: 5, bishops: 8
Test #3:
score: 0
Accepted
time: 22ms
memory: 5200kb
input:
100000 100000
output:
199998 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 1 ...
result:
ok n: 100000, m: 100000, bishops: 199998
Test #4:
score: 0
Accepted
time: 18ms
memory: 5188kb
input:
100000 99999
output:
199998 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: 99999, bishops: 199998
Test #5:
score: 0
Accepted
time: 13ms
memory: 5228kb
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: 11ms
memory: 4164kb
input:
1 100000
output:
100000 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: 1, m: 100000, bishops: 100000
Test #7:
score: 0
Accepted
time: 12ms
memory: 5216kb
input:
34535 99889
output:
134423 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 1 ...
result:
ok n: 34535, m: 99889, bishops: 134423
Test #8:
score: 0
Accepted
time: 2ms
memory: 4204kb
input:
12231 97889
output:
110119 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 1 ...
result:
ok n: 12231, m: 97889, bishops: 110119
Test #9:
score: 0
Accepted
time: 4ms
memory: 4124kb
input:
10000 100000
output:
109998 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 1 ...
result:
ok n: 10000, m: 100000, bishops: 109998
Test #10:
score: 0
Accepted
time: 11ms
memory: 4152kb
input:
13 99999
output:
100011 1 1 3 1 5 1 7 1 9 1 11 1 13 1 1 99999 3 99999 5 99999 7 99999 9 99999 11 99999 13 99999 7 9 7 11 7 13 7 15 7 17 7 19 7 21 7 23 7 25 7 27 7 29 7 31 7 33 7 35 7 37 7 39 7 41 7 43 7 45 7 47 7 49 7 51 7 53 7 55 7 57 7 59 7 61 7 63 7 65 7 67 7 69 7 71 7 73 7 75 7 77 7 79 7 81 7 83 7 85 7 87 7 89 7...
result:
ok n: 13, m: 99999, bishops: 100011
Test #11:
score: 0
Accepted
time: 11ms
memory: 4104kb
input:
21 99999
output:
100019 1 1 3 1 5 1 7 1 9 1 11 1 13 1 15 1 17 1 19 1 21 1 1 99999 3 99999 5 99999 7 99999 9 99999 11 99999 13 99999 15 99999 17 99999 19 99999 21 99999 11 13 11 15 11 17 11 19 11 21 11 23 11 25 11 27 11 29 11 31 11 33 11 35 11 37 11 39 11 41 11 43 11 45 11 47 11 49 11 51 11 53 11 55 11 57 11 59 11 61...
result:
ok n: 21, m: 99999, bishops: 100019
Test #12:
score: 0
Accepted
time: 11ms
memory: 5212kb
input:
49999 100000
output:
149998 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 1 ...
result:
ok n: 49999, m: 100000, bishops: 149998
Test #13:
score: 0
Accepted
time: 10ms
memory: 5288kb
input:
33333 99999
output:
133331 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 1 ...
result:
ok n: 33333, m: 99999, bishops: 133331
Test #14:
score: 0
Accepted
time: 6ms
memory: 4168kb
input:
23342 98876
output:
122216 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 1 ...
result:
ok n: 23342, m: 98876, bishops: 122216
Test #15:
score: 0
Accepted
time: 17ms
memory: 5272kb
input:
56713 91234
output:
147946 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 1 ...
result:
ok n: 56713, m: 91234, bishops: 147946
Test #16:
score: 0
Accepted
time: 17ms
memory: 5208kb
input:
99995 99995
output:
199988 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 1 ...
result:
ok n: 99995, m: 99995, bishops: 199988
Test #17:
score: 0
Accepted
time: 5ms
memory: 4144kb
input:
12345 54321
output:
66665 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 1 1...
result:
ok n: 12345, m: 54321, bishops: 66665
Test #18:
score: 0
Accepted
time: 16ms
memory: 5156kb
input:
90000 92000
output:
181998 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 1 ...
result:
ok n: 90000, m: 92000, bishops: 181998
Test #19:
score: 0
Accepted
time: 6ms
memory: 4220kb
input:
10000 70000
output:
79998 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 1 1...
result:
ok n: 10000, m: 70000, bishops: 79998
Test #20:
score: 0
Accepted
time: 10ms
memory: 4132kb
input:
10000 70001
output:
80000 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 1 1...
result:
ok n: 10000, m: 70001, bishops: 80000
Test #21:
score: 0
Accepted
time: 2ms
memory: 4180kb
input:
10000 80000
output:
89998 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 1 1...
result:
ok n: 10000, m: 80000, bishops: 89998
Test #22:
score: 0
Accepted
time: 8ms
memory: 4228kb
input:
10000 80001
output:
90000 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 1 1...
result:
ok n: 10000, m: 80001, bishops: 90000
Test #23:
score: 0
Accepted
time: 8ms
memory: 4232kb
input:
10000 80002
output:
90000 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 1 1...
result:
ok n: 10000, m: 80002, bishops: 90000
Test #24:
score: 0
Accepted
time: 5ms
memory: 4144kb
input:
10000 79999
output:
89998 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 1 1...
result:
ok n: 10000, m: 79999, bishops: 89998
Test #25:
score: 0
Accepted
time: 9ms
memory: 4204kb
input:
10000 79998
output:
89996 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 1 1...
result:
ok n: 10000, m: 79998, bishops: 89996
Test #26:
score: 0
Accepted
time: 13ms
memory: 4204kb
input:
11111 100000
output:
111110 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 1 ...
result:
ok n: 11111, m: 100000, bishops: 111110
Test #27:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
1 1
output:
1 1 1
result:
ok n: 1, m: 1, bishops: 1
Extra Test:
score: 0
Extra Test Passed