oj.uz

Submission #552843

# Submission time Handle Problem Language Result Execution time Memory
552843 2022-04-24T07:05:00 Z Stickfish Chess Rush (CEOI20_chessrush) C++17
51 / 100
 724 ms 27316 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 = 1124;
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 = min(0, r / c / 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;
        }
        for (int rml = 0; rml <= lst && rm0 + rml <= rmv; ++rml) {
            //if (!balls_borders[minmoves - 4 - choose_n0][rmv - rm0 - rml]) {
                //cout << minmoves - 4 << ' ' << choose_n0 << endl;
            //}
            cnt = Add(cnt, balls_borders[minmoves - 4 - choose_n0][rmv - rm0 - rml]);
        }
    }
    //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() {
    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 - c - 4);
    for (int nadd = 0; nadd <= c * 2 + 100; ++nadd) {
        int n = choose_n0 + nadd;
        choose[nadd][0] = 1;
        for (int k = 1; k <= c * 2 + 100 && 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 + 50; ++t) {
        for (int p = 0; p < c + 50; ++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 1 ms 980 KB Output is correct
2 Incorrect 72 ms 20360 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 1 ms 948 KB Output is correct
2 Correct 4 ms 1236 KB Output is correct
3 Correct 1 ms 948 KB Output is correct
4 Correct 7 ms 8148 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 31 ms 24384 KB Output is correct
6 Correct 200 ms 12860 KB Output is correct
7 Runtime error 19 ms 3308 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 121 ms 3068 KB Output is correct
3 Correct 88 ms 2632 KB Output is correct
4 Correct 1 ms 980 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 121 ms 3068 KB Output is correct
3 Correct 88 ms 2632 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 7 ms 1460 KB Output is correct
6 Correct 6 ms 1364 KB Output is correct
7 Correct 85 ms 2636 KB Output is correct
8 Correct 123 ms 2984 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 121 ms 3068 KB Output is correct
3 Correct 88 ms 2632 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 7 ms 1460 KB Output is correct
6 Correct 6 ms 1364 KB Output is correct
7 Correct 85 ms 2636 KB Output is correct
8 Correct 123 ms 2984 KB Output is correct
9 Correct 15 ms 1664 KB Output is correct
10 Correct 25 ms 1776 KB Output is correct
11 Correct 724 ms 6236 KB Output is correct
12 Correct 681 ms 5924 KB Output is correct
13 Correct 20 ms 1748 KB Output is correct
14 Correct 1 ms 1004 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 121 ms 3068 KB Output is correct
3 Correct 88 ms 2632 KB Output is correct
4 Correct 1 ms 980 KB Output is correct
5 Correct 7 ms 1460 KB Output is correct
6 Correct 6 ms 1364 KB Output is correct
7 Correct 85 ms 2636 KB Output is correct
8 Correct 123 ms 2984 KB Output is correct
9 Correct 15 ms 1664 KB Output is correct
10 Correct 25 ms 1776 KB Output is correct
11 Correct 724 ms 6236 KB Output is correct
12 Correct 681 ms 5924 KB Output is correct
13 Correct 20 ms 1748 KB Output is correct
14 Correct 1 ms 1004 KB Output is correct
15 Correct 24 ms 1784 KB Output is correct
16 Correct 25 ms 1720 KB Output is correct
17 Incorrect 41 ms 27316 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Incorrect 72 ms 20360 KB Output isn't correct
3 Halted 0 ms 0 KB -