제출 #494067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
494067		Wayne_Yan	Chess Rush (CEOI20_chessrush)	C++17	36 / 100	628 ms	692 KiB

chessrush

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#include "arithmetics.h"

typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
#define debug(x) (cerr << (#x) << " = " << x << "\n")
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))

template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

int R,C,Q;
int st, ed;
void PP(){
  if(st == ed) printf("%d 1\n", R-1);
  else printf("0 0\n");
}

void RR(){
  if(st == ed) printf("1 1");
  else printf("2 2");
  printf("\n");
}

void QQ(){
  if(st == ed){ printf("1 1\n"); return;}
  if( R == C ){
    if( abs(st-ed) == R-1){
      printf("1 1\n"); return;
    }
  }
  int ans = 0;
  ans ++; // first horizontal
  ans += 2; // first vertical
  ans ++; // first diagonal, then vertical;
  if((st+1+ed+R) % 2 == 0){ // (st, 1) & (ed, R)
    // up-right
    int k = (R-1+ed-st)>>1;
    if(st+k <= C) ans++;

    // up-left
    k = (R-1-ed+st)>>1;
    if(st-k > 0) ans++; 
  }
  if(R == C){
    if(st == 1 || st == R || ed == 1 || ed == R) ans++;
  }
  printf("2 %d\n", ans);

}

struct mat{
  int arr[100][100];
  mat operator * (mat b){
    mat ans;
    F(100){
      Fi(j, 100){
        Fi(k, 100){
          ans.arr[i][j] = Add(ans.arr[i][j], Mul(arr[i][k], b.arr[k][j]));
        }
      }
    }
    return ans;
  }
  mat (){F(100) fill(arr[i], arr[i]+100, 0);}
};

void KK(mat& answer){
  st--;
  ed--;
  printf("%d %d\n", R-1, answer.arr[st][ed]);
}

void BB(){
  if((st+1+ed+R) & 1){
    printf("0 0\n");
    return;
  }
  

}

signed main(){
  
  cin >> R >> C >> Q;

  
  mat trans;
  mat answer;
  
  if(C <= 100){
  F(C){
    Fi(j, C){
      if(abs(i-j) <= 1){
        trans.arr[i][j] = 1;
      }
      if(i == j) answer.arr[i][j] = 1;
    }
  }
  }
  int e = R-1;
  while(e){
    if(e & 1) answer = answer * trans;
    trans = trans * trans;
    e >>= 1;
  }
  
  

  while(Q--){
    char c;
    cin >> c;
    cin >> st >> ed;
    switch(c){
      case 'P':
        PP();
        break;
      case 'Q':
        QQ();
        break;
      case 'R':
        RR();
        break;
      case 'B':
        BB();
        break;
      case 'K':
        KK(answer);
        break;
      default:
        assert(0);
        break;
    }
  }
  return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 8 / 8
• Subtask 3: 0 / 15
• Subtask 4: 0 / 22
• Subtask 5: 5 / 5
• Subtask 6: 8 / 8
• Subtask 7: 15 / 15
• Subtask 8: 0 / 20
• Subtask 9: 0 / 7