显示代码纯文本
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
#include<string>
#include<iostream>
using namespace std;
const int maxn=110;
const int maxk=210;
const int maxr=1010;
const long double eps=1e-8;
int n,m,k,R,h;
int map[maxn][maxn];
int x[maxk],y[maxk];
int a[maxk],b[maxk],c[maxk],d[maxk];
int f[maxk],z[maxk],r[maxk],s[maxk];
int v[maxk],o[maxk],l[maxk];
int nown[maxk],nowm[maxk],skillable[maxk],bombed[maxk],dead[maxk];
int id[maxk];
int history[maxr][maxk][9];
int dx[4],dy[4];
int q[2][maxk];
int lastp;
int result[maxk];
bool use[maxk];
long double fac[1000010];
queue<int> enforce[maxk];
int get_num_of_skill(string s)
{
if (s == "toolihai") return 1;
if (s == "faceking") return 2;
if (s == "onepunch") return 3;
if (s == "rabiribi") return 4;
if (s == "firework") return 5;
if (s == "viuganda") return 6;
if (s == "2dsaigao") return 7;
if (s == "gugugugu") return 8;
if (s == "backward") return 9;
if (s == "hupraise") return 10;
return -100;
}
int sign(long double l)
{
if (fabsl(l)<=eps) return 0;
if (l<0) return -1;
else return 1;
}
int dis(int i,int j)
{
return abs(x[i]-x[j])+abs(y[i]-y[j]);
}
void init_one(int i)
{
nown[i]=a[i];
nowm[i]=b[i];
skillable[i]=0;
bombed[i]=0;
while (enforce[i].size())
enforce[i].pop();
dead[i]=0;
}
void init()
{
scanf("%d%d%d%d",&n,&m,&k,&R);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
scanf("%d",&map[i][j]);
for (int i=1;i<=k;i++)
{
scanf("%d%d",&x[i],&y[i]);
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
scanf("%d%d",&f[i],&z[i]);
scanf("%d",&r[i]);
string name;
cin>>name;
s[i]=get_num_of_skill(name);
if (s[i] == 1) {
} else if (s[i] == 2){
} else if (s[i] == 3) {
scanf("%d%d",&v[i],&l[i]);
} else if (s[i] == 4) {
scanf("%d",&v[i]);
} else if (s[i] == 5) {
scanf("%d",&l[i]);
} else if (s[i] == 6) {
} else if (s[i] == 7) {
scanf("%d%d%d",&o[i],&v[i],&l[i]);
} else if (s[i] == 8) {
} else if (s[i] == 9) {
scanf("%d",&l[i]);
} else if (s[i] == 10) {
}
else {
//fprintf(stderr,"wang yu zhong tian xia wu di, yang jing qin ye ye sheng hui.\n");
}
init_one(i);
}
for (int i=0;i<=n+1;i++)
map[i][0]=map[i][m+1]=1;
for (int i=0;i<=m+1;i++)
map[0][i]=map[n+1][i]=1;
lastp = 0;
}
void respawn(int i)
{
//fprintf(stderr,"%d respawns\n",i);
init_one(i);
}
void recover() {
//fprintf(stderr,"recover begin\n");
for (int i=1;i<=k;i++)
{
if (dead[i]>0)
{
dead[i]--;
if (!dead[i]) respawn(i);
}
if (f[i]>0) f[i]--;
if (skillable[i]>0) skillable[i]--;
if (bombed[i]>0) bombed[i]--;
while (enforce[i].size()>0)
{
int fv = enforce[i].front();
if (fv == h)
{
enforce[i].pop();
nown[i] = max(nown[i]-v[i],0);
nowm[i] = min(nowm[i],max(nown[i]-v[i],0));
//fprintf(stderr,"%d enforce disappears, back to (%d,%d)\n",i,nown[i],nowm[i]);
}
else break;
}
}
}
void log()
{
for (int i=1;i<=k;i++)
{
history[h][i][0] = h;
history[h][i][1] = x[i];
history[h][i][2] = y[i];
history[h][i][3] = d[i];
history[h][i][4] = nown[i];
history[h][i][5] = nowm[i];
history[h][i][6] = dead[i];
history[h][i][7] = bombed[i];
history[h][i][8] = skillable[i];
}
}
void move() {
//fprintf(stderr,"move begins\n");
for (int i=1;i<=k;i++)
if (!bombed[i] && !dead[i])
{
int xx=x[i]+dx[d[i]];
int yy=y[i]+dy[d[i]];
if (map[xx][yy])
{
d[i]=d[i]^1;
//fprintf(stderr,"%d turns at (%d,%d)\n",i,x[i],y[i]);
}
else
{
//fprintf(stderr,"%d moves from (%d,%d) to (%d,%d)\n",i,x[i],y[i],xx,yy);
x[i]=xx;
y[i]=yy;
}
}
}
bool dfs(int now)
{
for (int i=1;i<=k;i++)
if (c[i] && ((nown[i]^nown[now])%3==0) && !use[i])
{
use[i]=true;
if (!result[i] || dfs(result[i]))
{
result[i]=now;
return true;
}
}
return false;
}
void matching()
{
int ans=0;
memset(result,0,sizeof(result));
for (int i=1;i<=k;i++)
if (!c[i])
{
memset(use,false,sizeof(use));
if (dfs(i)) ans++;
}
printf("%d\n",ans);
}
bool check_in(int j,int i)
{
int ndx = x[j]-x[i];
int ndy = y[j]-y[i];
if (d[i] == 0) ndx=-ndx;
else if (d[i] == 2)
{
ndy = -ndy;
swap(ndx,ndy);
}
else swap(ndx,ndy);
return ndx >= 1 && ndx <= v[i] && ndy >= -ndx && ndy <= ndx;
}
void skill() {
//fprintf(stderr,"skill begin\n");
bool skip[2] = {false,false};
for (int i=1;i<=k;i++)
if (!f[i] && !skillable[i] && !skip[c[i]] && !dead[i])
{
//fprintf(stderr,"%d use skills %d\n",i,s[i]);
f[i]=z[i];
if (s[i] == 1) {
lastp = i;
} else if (s[i] == 2){
for (int j=1;j<=k;j++)
if (!dead[j])
{
if (d[j] == 0) d[j]=2;
else if (d[j] == 1) d[j]=3;
else if (d[j] == 2) d[j]=1;
else d[j]=0;
}
} else if (s[i] == 3) {
enforce[i].push(h+l[i]);
nown[i] += v[i];
//fprintf(stderr,"enforce to (%d,%d)\n",nown[i],nowm[i]);
} else if (s[i] == 4) {
for (int j=1;j<=k;j++)
if (check_in(j,i))
{
//fprintf(stderr,"%d is knoced from (%d,%d) to",j,x[j],y[j]);
x[j] += dx[d[i]];
y[j] += dy[d[i]];
while (map[x[j]][y[j]])
{
if (!x[j]) x[j]=n;
else if (x[j]==n+1) x[j]=1;
else if (!y[j]) y[j]=m;
else if (y[j]==m+1) y[j]=1;
else {
x[j] += dx[d[i]];
y[j] += dy[d[i]];
}
}
//fprintf(stderr," (%d,%d)\n",x[j],y[j]);
}
} else if (s[i] == 5) {
if (lastp) bombed[lastp] += l[i];
else bombed[i] += l[i];
} else if (s[i] == 6) {
int maxp=0,minp=0;
for (int j=1;j<=k;j++)
if (dead[j])
{
int distance = dis(i,j);
if (c[i] == c[j])
{
if (!maxp || distance>=dis(maxp,i)) maxp=j;
}
else
{
if (!minp || distance<=dis(minp,i)) minp=j;
}
}
if (maxp) respawn(maxp);
else if (minp) respawn(minp);
} else if (s[i] == 7) {
int nx = x[i];
int ny = y[i];
int ndx = dx[d[i]], ndy = dy[d[i]];
if (d[i] == 0) ndy = 1;
else if (d[i] == 1) ndy = -1;
else if (d[i] == 2) ndx = -1;
else ndx = 1;
for (int j=1;j<=o[i];j++)
{
int nnx = nx + ndx;
int nny = ny + ndy;
if (map[nnx][nny])
{
ndx = ndy;
ndy = -ndx;
nnx = nnx + ndx;
nny = nny + ndy;
nnx = (nnx+nx) / 2;
nny = (nny+ny) / 2;
if (map[nnx][nny])
{
ndx = ndy;
ndy = -ndx;
}
else
{
nx = nnx;
ny = nny;
}
}
else
{
nx = nnx;
ny = nny;
}
}
x[0]=nx;y[0]=ny;
//fprintf(stderr,"bomed at (%d,%d)\n",x[0],y[0]);
for (int j=1;j<=k;j++)
if (dis(0,j)<=v[i])
{
skillable[j]+=l[i];
//fprintf(stderr,"effect %d\n",j);
}
} else if (s[i] == 8) {
skip[c[i]] = true;
} else if (s[i] == 9) {
int j = h-l[i];
x[i]=history[j][i][1];
y[i]=history[j][i][2];
d[i]=history[j][i][3];
nown[i]=history[j][i][4];
nowm[i]=history[j][i][5];
dead[i]=history[j][i][6];
bombed[i]=history[j][i][7];
skillable[i]=history[j][i][8];
//fprintf(stderr,"%d jumps back to %d\n",i,j);
} else if (s[i] == 10) {
//fprintf(stderr,"matching begins\n");
matching();
}
else {
printf("wang yu zhong tian xia wu di, yang jing qin ye ye sheng hui.\n");
}
}
}
bool cmp(int i,int j)
{
if (x[i]==x[j]) return y[i]<y[j];
else return x[i]<x[j];
}
void change(int i,int j)
{
nown[j]=max(nown[j]-nown[i],0);
nowm[j]=max(nowm[j]-nown[i],0);
}
void die(int i)
{
dead[i]=r[i];
}
long double combinational(int i)
{
return fac[nown[i]]-fac[nowm[i]]-fac[nown[i]-nowm[i]];
}
bool cmp2(int i,int j)
{
return sign(combinational(i)-combinational(j))<0;
}
void fight() {
//fprintf(stderr,"fight begins\n");
for (int i=1;i<=k;i++)
id[i] = i;
sort(id+1,id+k+1,cmp);
for (int i=1;i<=k;)
{
int j=i;
while (j<=k && x[id[j]]==x[id[i]] && y[id[j]]==y[id[i]])
j++;
bool exists[2] = {false,false};
for (int t=i;t<j;t++)
if (!dead[id[t]]) exists[c[id[t]]] = true;
if (exists[0] && exists[1])
{
int cnt[2] = {0,0};
for (int t=i;t<j;t++)
if (!dead[id[t]])
{
cnt[c[id[t]]]++;
q[c[id[t]]][cnt[c[id[t]]]]=id[t];
}
sort(q[0]+1,q[0]+cnt[0]+1,cmp2);
sort(q[1]+1,q[1]+cnt[1]+1,cmp2);
//fprintf(stderr,"One fight begins\n");
//fprintf(stderr,"Team 0");
//for (int t=1;t<=cnt[0];t++)
//fprintf(stderr," %d",q[0][t]);
//fprintf(stderr,"\n");
//fprintf(stderr,"Team 1");
//for (int t=1;t<=cnt[1];t++)
//fprintf(stderr," %d",q[1][t]);
//fprintf(stderr,"\n");
int p1=cnt[0],p2=cnt[1];
while (p1!=0 && p2!=0)
{
int id1=q[0][p1];
int id2=q[1][p2];
if (cmp2(id1,id2))
{
p1--;
change(id1,id2);
die(id1);
}
else
{
if (cmp2(id2,id1))
{
p2--;
change(id2,id1);
die(id2);
}
else
{
p1--;
p2--;
die(id2);
die(id1);
}
}
}
//fprintf(stderr,"fight res %d %d\n",p1,p2);
}
i=j;
}
}
void gg_check()
{
for (int i=1;i<=k;i++)
if (x[i]<1 || x[i]>n || y[i]<1 || y[i]>m)
{
printf("%d\n",h);
exit(0);
}
}
void simulate()
{
for (int now_round=1;now_round<=R;now_round++)
{
//fprintf(stderr,"%d ronud begins\n",now_round);
h = now_round;
recover();
log();
move();
skill();
fight();
//gg_check();
}
for (int i=1;i<=k;i++)
printf("%d %d\n",x[i],y[i]);
}
int main()
{
freopen("thupc2018_problem.in","r",stdin);
freopen("thupc2018_problem.out","w",stdout);
dx[0]=-1;dx[1]=1;dy[2]=-1;dy[3]=1;
for (int a=1;a<=1000000;a++)
fac[a]=fac[a-1]+logl(a);
int T;
scanf("%d",&T);
for (int test=1;test<=T;test++)
{
//printf("%d\n",test);
//fprintf(stderr,"%d game begins\n",test);
init();
simulate();
//fprintf(stderr,"\n\n");
}
return 0;
}
LikableP