QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#281364 | #7178. Bishops | ikaurov# | WA | 0ms | 3888kb | C++20 | 3.1kb | 2023-12-10 03:22:27 | 2023-12-10 03:22:28 |
Judging History
answer
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'
vector<pair<int, int>> stupid_vertical(int n){
vector<pair<int, int>> ret;
for (int i = 1; i <= n; i++) ret.pb({1, i});
return ret;
}
vector<pair<int, int>> stupid_horizontal(int n){
vector<pair<int, int>> ret;
for (int i = 1; i <= n; i++) ret.pb({i, 1});
return ret;
}
vector<pair<int, int>> smart_square(int n){
vector<pair<int, int>> ret;
for (int i = 1; i <= n; i++) ret.pb({i, 1});
for (int i = 2; i < n; i++) ret.pb({i, n});
return ret;
}
vector<pair<int, int>> place(int n, int m){
if (n % 2 == 1 && m == 2 * n){
vector<pair<int, int>> ret;
for (int i = 1; i <= n; i++){
ret.pb({i, 1});
ret.pb({i, m});
if (i % 2 == 0) ret.pb({i, n}), ret.pb({i, n + 1});
}
return ret;
}
if (m % 2 == 1 && n == 2 * m){
vector<pair<int, int>> ret;
for (int i = 1; i <= m; i++){
ret.pb({1, i});
ret.pb({m, i});
if (i % 2 == 0) ret.pb({m, i}), ret.pb({m + 1, i});
}
return ret;
}
if (n == m){
return smart_square(n);
}
else{
if (n > m){
vector<pair<int, int>> ret;
int i = 0;
for (; i + m + (m % 2 == 1 && n % m == 0? m : 0) < n; i += m){
auto cur = stupid_vertical(m);
for (auto [x, y] : cur){
ret.pb({x + i, y});
}
}
vector<pair<int, int>> rem;
if (m % 2 == 1 && n % m == 0){
rem = place(2 * m, m);
}
else if (n % m == 0) rem = smart_square(m);
else rem = place(n % m, m);
for (auto [x, y] : rem) ret.pb({x + i, y});
return ret;
}
else{
vector<pair<int, int>> ret;
int i = 0;
for (; i + n + (n % 2 == 1 && m % n == 0? n : 0) < m; i += n){
auto cur = stupid_horizontal(n);
for (auto [x, y] : cur){
ret.pb({x, y + i});
}
}
vector<pair<int, int>> rem;
if (n % 2 == 1 && m % n == 0){
rem = place(n, 2 * n);
}
else if (m % n == 0) rem = smart_square(n);
else rem = place(n, m % n);
for (auto [x, y] : rem) ret.pb({x, y + i});
return ret;
}
}
}
void check(int n, int m, vector<pair<int, int>> ans){
int need = n + m - 1 - (__gcd(n, m) > 1);
// assert(sz(ans) == need);
for (int i = 0; i < sz(ans); i++){
for (int j = 0; j < i; j++){
int x1 = ans[i].fi, y1 = ans[i].se;
int x2 = ans[j].fi, y2 = ans[j].se;
assert(x1 + y1 != x2 + y2);
assert(x1 - y1 != x2 - y2);
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
// cout.precision(20);
// for (int n = 1; n < 200; n++){
// for (int m = 1; m < 200; m++){
// check(n, m, place(n, m));
// }
// }
int n, m;
cin >> n >> m;
auto ans = place(n, m);
cout << sz(ans) << endl;
for (auto [x, y] : ans) cout << x << " " << y << endl;
// check(n, m, ans);
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3888kb
input:
2 5
output:
6 1 1 2 1 1 3 2 3 1 5 1 5
result:
wrong answer Sum diagonals are not distinct