【CF625E】Frog Fights（模拟）

题面

翻译：

有\(n\)只青蛙在一个被分为了\(m\)等分的圆上，对于每份顺时针依次标号。

初始时每只青蛙所在的位置是\(p_i\)，速度是\(a_i\)。

然后从\(1\)号青蛙开始，顺次移动，每只青蛙顺时针移动\(a_i\)个格子。

途中碰到的所有青蛙都会被他淘汰。

如果它淘汰了\(x\)只青蛙，那么它的速度会变为\(a_i-x\)

求最终剩下的青蛙数量以及编号。

题解

发现在没有淘汰的情况下，所有青蛙的相对位置是不会发生变化的。

那么，我们按照所有青蛙所在的位置依次排序，计算一下它淘汰前面那只青蛙的时间。

把所有的这个时间全部丢到\(set\)里面去。

每次显然是把时间最小的那次淘汰给从\(set\)中取出来，

淘汰对应的青蛙，并且更新一下状态就好了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;#define ll long long#define RG register#define MAX 111111#define inf 1e9inline int read(){ RG int x=0,t=1;RG char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=-1,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return x*t;}int p[MAX],a[MAX],n,m,q[MAX],nt[MAX],lt[MAX];set
              
               
                 >S;bool cmp(int a,int b){return p[a]
                
                  u=*S.begin();if(u.first==inf)break; int v=u.second;S.erase(S.begin()); S.erase(make_pair(calc(nt[v],nt[nt[v]]),nt[v])); if(!S.empty())S.erase(make_pair(calc(lt[v],v),lt[v])); p[v]+=u.first;p[v]%=m;--a[v]; nt[v]=nt[nt[v]];lt[nt[v]]=v; S.insert(make_pair(calc(lt[v],v),lt[v])); S.insert(make_pair(calc(v,nt[v]),v)); } printf("%d\n",S.size()); for(set
                 
                  
                    >::iterator it=S.begin();it!=S.end();++it)printf("%d ",it->second); puts("");return 0;}