oj.uz

Submission #416951

# Submission time Handle Problem Language Result Execution time Memory
416951 2021-06-03T08:19:35 Z ACmachine Chess Rush (CEOI20_chessrush) C++17
28 / 100
 797 ms 776 KB 
#include "arithmetics.h"
#include <bits/stdc++.h>

using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i,j , k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
typedef long long ll;
const int mx = 102;
const int mod = (int)1e9 + 7;
struct matrix{
    ll mat[mx][mx];
    matrix(){
        REP(i, mx){
            fill(mat[i], mat[i] + mx, 0);
        }
    }
    matrix(vector<vector<int>> &a){
        REP(i, mx){
            fill(mat[i], mat[i] + mx, 0);
        }
        REP(i, a.size()){
            REP(j, a[i].size()){
                mat[i][j] = a[i][j];
            }
        }
    }
};
matrix multiply(matrix a, matrix b){
    matrix res;
    REP(i, mx){
        REP(j, mx){
            REP(k, mx){
                res.mat[i][k] = Add(res.mat[i][k], Mul(a.mat[i][j], b.mat[j][k]));
                //res.mat[i][k] += (a.mat[i][j] * b.mat[j][k]);
                //res.mat[i][k] %= mod;
            }
        }
    }
    return res;
};
matrix binpow(matrix a, int p){
    matrix res;
    REP(i, mx){
        res.mat[i][i] = 1;
    }
    while(p > 0){
        if(p & 1){
            res = multiply(res, a);
        }
        a = multiply(a, a);
        p >>= 1;
    }
    return res;
}
int main(){
    int r, c, q;
    cin >> r >> c >> q;
    auto solve_pawn = [&](int c1, int cr)->array<int,2>{
        if(c1 != cr) 
            return {0, 0};
        else{
            return {r - 1, 1};
        }
    };
    auto solve_queen = [&](int c1, int cr)->array<int,2>{
        if(c1 == cr){
            return {1, 1};
        }
        else if(abs(c1 - cr) == r - 1){
            return {1, 1};
        }
        else{
            array<int, 2> res = {2, 4};
            int f = r - 1 + cr - c1; int xf = f / 2;
            if(f % 2 == 0 && c1 + xf <= c && r - 1 - xf >= 0)
                res[1]++;
            int s = r - 1 + c1 - cr; int xs = s / 2;
            if(s % 2 == 0 && c1 - xs >= 1 && r - 1 - xs >= 0)
                res[1]++;
            if(r == c && (c1 == 1 || c1 == c)) 
                res[1]++;
            if(r == c && (cr == 1 || cr == c))
                res[1]++; 
            return res;
        }
    };
    auto solve_rook = [&](int c1, int cr)->array<int,2>{
        if(c1 == cr){
            return {1, 1};
        }
        else{
            return {2, 2};
        }
    };
    matrix king;
    FOR(i, 1, c + 1, 1){
        if(i != c)
            king.mat[i][i + 1] = 1;
        king.mat[i][i] = 1;
        if(i != 1)
            king.mat[i][i - 1] = 1;
    }
    matrix kingpow = binpow(king, r - 1);
    auto solve_king = [&](int c1, int cr)->array<int, 2>{
        return {r - 1, kingpow.mat[c1][cr]};
    };
    REP(i, q){
        char t;
        int c1, cr;
        cin >> t >> c1 >> cr;
        array<int, 2> res;
        if(t == 'P')
            res = solve_pawn(c1, cr);
        else if(t == 'Q')
            res = solve_queen(c1, cr);
        else if(t == 'R')
            res = solve_rook(c1, cr);
        else if(t == 'K')
            res = solve_king(c1, cr);
        cout << res[0] << " " << res[1] << "\n";
    }
    return 0;
}

Compilation message

chessrush.cpp: In constructor 'matrix::matrix(std::vector<std::vector<int> >&)':
chessrush.cpp:5:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
chessrush.cpp:7:19: note: in expansion of macro 'FOR'
    7 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
chessrush.cpp:23:9: note: in expansion of macro 'REP'
   23 |         REP(i, a.size()){
      |         ^~~
chessrush.cpp:5:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
      |                                            ^
chessrush.cpp:7:19: note: in expansion of macro 'FOR'
    7 | #define REP(i, n) FOR(i, 0, n, 1)
      |                   ^~~
chessrush.cpp:24:13: note: in expansion of macro 'REP'
   24 |             REP(j, a[i].size()){
      |             ^~~
chessrush.cpp: In lambda function:
chessrush.cpp:107:42: warning: narrowing conversion of 'kingpow.matrix::mat[c1][cr]' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
  107 |         return {r - 1, kingpow.mat[c1][cr]};
      |                        ~~~~~~~~~~~~~~~~~~^

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 756 KB Output is correct
2 Correct 462 ms 756 KB Output is correct
3 Correct 55 ms 760 KB Output is correct
4 Runtime error 1 ms 716 KB Execution killed with signal 11

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 752 KB Output is correct
2 Correct 153 ms 752 KB Output is correct
3 Correct 136 ms 752 KB Output is correct
4 Correct 148 ms 716 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 752 KB Output is correct
2 Correct 153 ms 752 KB Output is correct
3 Correct 136 ms 752 KB Output is correct
4 Correct 148 ms 716 KB Output is correct
5 Correct 153 ms 772 KB Output is correct
6 Correct 125 ms 716 KB Output is correct
7 Correct 138 ms 768 KB Output is correct
8 Correct 159 ms 776 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 752 KB Output is correct
2 Correct 153 ms 752 KB Output is correct
3 Correct 136 ms 752 KB Output is correct
4 Correct 148 ms 716 KB Output is correct
5 Correct 153 ms 772 KB Output is correct
6 Correct 125 ms 716 KB Output is correct
7 Correct 138 ms 768 KB Output is correct
8 Correct 159 ms 776 KB Output is correct
9 Correct 431 ms 756 KB Output is correct
10 Correct 797 ms 764 KB Output is correct
11 Correct 789 ms 760 KB Output is correct
12 Correct 684 ms 772 KB Output is correct
13 Correct 583 ms 756 KB Output is correct
14 Correct 626 ms 760 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 752 KB Output is correct
2 Correct 153 ms 752 KB Output is correct
3 Correct 136 ms 752 KB Output is correct
4 Correct 148 ms 716 KB Output is correct
5 Correct 153 ms 772 KB Output is correct
6 Correct 125 ms 716 KB Output is correct
7 Correct 138 ms 768 KB Output is correct
8 Correct 159 ms 776 KB Output is correct
9 Correct 431 ms 756 KB Output is correct
10 Correct 797 ms 764 KB Output is correct
11 Correct 789 ms 760 KB Output is correct
12 Correct 684 ms 772 KB Output is correct
13 Correct 583 ms 756 KB Output is correct
14 Correct 626 ms 760 KB Output is correct
15 Correct 630 ms 756 KB Output is correct
16 Correct 679 ms 764 KB Output is correct
17 Runtime error 1 ms 716 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 752 KB Output isn't correct
2 Halted 0 ms 0 KB -