QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#199782#7178. BishopskiwiHM#WA 0ms3460kbC++202.8kb2023-10-04 14:02:192023-10-04 14:02:19

Judging History

你现在查看的是最新测评结果

  • [2023-10-04 14:02:19]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3460kb
  • [2023-10-04 14:02:19]
  • 提交

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)