oj.uz

Submission #494067

# Submission time Handle Problem Language Result Execution time Memory
494067 2021-12-14T07:51:13 Z Wayne_Yan Chess Rush (CEOI20_chessrush) C++17
36 / 100
 628 ms 692 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;
  
  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.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 332 KB Output is correct
2 Correct 336 ms 420 KB Output is correct
3 Correct 48 ms 420 KB Output is correct
4 Correct 137 ms 440 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 440 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 129 ms 424 KB Output is correct
2 Correct 130 ms 424 KB Output is correct
3 Correct 107 ms 428 KB Output is correct
4 Correct 111 ms 432 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 424 KB Output is correct
2 Correct 130 ms 424 KB Output is correct
3 Correct 107 ms 428 KB Output is correct
4 Correct 111 ms 432 KB Output is correct
5 Correct 120 ms 440 KB Output is correct
6 Correct 105 ms 436 KB Output is correct
7 Correct 112 ms 436 KB Output is correct
8 Correct 131 ms 448 KB Output is correct

Subtask #7
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 424 KB Output is correct
2 Correct 130 ms 424 KB Output is correct
3 Correct 107 ms 428 KB Output is correct
4 Correct 111 ms 432 KB Output is correct
5 Correct 120 ms 440 KB Output is correct
6 Correct 105 ms 436 KB Output is correct
7 Correct 112 ms 436 KB Output is correct
8 Correct 131 ms 448 KB Output is correct
9 Correct 337 ms 428 KB Output is correct
10 Correct 628 ms 448 KB Output is correct
11 Correct 620 ms 436 KB Output is correct
12 Correct 556 ms 444 KB Output is correct
13 Correct 463 ms 452 KB Output is correct
14 Correct 486 ms 436 KB Output is correct

Subtask #8
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 424 KB Output is correct
2 Correct 130 ms 424 KB Output is correct
3 Correct 107 ms 428 KB Output is correct
4 Correct 111 ms 432 KB Output is correct
5 Correct 120 ms 440 KB Output is correct
6 Correct 105 ms 436 KB Output is correct
7 Correct 112 ms 436 KB Output is correct
8 Correct 131 ms 448 KB Output is correct
9 Correct 337 ms 428 KB Output is correct
10 Correct 628 ms 448 KB Output is correct
11 Correct 620 ms 436 KB Output is correct
12 Correct 556 ms 444 KB Output is correct
13 Correct 463 ms 452 KB Output is correct
14 Correct 486 ms 436 KB Output is correct
15 Correct 502 ms 460 KB Output is correct
16 Correct 503 ms 436 KB Output is correct
17 Runtime error 547 ms 692 KB Execution killed with signal 7
18 Halted 0 ms 0 KB -

Subtask #9
0 / 7.0

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