QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#210705 | #7178. Bishops | ucup-team191# | AC ✓ | 19ms | 5544kb | C++14 | 1.4kb | 2023-10-11 19:10:39 | 2023-10-11 19:10:39 |
Judging History
answer
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
const int N=300010,MOD=1e9+7;
const char en='\n';
const ll LLINF=1ll<<60;
int n,m;
bool sw;
vector<pii> solve(int n,int m)
{
vector<pii> v;
if (n==m)
{
if (n==1) return {{1,1}};
for (int i=1;i<n;++i) v.pb({i,1}),v.pb({i,m});
return v;
}
if (n%2==1)
{
for (int i=1;i<=n;++i) v.pb({i,1}),v.pb({i,m});
int po=(n+1)/2;
for (int i=1;i<=m;++i) if (i>po && i<=m-po) v.pb({po,i});
return v;
}
if (m%2==1)
{
if (m>2*n)
{
for (int i=1;i<=n;++i) v.pb({i,m});
vector<pii> os=solve(n,m-n);
for (auto x: os) v.pb(x);
return v;
}
for (int i=1;i<=n;++i) v.pb({i,1}),v.pb({i,m});
int po=(m+1)/2;
for (int i=1;i<=n;++i)
{
if (i+po>1+n && i<po) v.pb({i,po});
}
return v;
}
for (int i=1;i<=n;++i) v.pb({i,1}),v.pb({i,m});
int po=n/2+1;
for (int i=1;i<=m;++i) if (i>po && i<=m-po) v.pb({po,i});
return v;
}
//XYYYYYYYYX
//XYYYYYYYYX
//XYYYOOYYYX
//XYYYOOYYYX
//XYYYYYYYYX
//XYYYYYYYYX
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
if (n>m)
{
swap(n,m);
sw=1;
}
vector<pii> an=solve(n,m);
cout<<an.size()<<en;
for (auto x: an) if (sw) cout<<x.y<<' '<<x.x<<en;
else cout<<x.x<<' '<<x.y<<en;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3648kb
input:
2 5
output:
6 1 5 2 5 1 1 1 3 2 1 2 3
result:
ok n: 2, m: 5, bishops: 6
Test #2:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
5 5
output:
8 1 1 1 5 2 1 2 5 3 1 3 5 4 1 4 5
result:
ok n: 5, m: 5, bishops: 8
Test #3:
score: 0
Accepted
time: 19ms
memory: 5380kb
input:
100000 100000
output:
199998 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: 100000, m: 100000, bishops: 199998
Test #4:
score: 0
Accepted
time: 16ms
memory: 5192kb
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: 11ms
memory: 5220kb
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: 6ms
memory: 4252kb
input:
1 100000
output:
100000 1 1 1 100000 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 5...
result:
ok n: 1, m: 100000, bishops: 100000
Test #7:
score: 0
Accepted
time: 13ms
memory: 5192kb
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: 11ms
memory: 4312kb
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: 7ms
memory: 4248kb
input:
10000 100000
output:
109998 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: 10000, m: 100000, bishops: 109998
Test #10:
score: 0
Accepted
time: 9ms
memory: 4324kb
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: 9ms
memory: 4304kb
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: 15ms
memory: 5144kb
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: 13ms
memory: 5312kb
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: 12ms
memory: 4260kb
input:
23342 98876
output:
122216 1 1 1 98876 2 1 2 98876 3 1 3 98876 4 1 4 98876 5 1 5 98876 6 1 6 98876 7 1 7 98876 8 1 8 98876 9 1 9 98876 10 1 10 98876 11 1 11 98876 12 1 12 98876 13 1 13 98876 14 1 14 98876 15 1 15 98876 16 1 16 98876 17 1 17 98876 18 1 18 98876 19 1 19 98876 20 1 20 98876 21 1 21 98876 22 1 22 98876 23 ...
result:
ok n: 23342, m: 98876, bishops: 122216
Test #15:
score: 0
Accepted
time: 14ms
memory: 5352kb
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: 11ms
memory: 5148kb
input:
99995 99995
output:
199988 1 1 1 99995 2 1 2 99995 3 1 3 99995 4 1 4 99995 5 1 5 99995 6 1 6 99995 7 1 7 99995 8 1 8 99995 9 1 9 99995 10 1 10 99995 11 1 11 99995 12 1 12 99995 13 1 13 99995 14 1 14 99995 15 1 15 99995 16 1 16 99995 17 1 17 99995 18 1 18 99995 19 1 19 99995 20 1 20 99995 21 1 21 99995 22 1 22 99995 23 ...
result:
ok n: 99995, m: 99995, bishops: 199988
Test #17:
score: 0
Accepted
time: 7ms
memory: 4228kb
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: 14ms
memory: 5224kb
input:
90000 92000
output:
181998 1 1 1 92000 2 1 2 92000 3 1 3 92000 4 1 4 92000 5 1 5 92000 6 1 6 92000 7 1 7 92000 8 1 8 92000 9 1 9 92000 10 1 10 92000 11 1 11 92000 12 1 12 92000 13 1 13 92000 14 1 14 92000 15 1 15 92000 16 1 16 92000 17 1 17 92000 18 1 18 92000 19 1 19 92000 20 1 20 92000 21 1 21 92000 22 1 22 92000 23 ...
result:
ok n: 90000, m: 92000, bishops: 181998
Test #19:
score: 0
Accepted
time: 8ms
memory: 4328kb
input:
10000 70000
output:
79998 1 1 1 70000 2 1 2 70000 3 1 3 70000 4 1 4 70000 5 1 5 70000 6 1 6 70000 7 1 7 70000 8 1 8 70000 9 1 9 70000 10 1 10 70000 11 1 11 70000 12 1 12 70000 13 1 13 70000 14 1 14 70000 15 1 15 70000 16 1 16 70000 17 1 17 70000 18 1 18 70000 19 1 19 70000 20 1 20 70000 21 1 21 70000 22 1 22 70000 23 1...
result:
ok n: 10000, m: 70000, bishops: 79998
Test #20:
score: 0
Accepted
time: 9ms
memory: 5304kb
input:
10000 70001
output:
80000 1 70001 2 70001 3 70001 4 70001 5 70001 6 70001 7 70001 8 70001 9 70001 10 70001 11 70001 12 70001 13 70001 14 70001 15 70001 16 70001 17 70001 18 70001 19 70001 20 70001 21 70001 22 70001 23 70001 24 70001 25 70001 26 70001 27 70001 28 70001 29 70001 30 70001 31 70001 32 70001 33 70001 34 700...
result:
ok n: 10000, m: 70001, bishops: 80000
Test #21:
score: 0
Accepted
time: 9ms
memory: 4156kb
input:
10000 80000
output:
89998 1 1 1 80000 2 1 2 80000 3 1 3 80000 4 1 4 80000 5 1 5 80000 6 1 6 80000 7 1 7 80000 8 1 8 80000 9 1 9 80000 10 1 10 80000 11 1 11 80000 12 1 12 80000 13 1 13 80000 14 1 14 80000 15 1 15 80000 16 1 16 80000 17 1 17 80000 18 1 18 80000 19 1 19 80000 20 1 20 80000 21 1 21 80000 22 1 22 80000 23 1...
result:
ok n: 10000, m: 80000, bishops: 89998
Test #22:
score: 0
Accepted
time: 7ms
memory: 5544kb
input:
10000 80001
output:
90000 1 80001 2 80001 3 80001 4 80001 5 80001 6 80001 7 80001 8 80001 9 80001 10 80001 11 80001 12 80001 13 80001 14 80001 15 80001 16 80001 17 80001 18 80001 19 80001 20 80001 21 80001 22 80001 23 80001 24 80001 25 80001 26 80001 27 80001 28 80001 29 80001 30 80001 31 80001 32 80001 33 80001 34 800...
result:
ok n: 10000, m: 80001, bishops: 90000
Test #23:
score: 0
Accepted
time: 9ms
memory: 4100kb
input:
10000 80002
output:
90000 1 1 1 80002 2 1 2 80002 3 1 3 80002 4 1 4 80002 5 1 5 80002 6 1 6 80002 7 1 7 80002 8 1 8 80002 9 1 9 80002 10 1 10 80002 11 1 11 80002 12 1 12 80002 13 1 13 80002 14 1 14 80002 15 1 15 80002 16 1 16 80002 17 1 17 80002 18 1 18 80002 19 1 19 80002 20 1 20 80002 21 1 21 80002 22 1 22 80002 23 1...
result:
ok n: 10000, m: 80002, bishops: 90000
Test #24:
score: 0
Accepted
time: 11ms
memory: 5528kb
input:
10000 79999
output:
89998 1 79999 2 79999 3 79999 4 79999 5 79999 6 79999 7 79999 8 79999 9 79999 10 79999 11 79999 12 79999 13 79999 14 79999 15 79999 16 79999 17 79999 18 79999 19 79999 20 79999 21 79999 22 79999 23 79999 24 79999 25 79999 26 79999 27 79999 28 79999 29 79999 30 79999 31 79999 32 79999 33 79999 34 799...
result:
ok n: 10000, m: 79999, bishops: 89998
Test #25:
score: 0
Accepted
time: 9ms
memory: 4248kb
input:
10000 79998
output:
89996 1 1 1 79998 2 1 2 79998 3 1 3 79998 4 1 4 79998 5 1 5 79998 6 1 6 79998 7 1 7 79998 8 1 8 79998 9 1 9 79998 10 1 10 79998 11 1 11 79998 12 1 12 79998 13 1 13 79998 14 1 14 79998 15 1 15 79998 16 1 16 79998 17 1 17 79998 18 1 18 79998 19 1 19 79998 20 1 20 79998 21 1 21 79998 22 1 22 79998 23 1...
result:
ok n: 10000, m: 79998, bishops: 89996
Test #26:
score: 0
Accepted
time: 11ms
memory: 4144kb
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: 0ms
memory: 3884kb
input:
1 1
output:
1 1 1
result:
ok n: 1, m: 1, bishops: 1
Extra Test:
score: 0
Extra Test Passed