QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232688#7178. BishopsikefumyRE 0ms0kbC++204.3kb2023-10-30 19:39:342023-10-30 19:39:34

Judging History

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

  • [2023-10-30 19:39:34]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-10-30 19:39:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define int128 __int128_t
#define pii128 pair<int128,int128>
const int inf = 1 << 30;
const ll linf = 1e18;
const ll mod = 1e9 + 7;
const db EPS = 1e-10;
const db pi = acos(-1);
template<class T> bool chmin(T& x, T y){
    if(x > y) {
        x = y;
        return true;
    } else return false;
}
template<class T> bool chmax(T& x, T y){
    if(x < y) {
        x = y;
        return true;
    } else return false;
}

// overload macro
#define CAT( A, B ) A ## B
#define SELECT( NAME, NUM ) CAT( NAME, NUM )

#define GET_COUNT( _1, _2, _3, _4, _5, _6 /* ad nauseam */, COUNT, ... ) COUNT
#define VA_SIZE( ... ) GET_COUNT( __VA_ARGS__, 6, 5, 4, 3, 2, 1 )

#define VA_SELECT( NAME, ... ) SELECT( NAME, VA_SIZE(__VA_ARGS__) )(__VA_ARGS__)

// rep(overload)
#define rep( ... ) VA_SELECT(rep, __VA_ARGS__)
#define rep2(i, n) for (int i = 0; i < int(n); i++)
#define rep3(i, a, b) for (int i = a; i < int(b); i++)
#define rep4(i, a, b, c) for (int i = a; i < int(b); i += c)

// repll(overload)
#define repll( ... ) VA_SELECT(repll, __VA_ARGS__)
#define repll2(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repll3(i, a, b) for (ll i = a; i < (ll)(b); i++)
#define repll4(i, a, b, c) for (ll i = a; i < (ll)(b); i += c)

// rrep(overload)
#define rrep( ... ) VA_SELECT(rrep, __VA_ARGS__)    
#define rrep2(i, n) for (int i = n - 1; i >= 0; i--)
#define rrep3(i, a, b) for (int i = b - 1; i >= a; i--)
#define rrep4(i, a, b, c) for (int i = b - 1; i >= a; i -= c)

// rrepll(overload)
#define rrepll( ... ) VA_SELECT(rrepll, __VA_ARGS__)
#define rrepll2(i, n) for (ll i = (ll)(n) - 1; i >= 0ll; i--)
#define rrepll3(i, a, b) for (ll i = b - 1; i >= (ll)(a); i--)
#define rrepll4(i, a, b, c) for (ll i = b - 1; i >= (ll)(a); i -= c)

// for_earh
#define fore(e, v) for (auto&& e : v)

// vector
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

int n, m;
pii upper_right(pii p) {
    auto [x, y] = p;
    int d = min(x, m - 1 - y);
    return {x - d, y + d};
}

pii lower_right(pii p) {
    auto [x, y] = p;
    int d = min(n - 1 - x, m - 1 - y);
    return {x + d, y + d};
}

// 左側からのidx
int get_idx(pii p) {
    auto [x, y] = p;
    if (x == n - 1) return n - 1 + m - 1 - y;
    else return x;
}

pii get_point(int i1, int i2) {
    int x, y;
    if (i1 < n) x = i1, y = 0;
    else x = n - 1, y = i1 - n + 1;

    int mx = get_idx(lower_right({x, y}));
    int d = (mx - i2) / 2;

    return {x - d, y + d};
}
// 番号 区間
vector<pii> get_matching(vector<pair<int, pii>> elem) {
    // 番号 終端
    vector<vector<pii>> query(n + m - 1);
    int parity = 0;
    fore (e, elem) {
        auto [idx, p] = e;
        auto [l, r] = p;
        query[l].push_back({r, idx});
        parity = l % 2;
    }

    vector<pii> ret;
    int nw = parity;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    rep (i, nw, n + m, 2) {
        fore (u, query[i]) pq.push(u);
        while (!pq.empty()) {
            auto [r, idx] = pq.top();
            if (r < i) pq.pop();
            else break;
        }
        
        if (!pq.empty()) {
            ret.push_back({pq.top().second, i});
            pq.pop();
        }
    }

    return ret;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cin >> n >> m;
    int dx = 1, dy = 0, x = 0, y = 0;

    vector<pair<int, pii>> edges[2];
    rep (_, n + m - 1) {
        if (x == n - 1) dx = 0, dy = 1;
        auto [x1, y1] = lower_right(upper_right({x, y}));
        auto [x2, y2] = lower_right({x, y});
        edges[(x + y) % 2].push_back({x + y, {get_idx(lower_right(upper_right({x, y}))), get_idx(lower_right({x, y}))}});
        x += dx, y += dy;
    }

    vector<pii> ans;
    rep (i, 2) {
        auto v = get_matching(edges[i]);
        ans.insert(ans.end(), all(v));
    }

    cout << ans.size() << endl;
    fore (u, ans) {
        auto [x, y] = get_point(u.first, u.second);
        cout << x + 1 << ' ' << y + 1 << endl;
    }
}

详细

Test #1:

score: 0
Runtime Error

input:

2 5

output:


result: