oj.uz

답안 #416953

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
416953 2021-06-03T08:20:31 Z ACmachine Chess Rush (CEOI20_chessrush) C++17
0 / 100
 2000 ms 49136 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 = 1020;
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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2050 ms 49100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2070 ms 49136 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2067 ms 49100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2067 ms 49100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2065 ms 49088 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2065 ms 49088 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2065 ms 49088 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2065 ms 49088 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2050 ms 49100 KB Time limit exceeded
2 Halted 0 ms 0 KB -