oj.uz

Submission #552850

# Submission time Handle Problem Language Result Execution time Memory
552850 2022-04-24T07:24:36 Z Stickfish Chess Rush (CEOI20_chessrush) C++17
73 / 100
 733 ms 49008 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 < sz; ++i) {
            for (int j = 0; j < sz; ++j) {
                for (int t = 0; t < sz; ++t) {
                    ans[i][j] = Add(ans[i][j], Mul(m[t][j], f[i][t]));
                }
            }
        }
        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

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9428 KB Output is correct
2 Incorrect 68 ms 36080 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9428 KB Output is correct
2 Correct 16 ms 11732 KB Output is correct
3 Correct 10 ms 9300 KB Output is correct
4 Correct 31 ms 19840 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9300 KB Output is correct
2 Correct 10 ms 9428 KB Output is correct
3 Correct 10 ms 9364 KB Output is correct
4 Correct 10 ms 9600 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9300 KB Output is correct
2 Correct 10 ms 9428 KB Output is correct
3 Correct 10 ms 9364 KB Output is correct
4 Correct 10 ms 9600 KB Output is correct
5 Correct 73 ms 40900 KB Output is correct
6 Correct 51 ms 30236 KB Output is correct
7 Correct 31 ms 12364 KB Output is correct
8 Correct 102 ms 49008 KB Output is correct
9 Correct 14 ms 11372 KB Output is correct
10 Correct 431 ms 16368 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9940 KB Output is correct
2 Correct 136 ms 12160 KB Output is correct
3 Correct 88 ms 11756 KB Output is correct
4 Correct 10 ms 9428 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9940 KB Output is correct
2 Correct 136 ms 12160 KB Output is correct
3 Correct 88 ms 11756 KB Output is correct
4 Correct 10 ms 9428 KB Output is correct
5 Correct 16 ms 9984 KB Output is correct
6 Correct 15 ms 10016 KB Output is correct
7 Correct 90 ms 11828 KB Output is correct
8 Correct 131 ms 12144 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9940 KB Output is correct
2 Correct 136 ms 12160 KB Output is correct
3 Correct 88 ms 11756 KB Output is correct
4 Correct 10 ms 9428 KB Output is correct
5 Correct 16 ms 9984 KB Output is correct
6 Correct 15 ms 10016 KB Output is correct
7 Correct 90 ms 11828 KB Output is correct
8 Correct 131 ms 12144 KB Output is correct
9 Correct 27 ms 12372 KB Output is correct
10 Correct 38 ms 12540 KB Output is correct
11 Correct 733 ms 17916 KB Output is correct
12 Correct 655 ms 17708 KB Output is correct
13 Correct 36 ms 12492 KB Output is correct
14 Correct 14 ms 11220 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9940 KB Output is correct
2 Correct 136 ms 12160 KB Output is correct
3 Correct 88 ms 11756 KB Output is correct
4 Correct 10 ms 9428 KB Output is correct
5 Correct 16 ms 9984 KB Output is correct
6 Correct 15 ms 10016 KB Output is correct
7 Correct 90 ms 11828 KB Output is correct
8 Correct 131 ms 12144 KB Output is correct
9 Correct 27 ms 12372 KB Output is correct
10 Correct 38 ms 12540 KB Output is correct
11 Correct 733 ms 17916 KB Output is correct
12 Correct 655 ms 17708 KB Output is correct
13 Correct 36 ms 12492 KB Output is correct
14 Correct 14 ms 11220 KB Output is correct
15 Correct 34 ms 12472 KB Output is correct
16 Correct 34 ms 12528 KB Output is correct
17 Incorrect 102 ms 48904 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9428 KB Output is correct
2 Incorrect 68 ms 36080 KB Output isn't correct
3 Halted 0 ms 0 KB -