Submission #1294960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294960		Davdav1232	Chess Rush (CEOI20_chessrush)	C++20	28 / 100	2096 ms	15944 KiB

chessrush

#include "arithmetics.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll MOD=1e9+7;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int c, r; cin>>r>>c;
    int q; cin>>q;
    //precompute for king;
    int a=1;
    int d=1;
    while(d<r-1){
        d*=2;
        a++;
    }
    int x[2][c][c];
    for(int i=0; i<c; i++){
        for(int j=i; j<c; j++){
            if(i+1>=j) x[0][i][j]=1;
            else x[0][i][j]=0;
        }
    }
    //precompute EVERYTHING
    
    int ans1[2][c][c];
    for(int i=0; i<c; i++){
        ans1[0][i][i]=1;
        for(int j=i+1; j<c; j++){
            ans1[0][i][j]=0;
        }
    }
    d=r-1;
    int f=1;
    int g=1;
    for(int e=0; e<a; e++){
        if(e>0){
        for(int i=0; i<c; i++){
            for(int j=i; j<c; j++){
                x[g][i][j]=0;
                for(int k=0; k<=i; k++){
                    x[g][i][j]=Add(x[g][i][j], Mul(x[1-g][k][i], x[1-g][k][j]));
                }
                for(int k=i+1; k<=j; k++){
                    x[g][i][j]=Add(x[g][i][j], Mul(x[1-g][i][k], x[1-g][k][j]));
                }
                for(int k=j+1; k<c; k++){
                    x[g][i][j]=Add(x[g][i][j], Mul(x[1-g][i][k], x[1-g][j][k]));
                }
            }
        }
        g=1-g;}

        if(!((1<<e)&d)) continue;
        d-=(1<<e);
        for(int i=0; i<c; i++){
            for(int j=i; j<c; j++){
                ans1[f][i][j]=0;
                for(int k=0; k<=i; k++){
                    ans1[f][i][j]=Add(ans1[f][i][j], Mul(ans1[1-f][k][i], x[1-g][k][j]));
                }
                for(int k=i+1; k<=j; k++){
                    ans1[f][i][j]=Add(ans1[f][i][j], Mul(ans1[1-f][i][k], x[1-g][k][j]));
                }
                for(int k=j+1; k<c; k++){
                    ans1[f][i][j]=Add(ans1[f][i][j], Mul(ans1[1-f][i][k], x[1-g][j][k]));
                }
            }
        }
        f=1-f;
    }
    while(q--){
        char t; cin>>t;
        int c1, c2; cin>>c1>>c2;
        if(c1>c2) swap(c1, c2);
        if(t=='P'){
            if(c1==c2){
                cout<<r-1<<" "<<1<<"\n";
            }
            else{
                cout<<"0 0\n";
            }
            continue;
        }
        if(t=='R'){
            if(c1==c2){
                cout<<"1 1\n";
            }
            else{
                cout<<"2 2\n";
            }
            continue;
        }
        if(t=='Q'){
            if(c1==c2 || c2-c1==r-1){
                cout<<"1 1\n";
            }
            else{
                int ans=4;
                if(r==c){
                    if(c1==1 || c2==r){
                        ans++;
                    }
                }
                if((r+c2-c1-1)%2==0){
                    //check 2 cases
                    if(r-c2+1<=c1){
                        ans++;
                    }
                    c1=c+1-c1;
                    c2=c+1-c2;
                    if(r-c2+1<=c1){
                        ans++;
                    }
                }
                cout<<"2 "<<ans<<"\n";
            }
        }
        if(t=='K'){
            cout<<r-1<<" "<<ans1[1-f][c1-1][c2-1]<<"\n";
            continue;
        }
    }
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 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