QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#173750 | #7178. Bishops | ucup-team197# | WA | 16ms | 5340kb | C++20 | 2.4kb | 2023-09-10 01:37:03 | 2023-09-10 01:37:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()
vector<pair<int, int>> solve(int n, int m){
vector<pair<int, int>> v;
while(m >= 2 * n){
for(int i = 1; i <= n; ++i){
v.push_back({i, m});
}
m -= n;
}
if(m == n){
for(int i = 1; i <= n; ++i)
v.push_back({i, 1});
for(int i = 2; i <= n - 1; ++i)
v.push_back({i, n});
}
else{
for(int i = 1; i <= n; ++i)
v.push_back({i, 1});
for(int i = 1; i <= n; ++i)
v.push_back({i, m});
if(n % 2 == 0){
int mid = (1 + m) / 2;
for(int i = 1; i <= n; ++i){
int diff = m - mid;
int diff2 = mid - 1;
diff = min(diff, diff2);
// cout << diff << " diff " << n - diff << " " << i << " " << 1 + diff << endl;
if(i > n - diff && i < 1 + diff){
v.push_back({i, mid});
}
}
}
else{
int mid = (1 + n) / 2;
for(int i = 1; i <= m; ++i){
int diff = n - mid;
if(i > 1 + diff && i < m - diff){
v.push_back({mid, i});
}
}
}
}
return v;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
vector<pair<int, int>> v;
if(n < m){
v = solve(n, m);
}
else{
v = solve(m, n);
for(auto &[x, y]: v)
swap(x, y);
}
/*for(auto [x, y]: v){
assert(1 <= x && x <= n);
assert(1 <= y && y <= m);
}
for(int i = 0; i < v.size(); ++i){
auto [x, y] = v[i];
for(int j = i + 1; j < v.size(); ++j){
auto [x2, y2] = v[j];
int sum_1 = x + y;
int sum_2 = x2 + y2;
assert(sum_1 != sum_2);
int diff_1 = x - y;
int diff_2 = x2 - y2;
assert(diff_1 != diff_2);
}
}*/
cout << v.size() << "\n";
for(auto [x, y]: v)
cout << x << " " << y << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3800kb
input:
2 5
output:
6 1 5 2 5 1 1 2 1 1 3 2 3
result:
ok n: 2, m: 5, bishops: 6
Test #2:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
5 5
output:
8 1 1 1 2 1 3 1 4 1 5 5 2 5 3 5 4
result:
ok n: 5, m: 5, bishops: 8
Test #3:
score: 0
Accepted
time: 15ms
memory: 5188kb
input:
100000 100000
output:
199998 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: 100000, bishops: 199998
Test #4:
score: 0
Accepted
time: 16ms
memory: 5340kb
input:
100000 99999
output:
199998 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: 99999, bishops: 199998
Test #5:
score: 0
Accepted
time: 12ms
memory: 5164kb
input:
100000 50000
output:
149998 100000 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 10...
result:
ok n: 100000, m: 50000, bishops: 149998
Test #6:
score: 0
Accepted
time: 7ms
memory: 4172kb
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: 16ms
memory: 5280kb
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: 6ms
memory: 4076kb
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: 3ms
memory: 4144kb
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: 7ms
memory: 4308kb
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 1 99986 2 99986 3 99986 4 99986 5 99986 6 99986 7 99986 8 99986 9 99986 10 99986 11 99986 12 99986 13 99986 1 99973 2 99973 3 99973 4 99973 5 99973 6 99973 7 99973 8 99973 9 99973 10 99...
result:
ok n: 13, m: 99999, bishops: 100011
Test #11:
score: 0
Accepted
time: 10ms
memory: 4124kb
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 1 99978 2 99978 3 99978 4 99978 5 99978 6 99978 7 99978 8 99978 9 99978 10 99978 11 99978 12 99978 13 99978 14 99...
result:
ok n: 21, m: 99999, bishops: 100019
Test #12:
score: 0
Accepted
time: 13ms
memory: 5196kb
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: -100
Wrong Answer
time: 15ms
memory: 5196kb
input:
33333 99999
output:
133330 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:
wrong answer Participant's answer is not optimal (133330 < 133331)