Submission #302374

#	Time	Username	Problem	Language	Result	Execution time	Memory
302374		errorgorn	Chess Rush (CEOI20_chessrush)	C++14	51 / 100	2048 ms	39680 KiB

chessrush

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int MOD=1000000007;

int r,c,q;
vector<vector<ll> > mat;
vector<vector<ll> > b;

vector<vector<ll> > mul(vector<vector<ll> > i,vector<vector<ll> > j){
	int n=sz(i);
	vector<vector<ll> > res;
	rep(x,0,n) res.push_back(vector<ll>(n,0));
	
	rep(x,0,n) rep(y,0,n){
		rep(z,0,n) res[x][y]=(res[x][y]+i[x][z]*j[z][y])%MOD;
	}
	return res;
}

void uwu(){
	rep(x,0,c){
		mat.push_back(vector<ll>(c,0));
		b.push_back(vector<ll>(c,0));
		
		mat[x][x]=1;
		b[x][x]=1;
		if (x!=0) b[x][x-1]=1;
		if (x!=c-1) b[x][x+1]=1;
	}
	
	mat=mul(mat,mat);
	
	int rr=r;
	while (rr){
		if (rr&1) mat=mul(mat,b);
		b=mul(b,b);
		rr>>=1;
	}
}

int goal;
ii memo[105][105][2];

ii dp(int i,int j,int flag){
	if (j<1 || c<j) return ii(1e9,-1);
	if (i==0){
		if (j==goal) return ii(1,1);
		else return ii(1e9,-1);
	}
	
	if (memo[i][j][flag]!=ii(-1,-1)) return memo[i][j][flag];
	
	ii v1=dp(i-1,j-1,true),v2=dp(i-1,j+1,false);
	if (flag) v2.fi++;
	else v1.fi++;
	
	ii res;
	if (v1.fi==v2.fi) res=ii(v1.fi,(v1.se+v2.se)%MOD);
	else res=min(v1,v2);
	
	return memo[i][j][flag]=res;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>r>>c>>q;
	r--; //i think this is better?

	char qt;
	int a,b;
	
	while (q--){
		cin>>qt>>a>>b;
		
		if (qt=='P'){
			if (a==b) cout<<r<<" 1"<<endl;
			else cout<<"0 0"<<endl;
		}
		else if (qt=='R'){
			if (a==b) cout<<"1 1"<<endl;
			else cout<<"2 2"<<endl;
		}
		else if (qt=='Q'){
			if (a==b || abs(a-b)==r) cout<<"1 1"<<endl;
			else{
				int res=4;
				
				int extra=r-abs(a-b);
				if (extra%2==0 && max(a,b)+extra/2<=c) res++;
				if (extra%2==0 && 1<=min(a,b)-extra/2) res++;
				if (r==c-1 && (a==1 || a==c || b==1 || b==c)) res++;
				
				cout<<2<<" "<<res<<endl;
			}
		}
		else if (qt=='K'){
			if (mat.empty()) uwu();
		
			cout<<r<<" "<<mat[a-1][b-1]<<endl;
		}
		else if (qt=='B'){
			goal=a;
			memset(memo,-1,sizeof(memo));
			
			ii v1=dp(r,b,0),v2=dp(r,b,1);
			ii res;
			if (v1.fi==v2.fi) res=ii(v1.fi,(v1.se+v2.se)%MOD);
			else res=min(v1,v2);
			
			if (res.fi==1e9) cout<<"0 0"<<endl;
			else cout<<res.fi<<" "<<res.se<<endl;
		}
	}
}

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