zl程序教程

您现在的位置是:首页 >  其它

当前栏目

The 19th Zhejiang Provincial Collegiate Programming Contest

The Programming Contest
2023-09-11 14:15:02 时间

题解:

https://files.cnblogs.com/files/clrs97/2022ZJCPC%E5%88%86%E6%9E%90.zip

 

Code:

A. JB Loves Math

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<map>
#include<cassert>
#include<string>
using namespace std;
#define pb push_back
#define mp make_pair
#define data dataa
#define rep(i,n) for(int i=1;i<=n;i++)
typedef long long LL;
int main()
{
	int T;
	for(scanf("%d",&T);T--;)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		if(a==b)puts("0");
		else if(a<b)
		{
			if((b-a)%2==1)puts("1");
			else if((b-a)/2%2==1)puts("2");
			else puts("3");
		}
		else
		{
			if((a-b)%2==0)puts("1");
			else puts("2");
		}
	}
    return 0;
}

  

B. JB Loves Comma

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define data dataa
#define rep(i,n) for(int i=1;i<=n;i++)
typedef long long LL;
char s[100010];
bool comma[100010];
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    rep(i,n-2)if(s[i]=='c'&&s[i+1]=='j'&&s[i+2]=='b')comma[i+2]=1;
    rep(i,n)
    {
        putchar(s[i]);
        if(comma[i])putchar(',');
    }
    puts("");
    return 0;
}

  

C. JB Wants to Earn Big Money

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define data dataa
#define rep(i,n) for(int i=1;i<=n;i++)
typedef long long LL;
int main()
{
    int n,m,x,ans=0;
    scanf("%d%d%d",&n,&m,&x);
    rep(i,n)
    {
        int y;scanf("%d",&y);
        ans+=y>=x;
    }
    rep(i,m)
    {
        int y;scanf("%d",&y);
        ans+=y<=x;
    }
    printf("%d\n",ans);
    return 0;
}

  

D. The Profiteer

#include<cstdio>
typedef long long ll;
const int N=200005,M=20;
int n,k,e,i,v[N],a[N],b[N],ans[N];
int f[M][N],g[N],h[N];
inline void up(int&a,int b){a<b?(a=b):0;}
inline void copy(int*f,int*g){for(int i=0;i<=k;i++)f[i]=g[i];}
inline void ins(int*f,int x,int y){for(int i=k;i>=x;i--)up(f[i],f[i-x]+y);}
inline bool check(int l,int r,int x,int y){//ans[x]<=y?
  if(x>y)return 0;
  int i;
  copy(h,g);
  for(i=l;i<=r;i++)ins(h,x<=i&&i<=y?b[i]:a[i],v[i]);
  ll sum=0;
  for(i=1;i<=k;i++)sum+=h[i];
  return sum<=1LL*k*e;
}
void solve(int d,int L,int R,int dl,int dr){
  if(L>R||dl>dr)return;
  int dm=(dl+dr)>>1,l=L,r=R,mid,m=L-1,i;
  copy(g,f[d]);
  for(i=dl;i<=dr;i++){
    if(i>=L&&i<=R)continue;
    ins(g,L<=i&&i<=dm?b[i]:a[i],v[i]);
  }
  while(l<=r){
    mid=(l+r)>>1;
    if(check(l,r,mid,dm)){
      for(i=l;i<=mid;i++)ins(g,mid<i&&i<=dm?b[i]:a[i],v[i]);
      l=(m=mid)+1;
    }else{
      for(i=mid;i<=r;i++)ins(g,l<=i&&i<=dm?b[i]:a[i],v[i]);
      r=mid-1;
    }
  }
  for(i=L;i<=m;i++)ans[i]=dm;
  if(L<=m&&dl<dm){
    copy(f[d+1],f[d]);
    for(i=m+1;i<=R;i++){
      if(i>=dl&&i<dm)continue;
      ins(f[d+1],L<=i&&i<dm?b[i]:a[i],v[i]);
    }
    for(i=dm;i<=dr;i++){
      if(i>=L&&i<=R)continue;
      ins(f[d+1],L<=i&&i<dm?b[i]:a[i],v[i]);
    }
    solve(d+1,L,m,dl,dm-1);
  }
  if(R>m&&dr>dm){
    copy(f[d+1],f[d]);
    for(i=L;i<=m;i++){
      if(i>dm&&i<=dr)continue;
      ins(f[d+1],m<i&&i<=dr?b[i]:a[i],v[i]);
    }
    for(i=dl;i<=dm;i++){
      if(i>=L&&i<=R)continue;
      ins(f[d+1],m<i&&i<=dr?b[i]:a[i],v[i]);
    }
    solve(d+1,m+1,R,dm+1,dr);
  }
}
int main(){
  scanf("%d%d%d",&n,&k,&e);
  for(i=1;i<=n;i++)scanf("%d%d%d",&v[i],&a[i],&b[i]);
  for(i=1;i<=n;i++)ans[i]=n+1;
  solve(0,1,n,1,n);
  ll fin=0;
  for(i=1;i<=n;i++)fin+=n-ans[i]+1;
  printf("%lld",fin);
}

  

E. Easy Jump

#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 21000;
 
int n,H,S,T1,T2;
int P[maxn],o[maxn];
double p[maxn],q[maxn];
double f[maxn][10][10];
 
int main()
{
	ios_base::sync_with_stdio(false);
	
	cin>>n>>H>>S;
	for(int i=1;i<=n;i++) cin>>P[i];
	for(int i=1;i<=n;i++) p[i]=P[i]/100.0,q[i]=1-p[i];
	
	int K; cin>>K;
	while(K--)
	{
		int x; cin>>x;
		o[x]=1;
	}
	cin>>T1>>T2;
	
	for(int s=0;s<=S;s++) for(int h=1;h<=H;h++) f[n+1][s][h]=0;
	for(int i=n;i>=1;i--) 
	{
		if(o[i])
		{
			if(T1<T2&&S>0)
			{
				for(int s=S;s<=S;s++) for(int h=2;h<=H;h++)
				{
					double mn;
					if(h>2) mn= 1+ p[i]*f[i+1][S][h] + q[i]*f[i][s][h-1];
					else mn= ( 1+ p[i]*f[i+1][S][h] + q[i]*T1 )/p[i];
					
					for(int k=h;k<=H;k++)
					{
						double temp= (k-h)*T1+(1+ p[i]*f[i+1][S][k] + q[i]*T1)/p[i];
						mn=min( mn, temp );
					}
					f[i][s][h]=mn;
				}
			}
			else
			{
				for(int s=S;s<=S;s++) for(int h=2;h<=H;h++) 
				{
					if(h>2) f[i][s][h]= 1+ p[i]*f[i+1][o[i+1]?S:s][h] + q[i]*f[i][s][h-1];
					else f[i][s][h]= ( 1+ p[i]*f[i+1][o[i+1]?S:s][h] + q[i]*T2 )/p[i]; 
				}
			}
		}
		else
		{
			for(int s=0;s<=S;s++) for(int h=2;h<=H;h++)
			{
				if(h>2) f[i][s][h]= 1+ p[i]*f[i+1][o[i+1]?S:s][h] + q[i]*f[i][s][h-1];
				else
				{
					if(s&&T1<T2)
					{
						f[i][s][h]= 1+ p[i]*f[i+1][o[i+1]?S:s][h] + q[i]*(f[i][s-1][h]+T1);
					}
					else
					{
						f[i][s][h]= ( 1+ p[i]*f[i+1][o[i+1]?S:s][h] + q[i]*T2 )/p[i]; 
					}
				}
			}
		}
	}
	cout<<fixed<<setprecision(12)<<f[1][S][H]<<endl;
	
	return 0;
}

  

F. Easy Fix

#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define ll long long
using namespace std;
 
const int maxn = 110000;
const int maxp = maxn*20;
 
int n,m;
struct segment
{
	int tot;
	int seg[maxp],lc[maxp],rc[maxp];
	void init()
	{
		tot=0;
	}
	int newnode()
	{
		++tot;
		seg[tot]=lc[tot]=rc[tot]=0;
		return tot;
	}
	int loc,c;
	void upd(int &x,const int l,const int r)
	{
		if(!x) x=newnode();
		seg[x]+=c;
		if(l==r) return;
		int mid=(l+r)>>1;
		if(loc<=mid) upd(lc[x],l,mid);
		else upd(rc[x],mid+1,r);
	}
	void merge(int &x,const int y)
	{
		if(!y) return;
		if(!x) { x=y;return; }
		seg[x]+=seg[y];
		merge(lc[x],lc[y]);
		merge(rc[x],rc[y]);
	}
	int lx,rx;
	int query(const int x,const int l,const int r)
	{
		if(rx<l||r<lx||!x) return 0;
		if(lx<=l&&r<=rx) return seg[x];
		int mid=(l+r)>>1;
		return query(lc[x],l,mid)+query(rc[x],mid+1,r);
	}
};
struct Solve
{
	int	a[maxn];
	segment seg0a,seg0b,seg2,seg_2,segc;
	int root0a[maxn],root0b[maxn],root2[maxn],root_2[maxn],rootc[maxn];
	int li[maxn],ri[maxn];
	int s[maxn];
	void upd(int x,int c){ for(;x<=n;x+=lowbit(x))s[x]+=c; }
	int query(int x)
	{
		int re=0;
		for(;x;x-=lowbit(x)) re+=s[x];
		return re;
	}
	ll ans;
	void build()
	{
		ans=0;
		for(int i=1;i<=n;i++) s[i]=0;
		seg0a.init(); seg0b.init(); seg2.init(); seg_2.init(); segc.init();
		root0a[0]=root0b[0]=root2[0]=root_2[0]=rootc[0]=0;
		for(int i=1;i<=n;i++)
		{
			int l=query(a[i]),r=a[i]-1-l;
			li[i]=l,ri[i]=r;
			int k=l-r;
			ans+=min(l,r);
			
			if(k>=0)
			{
				seg0a.loc=a[i],seg0a.c=1;
				seg0a.upd(root0a[i],1,n);
			}
			if(k<=0)
			{
				seg0b.loc=a[i],seg0b.c=1;
				seg0b.upd(root0b[i],1,n);
			}
			if(k>=2)
			{
				seg2.loc=a[i],seg2.c=1;
				seg2.upd(root2[i],1,n);
			}
			if(k<=-2)
			{
				seg_2.loc=a[i],seg_2.c=1;
				seg_2.upd(root_2[i],1,n);
			}
			
			segc.loc=a[i],segc.c=1;
			segc.upd(rootc[i],1,n);
			
			seg0a.merge(root0a[i],root0a[i-1]);
			seg0b.merge(root0b[i],root0b[i-1]);
			seg2.merge(root2[i],root2[i-1]);
			seg_2.merge(root_2[i],root_2[i-1]);
			segc.merge(rootc[i],rootc[i-1]);
			upd(a[i],1);
		}
	}
	ll query(int l,int r)
	{
		if(l==r) return ans;
		ll ret=ans;
		int x=a[l],y=a[r];
		int d= x<y?-2:2;
		if(x>y) swap(x,y);
		
		{
			ret-=min(li[l],ri[l])+min(li[r],ri[r]);
			segc.lx=1,segc.rx=a[l];
			int numc=segc.query(rootc[r],1,n)-1;
			ret+=min(numc,a[l]-1-numc);
			
			segc.lx=1,segc.rx=a[r];
			numc=segc.query(rootc[l-1],1,n);
			ret+=min(numc,a[r]-1-numc);
		}
		if(d==2) 
		{
			seg0a.lx=x,seg0a.rx=y;
			ret-=seg0a.query(root0a[r-1],1,n)-seg0a.query(root0a[l],1,n);
			seg_2.lx=x,seg_2.rx=y;
			ret+=seg_2.query(root_2[r-1],1,n)-seg_2.query(root_2[l],1,n);
			//>=0 -,<=-2 +
		}
		else 
		{
			seg0b.lx=x,seg0b.rx=y;
			ret-=seg0b.query(root0b[r-1],1,n)-seg0b.query(root0b[l],1,n);
			seg2.lx=x,seg2.rx=y;
			ret+=seg2.query(root2[r-1],1,n)-seg2.query(root2[l],1,n);
			//<=0 -, >=2 +
		}
		
		return ret;
	}
}S1;
 
int main()
{
	ios_base::sync_with_stdio(false);
	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>S1.a[i];
	
	S1.build();
	
	cin>>m;
	while(m--)
	{
		int x,y; cin>>x>>y;
		if(x>y) swap(x,y);
		cout<<S1.query(x,y)<<endl;
	}
	
	return 0;
}

  

G. Easy Glide

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
const int maxn = 1020;
const double eps = 1e-7;
 
int n;
struct point
{
	int x,y;
	double dis(point k){ return hypot(x-k.x,y-k.y); }
}p[maxn],S,T;
double Dis[maxn][maxn];
double V1,V2;
 
int vis[maxn];
double f[maxn];
 
void Dij()
{
	for(int i=0;i<=n+1;i++) 
	{
		f[i]= Dis[0][i]/V1;
	}
	for(int k=0;k<=n+1;k++)
	{
		int mni=-1;
		for(int i=0;i<=n+1;i++) if(!vis[i])
		{
			if(mni==-1 || f[mni]-eps > f[i]) mni=i;
		}
		int i=mni;
		vis[i]=1;
		for(int j=0;j<=n+1;j++) 
		{
			double dd=Dis[i][j];
			double t;
			if( i>=1 && i<=n )
				t= dd > 3*V2 ? (dd-3*V2)/V1+3 : dd/V2;
			else
				t= dd/V1;
			if(f[j]-eps > f[i]+t)
				f[j]=f[i]+t;
		}
	}
}
 
int v1,v2;
 
int main()
{
	ios_base::sync_with_stdio(false);
	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
	cin>>S.x>>S.y;
	cin>>T.x>>T.y;
	p[0]=S,p[n+1]=T;
	cin>>V1>>V2;
	
	for(int i=0;i<=n+1;i++) for(int j=0;j<=n+1;j++) Dis[i][j]=p[i].dis(p[j]);
	
	Dij();
	
	cout<<fixed<<setprecision(12)<<f[n+1]<<endl;
	
	return 0;
}

  

H. A=B

#include <bits/stdc++.h>
using namespace std;
string str[]={
	"",
	"S=XY",
	"aX=Xa",
	"bX=Xb",
	"cX=Xc",
	"X=ZP",
	"PA=dp",
	"PB=ep",
	"PC=fp",
	"pa=aP",
	"pb=bP",
	"pc=cP",
	"p=(return)0",
	"aA=Aa",
	"bA=Ab",
	"cA=Ac",
	"aB=Ba",
	"bB=Bb",
	"cB=Bc",
	"aC=Ca",
	"bC=Cb",
	"cC=Cc",
	"Ya=AY",
	"Yb=BY",
	"Yc=CY",
	"P=",
	"Z=T1",
	"1da=ad1",
	"1eb=be1",
	"1fc=cf1",
	"1a=(return)1",
	"1b=(return)1",
	"1c=(return)1",
	"1Y=(return)1",
	"1=0",
	"0da=ad0",
	"0db=bd0",
	"0dc=cd0",
	"0ea=ae0",
	"0eb=be0",
	"0ec=ce0",
	"0fa=af0",
	"0fb=bf0",
	"0fc=cf0",
	"0=",
	"Ta=Z",
	"Tb=Z",
	"Tc=Z",
	"T=(return)0"
};
int n = 48;
int main(){
	int Tid = 0;
	cin >> Tid;
	for (int i=1;i<=n;i++) cout << str[i] << endl;
	return 0;
}

  

I. Barbecue

#include<bits/stdc++.h>
using namespace std;
 
typedef unsigned long long ull;
 
const int N=1e6+1e3+7;
 
const ull P=(1ull<<61)-1,bs=13131;
 
int n,q;
 
char s[N];
 
typedef unsigned long long ull;
 
ull mul(ull a,ull b)
{
    ull l1=(uint32_t)a,h1=a>>32,l2=(uint32_t)b,h2=b>>32;
    ull l=l1*l2,m=l1*h2+l2*h1,h=h1*h2;
    ull ret=(l&P)+(l>>61)+(h<<3)+(m>>29)+(m<<35>>3)+1;
    ret=(ret&P)+(ret>>61);
    ret=(ret&P)+(ret>>61);
    return ret-1;
}
 
ull add(ull x,ull y)
{
    return x+y>=P?x+y-P:x+y;
}
 
ull pw[N];
 
ull hl[N],hr[N];
 
bool chk(int l,int r)
{
    return add(hl[r],P-mul(hl[l-1],pw[r-l+1]))==add(hr[l],P-mul(hr[r+1],pw[r-l+1]));
}
 
int main()
{
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    pw[0]=1;
    for(int i=1;i<=n;i++)
        pw[i]=mul(pw[i-1],bs);
    for(int i=1;i<=n;i++)
        hl[i]=add(mul(hl[i-1],bs),s[i]);
    for(int i=n;i>=1;i--)
        hr[i]=add(mul(hr[i+1],bs),s[i]);
    while(q--)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        if(chk(l,r))
            puts("Budada");
        else
        {
            int len=r-l+1;
            puts(len&1?"Putata":"Budada");
        }
    }
}

  

J. Frog

#include<bits/stdc++.h>
using namespace std;
double pi=acos(-1.);
struct point
{
	double x,y;
	point operator+(const point &p)const{return {x+p.x,y+p.y};}
	point operator-(const point &p)const{return {x-p.x,y-p.y};}
	point operator*(const double k)const{return {x*k,y*k};}
	point operator/(const double k)const{return {x/k,y/k};}
	point turn90()const{return {-y,x};}
	point turn(const double d)const{return {x*cos(d)-y*sin(d),x*sin(d)+y*cos(d)};}
	point flip()const{return {x,-y};}
	double abs()const{return hypot(x,y);}
	double abs2()const{return x*x+y*y;}
	point unit()const{return *this/abs();}
};
point getmid(const point &A,const point &B)
{
	point del=B-A;
	point mid=(A+B)/2.;
	point t=del.unit().turn90()*(sqrt(1.-del.abs2()/4.));
	point C=mid+t,D=mid-t;
	if(C.abs2()>D.abs2())return C;
	return D;
}
int main()
{
	ios_base::sync_with_stdio(false);
	int T;
	cin>>T;
	while(T--)
	{
		int a,b;
		cin>>a>>b;
		double turn=pi*a/180;
		b-=a;
		if(b<0)b+=360;
		int flip=0;
		if(b>180)flip=1,b=360-b;
		vector<point> ans;
		point start{1.,0.},end{cos(b*pi/180.),sin(b*pi/180.)};
		ans.push_back(start);
		if(b==0)
		{
			
		}
		else if(b<=90)
		{
			ans.push_back(getmid(start,end));
			ans.push_back(end);
		}
		else if(b<=131)
		{
			ans.push_back({1.,1.});
			ans.push_back(getmid({1.,1.},end));
			ans.push_back(end);
		}
		else
		{
			ans.push_back({1.,1.});
			ans.push_back({0.,1.});
			ans.push_back(getmid({0.,1.},end));
			ans.push_back(end);
		}
		for(auto &z:ans)
		{
			if(flip)z=z.flip();
			z=z.turn(turn);
		}
		cout<<ans.size()-1<<endl;
		for(auto z:ans)
		{
			cout<<fixed<<setprecision(10)<<z.x<<' '<<z.y<<endl;
		}
	}
	
	return 0;
}

  

K. Dynamic Reachability

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const int N=50005,M=100005,Q=100005,K=7,CNT=K*64+5;
int n,m,q,i,j,k,l,r,x,y,t,op[Q][3];
int id[N],at[CNT],cnt,pool[CNT];
bool vis[N];int scc,from[N],s[N];
ull mask[N][K],f[CNT][K],F[CNT][K],now[K];
vector<int>g[N],h[N];
struct E{
  int u,v;
  bool active,mark;
}e[M];
inline void mark(int x){
  if(~id[x])return;
  at[cnt]=x;
  id[x]=cnt++;
}
inline bool bfs(int S,int T){
  int h,t,i;
  static ull vis[K];
  for(i=0;i<K;i++)vis[i]=0;
  for(i=0;i<cnt;i++)if(i!=S)vis[i>>6]^=1ULL<<(i&63);
  pool[h=t=0]=S;
  while(h<=t){
    int x=pool[h++];
    if(x==T)return 1;
    for(i=0;i<K;i++){
      ull o=F[x][i]&vis[i];
      for(vis[i]^=o;o;o-=o&-o)pool[++t]=(i<<6)+__builtin_ctzll(o);
    }
  }
  return 0;
}
void dfs(int x){
  vis[x]=1;
  for(vector<int>::iterator j=h[x].begin();j!=h[x].end();j++)
    if(e[*j].active&&!e[*j].mark&&!vis[e[*j].u])
      dfs(e[*j].u);
  s[++t]=x;
}
inline void go(int x){
  static int q[N];
  int h=1,t=1,i,y;
  q[1]=x;
  vis[x]=0;
  from[x]=++scc;
  for(i=0;i<K;i++)now[i]=0;
  while(h<=t){
    x=q[h++];
    if(~id[x])now[id[x]>>6]|=1ULL<<(id[x]&63);
    for(vector<int>::iterator j=g[x].begin();j!=g[x].end();j++)
      if(e[*j].active&&!e[*j].mark){
        y=e[*j].v;
        if(vis[y]){
          q[++t]=y;
          vis[y]=0;
          from[y]=scc;
        }else if(from[y]<scc){
          y=from[y];
          now[0]|=mask[y][0];
          now[1]|=mask[y][1];
          now[2]|=mask[y][2];
          now[3]|=mask[y][3];
          now[4]|=mask[y][4];
          now[5]|=mask[y][5];
          now[6]|=mask[y][6];
        }
      }
  }
  for(i=0;i<K;i++)mask[scc][i]=now[i];
}
int main(){
  scanf("%d%d%d",&n,&m,&q);
  for(i=1;i<=m;i++){
    scanf("%d%d",&x,&y);
    g[x].push_back(i);
    h[y].push_back(i);
    e[i].u=x;
    e[i].v=y;
    e[i].active=1;
  }
  for(i=0;i<q;i++){
    scanf("%d%d",&op[i][0],&op[i][1]);
    if(op[i][0]==2)scanf("%d",&op[i][2]);
  }
  for(i=1;i<=n;i++)id[i]=-1;
  for(l=0;l<q;l=r){
    r=min(q,l+K*32);
    cnt=0;
    for(i=0;i<K*64;i++)at[i]=0;
    for(i=l;i<r;i++){
      if(op[i][0]==1){
        t=op[i][1];
        x=e[t].u;
        y=e[t].v;
        e[t].mark=1;
      }else{
        x=op[i][1];
        y=op[i][2];
      }
      mark(x);
      mark(y);
    }
    scc=t=0;
    for(i=1;i<=n;i++)if(!vis[i])dfs(i);
    for(i=n;i;i--)if(vis[s[i]])go(s[i]);
    for(i=0;i<cnt;i++)for(k=0;k<K;k++)f[i][k]=mask[from[at[i]]][k];
    for(i=l;i<r;i++)if(op[i][0]==1){
      t=op[i][1];
      x=e[t].u;
      y=e[t].v;
      e[t].active^=1;
    }else{
      for(j=0;j<cnt;j++)for(k=0;k<K;k++)F[j][k]=f[j][k];
      for(j=l;j<r;j++)if(op[j][0]==1){
        t=op[j][1];
        if(e[t].active)F[id[e[t].u]][id[e[t].v]>>6]|=1ULL<<(id[e[t].v]&63);
      }
      puts(bfs(id[op[i][1]],id[op[i][2]])?"YES":"NO");
    }
    for(i=l;i<r;i++){
      if(op[i][0]==1){
        t=op[i][1];
        x=e[t].u;
        y=e[t].v;
        e[t].mark=0;
      }else{
        x=op[i][1];
        y=op[i][2];
      }
      id[x]=id[y]=-1;
    }
  }
}

  

L. Candy Machine

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define data dataa
#define rep(i,n) for(int i=1;i<=n;i++)
typedef long long LL;
const int N=1000010;
int a[N],n;
int main()
{
    scanf("%d",&n);
    rep(i,n)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int now=0,ans=0;
    LL sum=0;
    rep(i,n)
    {
        sum+=a[i];
        for(;now<i&&(LL)a[now+1]*i<=sum;now++);
        ans=max(ans,i-now);
    }
    printf("%d\n",ans);
    return 0;
}

  

M. BpbBppbpBB

#include<bits/stdc++.h>
using namespace std;
char pattern[11][11]={"######","##..##","#....#","#....#","##..##","######"};
int main()
{
	ios_base::sync_with_stdio(false);
	int n,m,cnt=0,cnt2=0;
	cin>>n>>m;
	vector<string> str(n);
	for(int i=0;i<n;i++)
	{
		cin>>str[i];
		for(auto ch:str[i])
			cnt+=(ch=='#');
	}
	auto check=[&](int x,int y)
	{
		for(int i=0;i<6;i++)
			for(int j=0;j<6;j++)
			{
				if(str[x+i][y+j]!=pattern[i][j])
					return false;
			}
		return true;
	};
	for(int i=0;i+6<n;i++)
	{
		for(int j=0;j+6<m;j++)
		{
			cnt2+=check(i,j);
		}
	}
	//146x+100y=cnt
	//2x+y=cnt2
	//x=(cnt2*100-cnt)/54
	long long x54=(cnt2*100ll-cnt);
	assert(x54>=0 and x54%54==0);
	int x=x54/54;
	assert(cnt2-2*x>=0);
	int y=cnt2-2*x;
	cout<<x<<' '<<y<<endl;
	return 0;
}