QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#166502 | #7178. Bishops | ucup-team1209# | AC ✓ | 35ms | 14964kb | C++20 | 1.3kb | 2023-09-06 14:02:24 | 2023-09-06 14:02:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
#define templ template<typename T>
templ bool chkmin(T &x,T y){return x>y?x=y,1:0;}
templ bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
#ifdef zqj
freopen("a.in","r",stdin);
#endif
}
#define sz 122222
int n,m;
// array<int,3>a[sz<<1];
vector<pii>V[sz<<1];
int main() {
file();
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>m;
rep(i,2,n+m) {
int l=2-i,r=2*n-i;
chkmin(r,i-2);
chkmax(l,i-2*m);
chkmax(l,1-m);
chkmin(r,n-1);
assert(l<=r);
l+=m,r+=m;
V[l].push_back({r,i});
}
vector<pii>ans;
priority_queue<pii,vector<pii>,greater<pii>>q[2];
rep(j,1,n+m-1) {
for (auto [r,id]:V[j]) q[j&1].push({r,id});
while (q[j&1].size()&&q[j&1].top().fir<j) q[j&1].pop();
if (q[j&1].size()) {
auto [r,id]=q[j&1].top(); q[j&1].pop();
ans.push_back({(id+(j-m))/2,(id-(j-m))/2});
}
}
cout<<ans.size()<<'\n';
for (auto [x,y]:ans) cout<<x<<' '<<y<<'\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 9240kb
input:
2 5
output:
6 1 5 2 5 1 3 2 3 1 1 2 1
result:
ok n: 2, m: 5, bishops: 6
Test #2:
score: 0
Accepted
time: 1ms
memory: 9268kb
input:
5 5
output:
8 1 5 1 4 1 3 1 2 1 1 5 4 5 3 5 2
result:
ok n: 5, m: 5, bishops: 8
Test #3:
score: 0
Accepted
time: 28ms
memory: 14964kb
input:
100000 100000
output:
199998 1 100000 1 99999 1 99998 1 99997 1 99996 1 99995 1 99994 1 99993 1 99992 1 99991 1 99990 1 99989 1 99988 1 99987 1 99986 1 99985 1 99984 1 99983 1 99982 1 99981 1 99980 1 99979 1 99978 1 99977 1 99976 1 99975 1 99974 1 99973 1 99972 1 99971 1 99970 1 99969 1 99968 1 99967 1 99966 1 99965 1 99...
result:
ok n: 100000, m: 100000, bishops: 199998
Test #4:
score: 0
Accepted
time: 33ms
memory: 14952kb
input:
100000 99999
output:
199998 1 99999 1 99998 1 99997 1 99996 1 99995 1 99994 1 99993 1 99992 1 99991 1 99990 1 99989 1 99988 1 99987 1 99986 1 99985 1 99984 1 99983 1 99982 1 99981 1 99980 1 99979 1 99978 1 99977 1 99976 1 99975 1 99974 1 99973 1 99972 1 99971 1 99970 1 99969 1 99968 1 99967 1 99966 1 99965 1 99964 1 999...
result:
ok n: 100000, m: 99999, bishops: 199998
Test #5:
score: 0
Accepted
time: 22ms
memory: 14596kb
input:
100000 50000
output:
149998 1 50000 1 49999 1 49998 1 49997 1 49996 1 49995 1 49994 1 49993 1 49992 1 49991 1 49990 1 49989 1 49988 1 49987 1 49986 1 49985 1 49984 1 49983 1 49982 1 49981 1 49980 1 49979 1 49978 1 49977 1 49976 1 49975 1 49974 1 49973 1 49972 1 49971 1 49970 1 49969 1 49968 1 49967 1 49966 1 49965 1 499...
result:
ok n: 100000, m: 50000, bishops: 149998
Test #6:
score: 0
Accepted
time: 7ms
memory: 12980kb
input:
1 100000
output:
100000 1 100000 1 99999 1 99998 1 99997 1 99996 1 99995 1 99994 1 99993 1 99992 1 99991 1 99990 1 99989 1 99988 1 99987 1 99986 1 99985 1 99984 1 99983 1 99982 1 99981 1 99980 1 99979 1 99978 1 99977 1 99976 1 99975 1 99974 1 99973 1 99972 1 99971 1 99970 1 99969 1 99968 1 99967 1 99966 1 99965 1 99...
result:
ok n: 1, m: 100000, bishops: 100000
Test #7:
score: 0
Accepted
time: 15ms
memory: 14364kb
input:
34535 99889
output:
134423 1 99889 2 99889 3 99889 4 99889 5 99889 6 99889 7 99889 8 99889 9 99889 10 99889 11 99889 12 99889 13 99889 14 99889 15 99889 16 99889 17 99889 18 99889 19 99889 20 99889 21 99889 22 99889 23 99889 24 99889 25 99889 26 99889 27 99889 28 99889 29 99889 30 99889 31 99889 32 99889 33 99889 34 99...
result:
ok n: 34535, m: 99889, bishops: 134423
Test #8:
score: 0
Accepted
time: 15ms
memory: 13156kb
input:
12231 97889
output:
110119 1 97889 2 97889 3 97889 4 97889 5 97889 6 97889 7 97889 8 97889 9 97889 10 97889 11 97889 12 97889 13 97889 14 97889 15 97889 16 97889 17 97889 18 97889 19 97889 20 97889 21 97889 22 97889 23 97889 24 97889 25 97889 26 97889 27 97889 28 97889 29 97889 30 97889 31 97889 32 97889 33 97889 34 97...
result:
ok n: 12231, m: 97889, bishops: 110119
Test #9:
score: 0
Accepted
time: 15ms
memory: 13088kb
input:
10000 100000
output:
109998 1 100000 2 100000 3 100000 4 100000 5 100000 6 100000 7 100000 8 100000 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31...
result:
ok n: 10000, m: 100000, bishops: 109998
Test #10:
score: 0
Accepted
time: 12ms
memory: 12904kb
input:
13 99999
output:
100011 1 99999 2 99999 3 99999 4 99999 5 99999 6 99999 7 99999 8 99999 9 99999 10 99999 11 99999 12 99999 13 99999 7 99992 7 99991 7 99990 7 99989 7 99988 7 99987 7 99986 7 99985 7 99984 7 99983 7 99982 7 99981 7 99980 7 99979 7 99978 7 99977 7 99976 7 99975 7 99974 7 99973 7 99972 7 99971 7 99970 7...
result:
ok n: 13, m: 99999, bishops: 100011
Test #11:
score: 0
Accepted
time: 10ms
memory: 12908kb
input:
21 99999
output:
100019 1 99999 2 99999 3 99999 4 99999 5 99999 6 99999 7 99999 8 99999 9 99999 10 99999 11 99999 12 99999 13 99999 14 99999 15 99999 16 99999 17 99999 18 99999 19 99999 20 99999 21 99999 11 99988 11 99987 11 99986 11 99985 11 99984 11 99983 11 99982 11 99981 11 99980 11 99979 11 99978 11 99977 11 99...
result:
ok n: 21, m: 99999, bishops: 100019
Test #12:
score: 0
Accepted
time: 32ms
memory: 14508kb
input:
49999 100000
output:
149998 1 100000 2 100000 3 100000 4 100000 5 100000 6 100000 7 100000 8 100000 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31...
result:
ok n: 49999, m: 100000, bishops: 149998
Test #13:
score: 0
Accepted
time: 25ms
memory: 14440kb
input:
33333 99999
output:
133331 1 99999 2 99999 3 99999 4 99999 5 99999 6 99999 7 99999 8 99999 9 99999 10 99999 11 99999 12 99999 13 99999 14 99999 15 99999 16 99999 17 99999 18 99999 19 99999 20 99999 21 99999 22 99999 23 99999 24 99999 25 99999 26 99999 27 99999 28 99999 29 99999 30 99999 31 99999 32 99999 33 99999 34 99...
result:
ok n: 33333, m: 99999, bishops: 133331
Test #14:
score: 0
Accepted
time: 18ms
memory: 13248kb
input:
23342 98876
output:
122216 1 98876 2 98876 3 98876 4 98876 5 98876 6 98876 7 98876 8 98876 9 98876 10 98876 11 98876 12 98876 13 98876 14 98876 15 98876 16 98876 17 98876 18 98876 19 98876 20 98876 21 98876 22 98876 23 98876 24 98876 25 98876 26 98876 27 98876 28 98876 29 98876 30 98876 31 98876 32 98876 33 98876 34 98...
result:
ok n: 23342, m: 98876, bishops: 122216
Test #15:
score: 0
Accepted
time: 24ms
memory: 14328kb
input:
56713 91234
output:
147946 1 91234 2 91234 3 91234 4 91234 5 91234 6 91234 7 91234 8 91234 9 91234 10 91234 11 91234 12 91234 13 91234 14 91234 15 91234 16 91234 17 91234 18 91234 19 91234 20 91234 21 91234 22 91234 23 91234 24 91234 25 91234 26 91234 27 91234 28 91234 29 91234 30 91234 31 91234 32 91234 33 91234 34 91...
result:
ok n: 56713, m: 91234, bishops: 147946
Test #16:
score: 0
Accepted
time: 35ms
memory: 14964kb
input:
99995 99995
output:
199988 1 99995 1 99994 1 99993 1 99992 1 99991 1 99990 1 99989 1 99988 1 99987 1 99986 1 99985 1 99984 1 99983 1 99982 1 99981 1 99980 1 99979 1 99978 1 99977 1 99976 1 99975 1 99974 1 99973 1 99972 1 99971 1 99970 1 99969 1 99968 1 99967 1 99966 1 99965 1 99964 1 99963 1 99962 1 99961 1 99960 1 999...
result:
ok n: 99995, m: 99995, bishops: 199988
Test #17:
score: 0
Accepted
time: 5ms
memory: 11608kb
input:
12345 54321
output:
66665 1 54321 2 54321 3 54321 4 54321 5 54321 6 54321 7 54321 8 54321 9 54321 10 54321 11 54321 12 54321 13 54321 14 54321 15 54321 16 54321 17 54321 18 54321 19 54321 20 54321 21 54321 22 54321 23 54321 24 54321 25 54321 26 54321 27 54321 28 54321 29 54321 30 54321 31 54321 32 54321 33 54321 34 543...
result:
ok n: 12345, m: 54321, bishops: 66665
Test #18:
score: 0
Accepted
time: 24ms
memory: 14636kb
input:
90000 92000
output:
181998 1 92000 2 92000 3 92000 4 92000 5 92000 6 92000 7 92000 8 92000 9 92000 10 92000 11 92000 12 92000 13 92000 14 92000 15 92000 16 92000 17 92000 18 92000 19 92000 20 92000 21 92000 22 92000 23 92000 24 92000 25 92000 26 92000 27 92000 28 92000 29 92000 30 92000 31 92000 32 92000 33 92000 34 92...
result:
ok n: 90000, m: 92000, bishops: 181998
Test #19:
score: 0
Accepted
time: 10ms
memory: 12016kb
input:
10000 70000
output:
79998 1 70000 2 70000 3 70000 4 70000 5 70000 6 70000 7 70000 8 70000 9 70000 10 70000 11 70000 12 70000 13 70000 14 70000 15 70000 16 70000 17 70000 18 70000 19 70000 20 70000 21 70000 22 70000 23 70000 24 70000 25 70000 26 70000 27 70000 28 70000 29 70000 30 70000 31 70000 32 70000 33 70000 34 700...
result:
ok n: 10000, m: 70000, bishops: 79998
Test #20:
score: 0
Accepted
time: 12ms
memory: 12064kb
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: 14ms
memory: 12384kb
input:
10000 80000
output:
89998 1 80000 2 80000 3 80000 4 80000 5 80000 6 80000 7 80000 8 80000 9 80000 10 80000 11 80000 12 80000 13 80000 14 80000 15 80000 16 80000 17 80000 18 80000 19 80000 20 80000 21 80000 22 80000 23 80000 24 80000 25 80000 26 80000 27 80000 28 80000 29 80000 30 80000 31 80000 32 80000 33 80000 34 800...
result:
ok n: 10000, m: 80000, bishops: 89998
Test #22:
score: 0
Accepted
time: 19ms
memory: 12372kb
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: 12400kb
input:
10000 80002
output:
90000 1 80002 2 80002 3 80002 4 80002 5 80002 6 80002 7 80002 8 80002 9 80002 10 80002 11 80002 12 80002 13 80002 14 80002 15 80002 16 80002 17 80002 18 80002 19 80002 20 80002 21 80002 22 80002 23 80002 24 80002 25 80002 26 80002 27 80002 28 80002 29 80002 30 80002 31 80002 32 80002 33 80002 34 800...
result:
ok n: 10000, m: 80002, bishops: 90000
Test #24:
score: 0
Accepted
time: 7ms
memory: 12404kb
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: 14ms
memory: 12420kb
input:
10000 79998
output:
89996 1 79998 2 79998 3 79998 4 79998 5 79998 6 79998 7 79998 8 79998 9 79998 10 79998 11 79998 12 79998 13 79998 14 79998 15 79998 16 79998 17 79998 18 79998 19 79998 20 79998 21 79998 22 79998 23 79998 24 79998 25 79998 26 79998 27 79998 28 79998 29 79998 30 79998 31 79998 32 79998 33 79998 34 799...
result:
ok n: 10000, m: 79998, bishops: 89996
Test #26:
score: 0
Accepted
time: 14ms
memory: 13148kb
input:
11111 100000
output:
111110 1 100000 2 100000 3 100000 4 100000 5 100000 6 100000 7 100000 8 100000 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 100000 29 100000 30 100000 31...
result:
ok n: 11111, m: 100000, bishops: 111110
Test #27:
score: 0
Accepted
time: 1ms
memory: 9136kb
input:
1 1
output:
1 1 1
result:
ok n: 1, m: 1, bishops: 1
Extra Test:
score: 0
Extra Test Passed