hack

in:
7 7
3 1 1
6 7
4 3
1 2
200000

out:

Game over after 8406 seconds
6
699 32 0 2 7
684 32 50 0 0
611 32 26 4 7
220 32 63 6 5
170 32 65 2 3
152 33 76 2 5

#include<bits/stdc++.h>
#define maxn 10
#define maxt 200005
#define maxs 23
#define maxd 10005
#define maxr 17
#define int long long
using namespace std;
int n,m,s,d,r,T,alive_antcnt,all_antcnt,level=0;
inline double ksm(double d,int z){
    double res=1.00;
    while(z){
        if(z&1)res=res*d;
        d=d*d;z>>=1;
    }
    return res;
}
inline int level_hp(int lv){
    int hp=4*ksm(1.1,lv);
    return hp;
}
int informatics[maxn][maxn];
bool havetower[maxn][maxn];
bool haveant[maxn][maxn];
bool havecake[maxn][maxn];
struct node{int x,y;};
int bossAnt;
struct Ant{int age,hp,maxHP,id,level;bool havecake;node lastplace,nowplace;}ant[10],AnsAnt[maxt];
struct SuperTower{node place;}tower[maxs];
inline void KillAnt(int aliveid){
    AnsAnt[ant[aliveid].id]=ant[aliveid];
    if(ant[aliveid].havecake){
        havecake[n][m]=true;
        ant[aliveid].havecake=false;
        bossAnt=0;
    }
    haveant[ant[aliveid].nowplace.x][ant[aliveid].nowplace.y]=false;
    for(int i=aliveid;i<alive_antcnt;++i)ant[i]=ant[i+1];
    --alive_antcnt;return;
}
inline void newant(){
    ++all_antcnt;
    ++alive_antcnt;
    if(all_antcnt%6==1)++level;
    ant[alive_antcnt].level=level;
    ant[alive_antcnt].age=0;
    ant[alive_antcnt].havecake=false;
    ant[alive_antcnt].hp=level_hp(level);
    ant[alive_antcnt].id=all_antcnt;
    ant[alive_antcnt].lastplace={-10,-10};
    ant[alive_antcnt].maxHP=level_hp(level);
    ant[alive_antcnt].nowplace={0,0};
    haveant[0][0]=true;
    return;
}
int addtime;
int target[maxs];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int atk[maxn][maxn];
bool cmp(Ant a,Ant b){return a.id<b.id;}
inline int pf(int x){return x*x;}
inline double Pf(double x){return x*x;}
int GameOver=0;
inline double dis(double x1,double y1,double x2,double y2){return sqrt(Pf(x1-x2)+Pf(y1-y2));}
signed main(){
    cin>>n>>m>>s>>d>>r;
    for(int i=1;i<=s;++i){cin>>tower[i].place.x>>tower[i].place.y;havetower[tower[i].place.x][tower[i].place.y]=true;}
    cin>>T;havecake[n][m]=true;
    for(int i=0;i<=m+1;++i)haveant[n+1][i]=true;
    for(int i=0;i<=n+1;++i)haveant[i][m+1]=true;
    for(int nowtime=1;nowtime<=T;++nowtime){
        sort(ant+1,ant+alive_antcnt+1,cmp);
        if(alive_antcnt<6&&!haveant[0][0])newant();
        for(int i=1;i<=alive_antcnt;++i){
            if(ant[i].havecake)informatics[ant[i].nowplace.x][ant[i].nowplace.y]+=5;
            else informatics[ant[i].nowplace.x][ant[i].nowplace.y]+=2;
        }
        for(int i=1;i<=alive_antcnt;++i){
            int x=ant[i].nowplace.x,y=ant[i].nowplace.y;bool chosen=false;
            int choise[10],cnt=0;
            for(int dir=0;dir<4;++dir){
                if(x+dx[dir]<0||x+dx[dir]>n||y+dy[dir]<0||y+dy[dir]>m)continue;
                if(haveant[x+dx[dir]][y+dy[dir]])continue;
                if(havetower[x+dx[dir]][y+dy[dir]])continue;
                if(x+dx[dir]==ant[i].lastplace.x&&y+dy[dir]==ant[i].lastplace.y)continue;
                chosen=true;choise[++cnt]=dir;
            }
            if(!chosen){
                ant[i].lastplace=ant[i].nowplace;
                continue;
            }
            int finaldir=0,informaticsmax=-1;
            for(int j=1;j<=cnt;++j){
                int dir=choise[j];
                if(informatics[x+dx[dir]][y+dy[dir]]>informaticsmax){
                    informaticsmax=informatics[x+dx[dir]][y+dy[dir]];
                    finaldir=dir;
                }
            }
            if(ant[i].age%5==4){
                finaldir--;
                if(finaldir==-1)finaldir=3;//informatics[x+dx[finaldir]][y+dy[finaldir]]!=informaticsmax||
                while(x+dx[finaldir]<0||x+dx[finaldir]>n||y+dy[finaldir]<0||y+dy[finaldir]>m||haveant[x+dx[finaldir]][y+dy[finaldir]]||havetower[x+dx[finaldir]][y+dy[finaldir]]){
                    finaldir--;
                    if(finaldir==-1)finaldir=3;
                }
            }
            ant[i].lastplace={x,y};
            ant[i].nowplace={x+dx[finaldir],y+dy[finaldir]};
            haveant[ant[i].lastplace.x][ant[i].lastplace.y]=false;
            haveant[ant[i].nowplace.x][ant[i].nowplace.y]=true;
            if(havecake[ant[i].nowplace.x][ant[i].nowplace.y]){
                ant[i].havecake=true;
                havecake[n][m]=false;
                bossAnt=i;
                ant[i].hp+=ant[i].maxHP/2;
                if(ant[i].hp>ant[i].maxHP)ant[i].hp=ant[i].maxHP;
            }
        }
        for(int i=1;i<=s;++i){
            target[i]=0;
            int x=tower[i].place.x,y=tower[i].place.y;
            int mindis=1e9;
            for(int j=1;j<=alive_antcnt;++j){
                int dis=pf(ant[j].nowplace.x-x)+pf(ant[j].nowplace.y-y);
                if(dis>r*r)continue;
                if(dis<mindis){
                    mindis=dis;
                    target[i]=j;
                }
                else if(dis==mindis&&ant[target[i]].age>ant[j].age)target[i]=j;
            }
            if(bossAnt)
            if(pf(ant[bossAnt].nowplace.x-x)+pf(ant[bossAnt].nowplace.y-y)<=r*r)target[i]=bossAnt;
            // cerr<<"Tower "<<i<<": "<<target[i]<<'\n';
        }
        for(int i=0;i<=n;++i)
        for(int j=0;j<=m;++j)
        atk[i][j]=0;
        for(int i=1;i<=s;++i){
            // cerr<<"Target?\n";
            if(target[i]==0)continue;
            int x=tower[i].place.x,y=tower[i].place.y;
            // cerr<<target[i]<<" I ak IOI\n";
            // cerr<<"Thinking about towers\n";
            if(ant[target[i]].nowplace.x==x){
                if(ant[target[i]].nowplace.y<y)
                    for(int j=max(ant[target[i]].nowplace.y,y-r);j<y;++j)atk[x][j]+=d;
                else
                    for(int j=y+1;j<=min(ant[target[i]].nowplace.y,y+r);++j)atk[x][j]+=d;
                continue;
            }
            if(ant[target[i]].nowplace.y==y){
                if(ant[target[i]].nowplace.x<x)
                    for(int j=max(ant[target[i]].nowplace.x,x-r);j<x;++j)atk[j][y]+=d;
                else
                    for(int j=x+1;j<=min(ant[target[i]].nowplace.x,x+r);++j)atk[j][y]+=d;
                continue;
            }
            double k,b;//y=kx+b
            k=(double)(ant[target[i]].nowplace.y-y)*1.00/(ant[target[i]].nowplace.x-x);
            b=(double)y-k*x;
            // cerr<<k<<' '<<b<<" FFTakNTT\n";
            for(int j=1;j<=alive_antcnt;++j){
                double A=ant[j].nowplace.x;
                double B=ant[j].nowplace.y;
                double R=0.5;
                double delta=Pf(2*k*b-2*A-2*k*B)-4*(1+k*k)*(A*A-2*B*b+B*B+b*b-R*R);
                if(delta<0)continue;
                double pt2=sqrt(delta);
                double pt1=(-2*k*b+2*A+2*B*k);
                double pt3=2*(1+k*k);
                double x1=(pt1+pt2)/pt3;
                double x2=(pt1-pt2)/pt3;
                double L=min(A,x*1.00),Rr=max(A,x*1.00);
                if((L<=x1&&x1<=Rr)||(L<=x2&&x2<=Rr))
                    atk[ant[j].nowplace.x][ant[j].nowplace.y]+=d;
            }
        }
        for(int i=1;i<=alive_antcnt;++i){
            ant[i].hp-=atk[ant[i].nowplace.x][ant[i].nowplace.y];
            if(ant[i].hp<0)KillAnt(i);
        }
        for(int i=1;i<=alive_antcnt;++i){
            if(ant[i].havecake&&ant[i].nowplace.x==0&&ant[i].nowplace.y==0){
                GameOver=T;
                cerr<<"Break Over AT lv14.9\n";
                break;
            }
        }
        if(GameOver)break;
        for(int i=1;i<=alive_antcnt;++i)ant[i].age++;
        addtime++;
        for(int i=0;i<=n;++i){
            for(int j=0;j<=m;++j){
                informatics[i][j]--;
                if(informatics[i][j]<0)informatics[i][j]=0;
            }
        }
    }
    if(GameOver)cout<<"Game over after "<<GameOver<<" seconds\n";
    else cout<<"The game is going on\n";
    cout<<alive_antcnt<<"\n";
    sort(ant+1,ant+alive_antcnt+1,cmp);
    for(int i=1;i<=alive_antcnt;++i)
        cout<<ant[i].age<<" "<<ant[i].level<<" "<<ant[i].hp<<" "<<ant[i].nowplace.x<<" "<<ant[i].nowplace.y<<"\n";
    cerr<<"ntt ak ioi "<<all_antcnt<<"\n";
    return 0;
}