oj.uz

답안 #553682

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
553682 2022-04-26T15:14:55 Z Stickfish Chess Rush (CEOI20_chessrush) C++17
73 / 100
 329 ms 49036 KB 
#include <iostream>
#include "arithmetics.h"
#include <vector>
#include <cassert>
using namespace std;
using ll = long long;

pair<int, int> pawn(int r, int c, int j0, int j1) {
    if (j0 == j1)
        return {r - 1, 1};
    else
        return {0, 0};
}

pair<int, int> rook(int r, int c, int j0, int j1) {
    if (j0 == j1)
        return {1, 1};
    else
        return {2, 2};
}

struct point {
    ll x, y;

    point(){}

    point(ll x_, ll y_): x(x_), y(y_) {}

    point operator/(ll t) const {
        return {x / t, y / t};
    }

    point operator*(ll t) const {
        return {x * t, y * t};
    }

    bool operator==(point pt) const {
        return x == pt.x && y == pt.y;
    }

    bool operator!=(point pt) const {
        return x != pt.x || y != pt.y;
    }

    ll operator*(point pt) const {
        return x * pt.y - y * pt.x;
    }

    ll operator^(point pt) const {
        return x * pt.x + y * pt.y;
    }

    point operator+(point pt) const {
        return {x + pt.x, y + pt.y};
    }

    point operator-(point pt) const {
        return {x - pt.x, y - pt.y};
    }

    point rotate_45_normal() {
        point ans(x - y, x + y);
        if (abs(x + y) == 2 || abs(x - y) == 2)
            return ans / 2;
        else
            return ans;
    }

    point rotate_90() {
        return {-y, x};
    }

};

pair<int, int> queen(int r, int c, int j0, int j1) {
    for (point dir(1, 0); dir != point(-1, 0); dir = dir.rotate_45_normal()) {
        //cout << "! " << dir.x << ' ' << dir.y << endl;
        if (dir * point(j1 - j0, r - 1) == 0)
            return {1, 1};
    }
    int cnt = 2;
    for (point dir(1, 1); dir != point(-1, -1); dir = dir.rotate_90()) {
        // (j0, 0) + dir * k = (j1, y0)
        ll y0 = (j1 - j0) / dir.x * dir.y;
        if (0 <= y0 && y0 < r)
            cnt += 2;
        // (j0, 0) + dir * k = (x1, r - 1)
        ll x1 = j0 + (r - 1) / dir.y * dir.x;
        if (0 <= x1 && x1 < c)
            ++cnt;
        // (x2, 0) + dir * k = (j1, r - 1)
        ll x2 = j1 - (r - 1) / dir.y * dir.x;
        if (0 <= x2 && x2 < c)
            ++cnt;
    }
    if ((j0 + j1 + r) % 2) {
        int jright = 2 * c - j1 - 1;
        if (point(jright - j0, r - 1) * point(1, 1) >= 0)
            ++cnt;
        int jleft = -j1 - 1;
        if (point(-1, 1) * point(jleft - j0, r - 1) >= 0)
            ++cnt;
    }
    return {2, cnt};
}

const int MAXC = 1524;
int choose[MAXC * 2][MAXC * 2];
int balls_borders[MAXC][MAXC];
int choose_n0;

pair<int, int> bishop_goleft(int r, int c, int j0, int j1) {
    if (j0 == c - 1 && j1 == 0 && r == c)
        return {1, 1};
    int loopcnt = max(0, r / (c - 1) / 2 - 3);
    point pt(0, j0 + loopcnt * (c - 1) * 2);
    int minmoves = 1 + loopcnt * 2;
    int rmv = 0;
    int lst = 0;
    while (true) {
        if ((point(j1, r - 1) - pt) * point(1, 1) >= 0) {
            ++minmoves;
            lst = r - 1 - pt.y;
            pt = pt + point(lst, lst);
            rmv = abs(j1 - pt.x) / 2;
            break;
        }
        minmoves += 2;
        pt = pt + point(c - 1, c - 1);
        if (point(-1, 1) * (point(j1, r - 1) - pt) >= 0) {
            lst = r - 1 - pt.y;
            pt = pt + point(-lst, lst);
            rmv = abs(j1 - pt.x) / 2;
            break;
        }
        pt = pt + point(1 - c, c - 1);
    }
    lst = c - 1 - lst;
    int cnt = 0;
    if (minmoves == 2)
        return {2, 1};
    for (int rm0 = 0; rm0 <= j0 && rm0 <= rmv; ++rm0) {
        int Cvl = 0;
        if (minmoves == 3) {
            if (lst + rm0 >= rmv)
                ++cnt;
            continue;
        }
        cnt = Add(cnt, balls_borders[minmoves - 4 - choose_n0][rmv - rm0]);
        if (lst + rm0 < rmv) {
            cnt = Sub(cnt, balls_borders[minmoves - 4 - choose_n0][rmv - rm0 - lst - 1]);
        }
    }
    //cout << "---" << ' ' << minmoves << endl;
    return {minmoves, cnt};
}

pair<int, int> bishop(int r, int c, int j0, int j1) {
    if ((r + j0 + j1) % 2 == 0)
        return {0, 0};
    pair<int, int> ansup = bishop_goleft(r, c, j0, j1);
    pair<int, int> ansdown = bishop_goleft(r, c, c - j0 - 1, c - j1 - 1);
    if (ansup.first == ansdown.first)
        return {ansup.first, Add(ansup.second, ansdown.second)};
    return min(ansup, ansdown);
}

struct matrix {
    matrix(int sz_): sz(sz_), f(sz_, vector<int>(sz_, 0)) {}

    vector<int>& operator[](int i) {
        return f[i];
    }
    
    matrix operator*(matrix m) {
        matrix ans(sz);
        for (int i = 0; i * 2 - 1 < sz; ++i) {
            for (int t = 0; t < sz; ++t) {
                if (f[i][t] == 0)
                    continue;
                for (int j = 0; j < sz; ++j) {
                    ans[i][j] = Add(ans[i][j], Mul(m[t][j], f[i][t]));
                }
            }
        }
        for (int i = 0; i * 2 - 1 < sz; ++i) {
            for (int j = 0; j < sz; ++j) {
                ans[sz - i - 1][sz - j - 1] = ans[i][j];
            }
        }
        return ans;
    }

    int sz;
    vector<vector<int>> f;
};

matrix pw(matrix a, int m) {
    if (m == 1)
        return a;
    if (m % 2)
        return a * pw(a, m - 1);
    return pw(a * a, m / 2);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int r, c, q;
    cin >> r >> c >> q;
    matrix king_ans(c);
    for (int i = 0; i < c; ++i) {
        king_ans[i][i] = 1;
        if (i)
            king_ans[i][i - 1] = 1;
        if (i + 1 < c)
            king_ans[i][i + 1] = 1;
    }
    if (c <= 100)
        king_ans = pw(king_ans, r - 1);

    choose_n0 = max(0, r / (c - 1) - c - 100);
    for (int nadd = 0; nadd <= c * 2 + 1000; ++nadd) {
        int n = choose_n0 + nadd;
        choose[nadd][0] = 1;
        for (int k = 1; k <= c * 2 + 1000 && k <= n; ++k) {
            if (nadd == 0)
                choose[nadd][k] = Div(Mul(choose[nadd][k - 1], n - k + 1), k);
            else
                choose[nadd][k] = Add(choose[nadd - 1][k], choose[nadd - 1][k - 1]);
        }
    }
    for (int t = 0; t < c + 500; ++t) {
        for (int p = 0; p < c + 500; ++p) {
            balls_borders[t][p] = choose[p + t][p];
            if (p)
                balls_borders[t][p] = Add(balls_borders[t][p], balls_borders[t][p - 1]);
        }
    }
    while (q--) {
        char t;
        int j0, j1;
        cin >> t >> j0 >> j1;
        --j0, --j1;
        pair<int, int> ans;
        if (t == 'P') {
            ans = pawn(r, c, j0, j1);
        } else if (t == 'Q') {
            ans = queen(r, c, j0, j1);
        } else if (t == 'R') {
            ans = rook(r, c, j0, j1);
        } else if (t == 'K') {
            ans = {r - 1, king_ans[j0][j1]};
        } else if (t == 'B') {
            ans = bishop(r, c, j0, j1);
        }
        cout << ans.first << ' ' << ans.second << '\n';
    }
}

Compilation message

chessrush.cpp: In function 'std::pair<int, int> bishop_goleft(int, int, int, int)':
chessrush.cpp:143:13: warning: unused variable 'Cvl' [-Wunused-variable]
  143 |         int Cvl = 0;
      |             ^~~

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9396 KB Output is correct
2 Incorrect 63 ms 36112 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9364 KB Output is correct
2 Correct 16 ms 11716 KB Output is correct
3 Correct 11 ms 9300 KB Output is correct
4 Correct 37 ms 19912 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 9300 KB Output is correct
2 Correct 14 ms 9480 KB Output is correct
3 Correct 11 ms 9428 KB Output is correct
4 Correct 10 ms 9600 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 9300 KB Output is correct
2 Correct 14 ms 9480 KB Output is correct
3 Correct 11 ms 9428 KB Output is correct
4 Correct 10 ms 9600 KB Output is correct
5 Correct 82 ms 40916 KB Output is correct
6 Correct 51 ms 30236 KB Output is correct
7 Correct 22 ms 12408 KB Output is correct
8 Correct 104 ms 49036 KB Output is correct
9 Correct 17 ms 11400 KB Output is correct
10 Correct 180 ms 16400 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9940 KB Output is correct
2 Correct 31 ms 12180 KB Output is correct
3 Correct 22 ms 11776 KB Output is correct
4 Correct 10 ms 9368 KB Output is correct

Subtask #6
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9940 KB Output is correct
2 Correct 31 ms 12180 KB Output is correct
3 Correct 22 ms 11776 KB Output is correct
4 Correct 10 ms 9368 KB Output is correct
5 Correct 13 ms 10068 KB Output is correct
6 Correct 12 ms 9940 KB Output is correct
7 Correct 23 ms 11860 KB Output is correct
8 Correct 27 ms 12232 KB Output is correct

Subtask #7
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9940 KB Output is correct
2 Correct 31 ms 12180 KB Output is correct
3 Correct 22 ms 11776 KB Output is correct
4 Correct 10 ms 9368 KB Output is correct
5 Correct 13 ms 10068 KB Output is correct
6 Correct 12 ms 9940 KB Output is correct
7 Correct 23 ms 11860 KB Output is correct
8 Correct 27 ms 12232 KB Output is correct
9 Correct 19 ms 12372 KB Output is correct
10 Correct 27 ms 12512 KB Output is correct
11 Correct 329 ms 18040 KB Output is correct
12 Correct 310 ms 17824 KB Output is correct
13 Correct 23 ms 12492 KB Output is correct
14 Correct 13 ms 11220 KB Output is correct

Subtask #8
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 9940 KB Output is correct
2 Correct 31 ms 12180 KB Output is correct
3 Correct 22 ms 11776 KB Output is correct
4 Correct 10 ms 9368 KB Output is correct
5 Correct 13 ms 10068 KB Output is correct
6 Correct 12 ms 9940 KB Output is correct
7 Correct 23 ms 11860 KB Output is correct
8 Correct 27 ms 12232 KB Output is correct
9 Correct 19 ms 12372 KB Output is correct
10 Correct 27 ms 12512 KB Output is correct
11 Correct 329 ms 18040 KB Output is correct
12 Correct 310 ms 17824 KB Output is correct
13 Correct 23 ms 12492 KB Output is correct
14 Correct 13 ms 11220 KB Output is correct
15 Correct 22 ms 12488 KB Output is correct
16 Correct 26 ms 12500 KB Output is correct
17 Incorrect 115 ms 48972 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9396 KB Output is correct
2 Incorrect 63 ms 36112 KB Output isn't correct
3 Halted 0 ms 0 KB -