QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#199782 | #7178. Bishops | kiwiHM# | WA | 0ms | 3460kb | C++20 | 2.8kb | 2023-10-04 14:02:19 | 2023-10-04 14:02:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct node{
int x, y;
};
vector <node> vec0, vec1, ans;
struct interval{
int l, r, v;
};
vector <interval> itv0, itv1;
int n, m;
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
if ((i + 1) % 2 == 0)
vec0.push_back((node) {i, 1});
else vec1.push_back((node) {i, 1});
}
for (int i = 2; i <= m; i++){
if ((n + i) % 2 == 0)
vec0.push_back((node) {n, i});
else vec1.push_back((node) {n, i});
}
for (auto lft : vec0){
node rgt = (node) {1, lft.x + lft.y - 1};
if (rgt.y > m){
int c = rgt.y - m;
rgt.x += c; rgt.y -= c;
}
int l = lft.x - lft.y, r = rgt.x - rgt.y;
if (l > r) swap(l, r);
itv0.push_back((interval) {l, r, lft.x + lft.y});
}
for (auto lft : vec1){
node rgt = (node) {1, lft.x + lft.y - 1};
if (rgt.y > m){
int c = rgt.y - m;
rgt.x += c; rgt.y -= c;
}
int l = lft.x - lft.y, r = rgt.x - rgt.y;
if (l > r) swap(l, r);
itv1.push_back((interval) {l, r, lft.x + lft.y});
}
sort(itv0.begin(), itv0.end(), [&](interval p, interval q){
return p.r < q.r;
});
int pos = 0, si = itv0.size();
multiset < pair<int,int> > lftp;
int st = (m - 1) % 2 == 0 ? m - 1 : m - 2;
for (int i = st; i >= 1 - n; i -= 2){
while (pos < si && itv0[pos].r >= i)
lftp.insert(make_pair(itv0[pos].l, itv0[pos].v)), pos++;
while (lftp.size() && (*(--lftp.end())).first > i)
lftp.erase(--lftp.end());
if (lftp.size() && (*(--lftp.end())).first <= i){
int del = (*(--lftp.end())).first;
int sum = (*(--lftp.end())).second;
int x = (sum + del) / 2;
int y = sum - x;
lftp.erase(make_pair(del, sum));
ans.push_back((node) {x, y});
}
}
pos = 0, si = itv1.size();
lftp.clear();
st = (m - 1) % 2 == 1 ? m - 1 : m - 2;
for (int i = st; i >= 1 - n; i -= 2){
while (pos < si && itv1[pos].r >= i)
lftp.insert(make_pair(itv1[pos].l, itv1[pos].v)), pos++;
while (lftp.size() && (*(--lftp.end())).first > i)
lftp.erase(--lftp.end());
if (lftp.size() && (*(--lftp.end())).first <= i){
int del = (*(--lftp.end())).first;
int sum = (*(--lftp.end())).second;
int x = (sum + del) / 2;
int y = sum - x;
lftp.erase(make_pair(del, sum));
ans.push_back((node) {x, y});
}
}
cout << ans.size() << endl;
for (auto item : ans){
cout << item.x << ' ' << item.y << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3460kb
input:
2 5
output:
2 1 2 1 4
result:
wrong answer Participant's answer is not optimal (2 < 6)