oj.uz

Submission #552839

# Submission time Handle Problem Language Result Execution time Memory
552839 2022-04-24T06:58:43 Z Stickfish Chess Rush (CEOI20_chessrush) C++17
36 / 100
 696 ms 24312 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 = 1024;
int choose[MAXC * 2][MAXC * 2];
int balls_borders[MAXC][MAXC];
int balls_borders_sm[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) {
            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 * 2 - 4);
    for (int nadd = 0; nadd <= c * 2 + 10; ++nadd) {
        int n = choose_n0 + nadd;
        choose[nadd][0] = 1;
        for (int k = 1; k <= c * 2 + 10 && 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 + 5; ++t) {
        for (int p = 0; p < c + 5; ++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:144:13: warning: unused variable 'Cvl' [-Wunused-variable]
  144 |         int Cvl = 0;
      |             ^~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Incorrect 75 ms 16408 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 436 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 8 ms 6484 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 22.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 120 ms 2272 KB Output is correct
3 Correct 81 ms 1992 KB Output is correct
4 Correct 1 ms 468 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 120 ms 2272 KB Output is correct
3 Correct 81 ms 1992 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 7 ms 852 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 82 ms 1952 KB Output is correct
8 Correct 129 ms 2304 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 120 ms 2272 KB Output is correct
3 Correct 81 ms 1992 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 7 ms 852 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 82 ms 1952 KB Output is correct
8 Correct 129 ms 2304 KB Output is correct
9 Correct 13 ms 980 KB Output is correct
10 Correct 24 ms 1136 KB Output is correct
11 Correct 696 ms 5232 KB Output is correct
12 Correct 615 ms 5196 KB Output is correct
13 Correct 18 ms 1108 KB Output is correct
14 Correct 1 ms 340 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 724 KB Output is correct
2 Correct 120 ms 2272 KB Output is correct
3 Correct 81 ms 1992 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 7 ms 852 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 82 ms 1952 KB Output is correct
8 Correct 129 ms 2304 KB Output is correct
9 Correct 13 ms 980 KB Output is correct
10 Correct 24 ms 1136 KB Output is correct
11 Correct 696 ms 5232 KB Output is correct
12 Correct 615 ms 5196 KB Output is correct
13 Correct 18 ms 1108 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 20 ms 1124 KB Output is correct
16 Correct 19 ms 1156 KB Output is correct
17 Incorrect 46 ms 24312 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 468 KB Output is correct
2 Incorrect 75 ms 16408 KB Output isn't correct
3 Halted 0 ms 0 KB -