oj.uz

Submission #494066

# Submission time Handle Problem Language Result Execution time Memory
494066 2021-12-14T07:50:01 Z Wayne_Yan Chess Rush (CEOI20_chessrush) C++17
28 / 100
 657 ms 716 KB 
#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;
  
  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.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 428 KB Output is correct
2 Correct 333 ms 448 KB Output is correct
3 Correct 48 ms 428 KB Output is correct
4 Runtime error 1 ms 676 KB Execution killed with signal 11

Subtask #3
0 / 15.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 448 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 124 ms 428 KB Output is correct
2 Correct 124 ms 424 KB Output is correct
3 Correct 114 ms 332 KB Output is correct
4 Correct 116 ms 432 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 428 KB Output is correct
2 Correct 124 ms 424 KB Output is correct
3 Correct 114 ms 332 KB Output is correct
4 Correct 116 ms 432 KB Output is correct
5 Correct 124 ms 448 KB Output is correct
6 Correct 103 ms 428 KB Output is correct
7 Correct 123 ms 448 KB Output is correct
8 Correct 130 ms 444 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 428 KB Output is correct
2 Correct 124 ms 424 KB Output is correct
3 Correct 114 ms 332 KB Output is correct
4 Correct 116 ms 432 KB Output is correct
5 Correct 124 ms 448 KB Output is correct
6 Correct 103 ms 428 KB Output is correct
7 Correct 123 ms 448 KB Output is correct
8 Correct 130 ms 444 KB Output is correct
9 Correct 351 ms 436 KB Output is correct
10 Correct 657 ms 432 KB Output is correct
11 Correct 642 ms 432 KB Output is correct
12 Correct 573 ms 436 KB Output is correct
13 Correct 462 ms 436 KB Output is correct
14 Correct 504 ms 452 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 428 KB Output is correct
2 Correct 124 ms 424 KB Output is correct
3 Correct 114 ms 332 KB Output is correct
4 Correct 116 ms 432 KB Output is correct
5 Correct 124 ms 448 KB Output is correct
6 Correct 103 ms 428 KB Output is correct
7 Correct 123 ms 448 KB Output is correct
8 Correct 130 ms 444 KB Output is correct
9 Correct 351 ms 436 KB Output is correct
10 Correct 657 ms 432 KB Output is correct
11 Correct 642 ms 432 KB Output is correct
12 Correct 573 ms 436 KB Output is correct
13 Correct 462 ms 436 KB Output is correct
14 Correct 504 ms 452 KB Output is correct
15 Correct 547 ms 432 KB Output is correct
16 Correct 527 ms 428 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 65 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -