QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#175523 | #7178. Bishops | SorahISA | AC ✓ | 19ms | 9380kb | C++20 | 2.9kb | 2023-09-10 19:06:44 | 2023-09-10 19:06:45 |
Judging History
answer
#ifndef Yamada
#define Yamada
#include Yamada __FILE__ Yamada
void solve() {
int N, M; cin >> N >> M;
if (N == 1 and M == 1) {
cout << 1 << "\n";
cout << 1 << " " << 1 << "\n";
return;
}
bool flag_swap = false;
if (N == M) --N;
if (N > M) swap(N, M), flag_swap = true;
vector<pii> bishops;
for (int c1 = 1, c2 = M; c1 + N <= c2; c1 += N, c2 -= N) {
for (int r = 1; r <= N; ++r) bishops.eb(r, c1), bishops.eb(r, c2);
if (c1 + 3*N > c2) {
if (c1 + 2*N <= c2) {
c1 += N;
for (int r = 1; r <= N; ++r) bishops.eb(r, c1);
}
if (N % 2 == 1) {
for (int r = (N+1)/2, c = c1+N/2+1; c <= c2-N/2-1; ++c) bishops.eb(r, c);
}
else {
int c = (c1 + c2) / 2, k = N - (c - c1);
for (int r = k+1; r <= N-k; ++r) bishops.eb(r, c);
if (N - 2*k == 1 and c - c1 != c2 - c) bishops.eb(k+1, c+1);
}
}
}
cout << SZ(bishops) << "\n";
for (auto [r, c] : bishops) {
if (flag_swap) cout << c << " " << r << "\n";
else cout << r << " " << c << "\n";
}
// vector<string> board(N, string(M, '.'));
// for (auto [r, c] : bishops) board[r-1][c-1] = 'x';
// for (string &str : board) debug(str);
}
int32_t main() {
fastIO();
int t = 1; // cin >> t;
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}
#else
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
// #define double __float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;
#define X first
#define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())
#ifdef local
#define fastIO() void()
#define debug(...) \
fprintf(stderr, "%sAt [%s], line %d: (%s) = ", "\u001b[33m", __FILE__, __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), fprintf(stderr, "%s", "\u001b[0m")
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}
#endif
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3628kb
input:
2 5
output:
6 1 1 1 5 2 1 2 5 1 3 2 3
result:
ok n: 2, m: 5, bishops: 6
Test #2:
score: 0
Accepted
time: 1ms
memory: 3632kb
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: 7552kb
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: 15ms
memory: 7520kb
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: 17ms
memory: 7704kb
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: 3ms
memory: 5412kb
input:
1 100000
output:
100000 1 1 1 100000 1 2 1 99999 1 3 1 99998 1 4 1 99997 1 5 1 99996 1 6 1 99995 1 7 1 99994 1 8 1 99993 1 9 1 99992 1 10 1 99991 1 11 1 99990 1 12 1 99989 1 13 1 99988 1 14 1 99987 1 15 1 99986 1 16 1 99985 1 17 1 99984 1 18 1 99983 1 19 1 99982 1 20 1 99981 1 21 1 99980 1 22 1 99979 1 23 1 99978 1 ...
result:
ok n: 1, m: 100000, bishops: 100000
Test #7:
score: 0
Accepted
time: 16ms
memory: 8052kb
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: 9ms
memory: 5244kb
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: 13ms
memory: 5232kb
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: 11ms
memory: 5236kb
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 1 14 1 99986 2 14 2 99986 3 14 3 99986 4 14 4 99986 5 14 5 99986 6 14 6 99986 7 14 7 99986 8 14 8 99986 9 14 9 99986 10 14 10 999...
result:
ok n: 13, m: 99999, bishops: 100011
Test #11:
score: 0
Accepted
time: 11ms
memory: 5332kb
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 1 22 1 99978 2 22...
result:
ok n: 21, m: 99999, bishops: 100019
Test #12:
score: 0
Accepted
time: 9ms
memory: 8324kb
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: 10ms
memory: 8588kb
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: 4ms
memory: 5420kb
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: 11ms
memory: 8156kb
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: 9380kb
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: 2ms
memory: 5336kb
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: 10ms
memory: 7524kb
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: 5ms
memory: 5256kb
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: 4ms
memory: 5336kb
input:
10000 70001
output:
80000 1 1 1 70001 2 1 2 70001 3 1 3 70001 4 1 4 70001 5 1 5 70001 6 1 6 70001 7 1 7 70001 8 1 8 70001 9 1 9 70001 10 1 10 70001 11 1 11 70001 12 1 12 70001 13 1 13 70001 14 1 14 70001 15 1 15 70001 16 1 16 70001 17 1 17 70001 18 1 18 70001 19 1 19 70001 20 1 20 70001 21 1 21 70001 22 1 22 70001 23 1...
result:
ok n: 10000, m: 70001, bishops: 80000
Test #21:
score: 0
Accepted
time: 5ms
memory: 5284kb
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: 9ms
memory: 5276kb
input:
10000 80001
output:
90000 1 1 1 80001 2 1 2 80001 3 1 3 80001 4 1 4 80001 5 1 5 80001 6 1 6 80001 7 1 7 80001 8 1 8 80001 9 1 9 80001 10 1 10 80001 11 1 11 80001 12 1 12 80001 13 1 13 80001 14 1 14 80001 15 1 15 80001 16 1 16 80001 17 1 17 80001 18 1 18 80001 19 1 19 80001 20 1 20 80001 21 1 21 80001 22 1 22 80001 23 1...
result:
ok n: 10000, m: 80001, bishops: 90000
Test #23:
score: 0
Accepted
time: 11ms
memory: 5236kb
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: 12ms
memory: 5260kb
input:
10000 79999
output:
89998 1 1 1 79999 2 1 2 79999 3 1 3 79999 4 1 4 79999 5 1 5 79999 6 1 6 79999 7 1 7 79999 8 1 8 79999 9 1 9 79999 10 1 10 79999 11 1 11 79999 12 1 12 79999 13 1 13 79999 14 1 14 79999 15 1 15 79999 16 1 16 79999 17 1 17 79999 18 1 18 79999 19 1 19 79999 20 1 20 79999 21 1 21 79999 22 1 22 79999 23 1...
result:
ok n: 10000, m: 79999, bishops: 89998
Test #25:
score: 0
Accepted
time: 9ms
memory: 5280kb
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: 2ms
memory: 5320kb
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: 3856kb
input:
1 1
output:
1 1 1
result:
ok n: 1, m: 1, bishops: 1
Extra Test:
score: 0
Extra Test Passed