Codeforces 题目AC代码集锦
Karieciation · · 休闲·娱乐
Ethflow Round 1 (Codeforces Round 1001, Div. 1 + Div. 2)
CF2062A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
char s[N];
void solve()
{
scanf("%s",s+1);
int n=strlen(s+1);
int ans=0;
for(int i=1;i<=n;i++)
if(s[i]==49)
ans++;
write(ans);
LF();
}
int main()
{
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2062B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,a[N];
void solve()
{
read(n);
bool flag=true;
for(int i=1;i<=n;i++)
{
read(a[i]);
if(a[i]<=n-i<<1||a[i]<=i-1<<1)
flag=false;
}
if(flag)
puts("YES");
else
puts("NO");
}
int main()
{
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2062C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=55;
const ll INF=0x3f3f3f3f3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n;
ll a[N],ans;
void dfs(int len,ll a[])
{
if(len==1)
{
ans=max(ans,a[1]);
return;
}
ll sum=0;
for(int i=1;i<len;i++)
sum+=a[i];
sum+=a[len];
ans=max(ans,sum);
ll b[N];
if(a[1]<a[len])
{
for(int i=1;i<len;i++)
b[i]=a[i+1]-a[i];
dfs(len-1,b);
}
else
{
for(int i=1;i<len;i++)
b[i]=a[i]-a[i+1];
dfs(len-1,b);
}
}
void solve()
{
read(n);
ans=-INF;
for(int i=1;i<=n;i++)
read(a[i]);
dfs(n,a);
write(ans);
LF();
}
int main()
{
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)
CF2061A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,a[N];
void solve()
{
read(n);
int cnt=0,flag=0;
for(int i=1;i<=n;i++)
{
read(a[i]);
if(a[i]&1)
cnt++;
else
flag=2;
}
write(cnt+flag-1);
LF();
}
int main()
{
// freopen("wjts.in","r",stdin);
// freopen("wjts.out","w",stdout);
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2061B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,a[N];
bool vis[N];
void solve()
{
read(n);
for(int i=1;i<=n;i++)
{
vis[i]=false;
read(a[i]);
}
sort(a+1,a+1+n);
bool flag=false;
int u=0;
for(int i=n-1;i;i--)
if(a[i]==a[i+1])
{
vis[i]=vis[i+1]=true,u=a[i]+a[i];
flag=true;
break;
}
if(!flag)
{
puts("-1");
return;
}
int q=INF,c,d;
for(int i=1;i<n;i++)
{
if(vis[i])
continue;
if(vis[i+1])
{
if(i+2==n)
break;
if(a[i+3]-a[i]<q)
q=a[i+3]-a[i],c=a[i],d=a[i+3];
}
else if(a[i+1]-a[i]<q)
q=a[i+1]-a[i],c=a[i],d=a[i+1];
}
if(q<u)
{
write(u>>1,u>>1,c,d);
LF();
}
else puts("-1");
}
int main()
{
// freopen("wjts.in","r",stdin);
// freopen("wjts.out","w",stdout);
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2061C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f,mod=998244353;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,a[N],f[N][2],g[N][2];
void solve()
{
read(n);
for(int i=1;i<=n;i++)
{
f[i][0]=f[i][1]=g[i][0]=g[i][1]=0;
read(a[i]);
}
f[1][0]=0,f[1][1]=1,g[1][1]=1;
if(!a[1])
f[1][0]=1;
for(int i=2;i<=n;i++)
{
f[i][1]=f[i-1][0],g[i][1]=g[i-1][0]+1;
if(g[i-1][0]==a[i])
f[i][0]=(f[i][0]+f[i-1][0])%mod,g[i][0]=g[i-1][0];
if(g[i-1][1]==a[i])
f[i][0]=(f[i][0]+f[i-1][1])%mod,g[i][0]=g[i-1][1];
}
write((f[n][0]+f[n][1])%mod);
LF();
}
int main()
{
// freopen("wjts.in","r",stdin);
// freopen("wjts.out","w",stdout);
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2061D
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f,mod=998244353;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,m;
ll a[N],b[N];
map<ll,int> A,B;
bool need(ll x,int y)
{
if(!x)
return true;
bool flag=false;
while(A[x]&&y)
A[x]--,y--;
if(y)
{
int u=x>>1,v=x-u;
if(u==v)
flag|=need(u,y<<1);
else
{
flag|=need(u,y);
if(flag)
return true;
flag|=need(v,y);
}
}
return flag;
}
void solve()
{
A.clear(),B.clear();
read(n,m);
ll suma=0,sumb=0;
for(int i=1;i<=n;i++)
{
read(a[i]);
A[a[i]]++,suma+=a[i];
}
for(int i=1;i<=m;i++)
{
read(b[i]);
B[b[i]]++,sumb+=b[i];
}
if(suma!=sumb)
{
puts("No");
return;
}
for(map<ll,int> :: iterator it=B.begin();it!=B.end();it++)
{
bool flag=need(it->first,it->second);
if(flag)
{
puts("No");
return;
}
}
puts("Yes");
}
int main()
{
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}Codeforces Round 998 (Div. 3)
CF2060A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int a,b,c,d;
void solve()
{
read(a,b,c,d);
int e=a+b,f=c-b,g=d-c;
if(f==g||e==f||e==g)
{
if(e==f&&f==g)
putchar(51);
else
putchar(50);
}
else
putchar(49);
LF();
}
int main()
{
// freopen("wjts.in","r",stdin);
// freopen("wjts.out","w",stdout);
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2060B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2005,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,m,a[N][N],b[N][N],num[N],num2[N],cnt[N];
void sot(int l,int r)
{
if(l==r)
return ;
int o=l+r>>1,u=l,v=o+1,w=l;
sot(l,o);
sot(o+1,r);
while(u<=o&&v<=r)
if(a[u][1]<=a[v][1])
{
for(int i=1;i<=m;i++)
b[w][i]=a[u][i];
num2[w++]=num[u++];
}
else
{
for(int i=1;i<=m;i++)
b[w][i]=a[v][i];
num2[w++]=num[v++];
}
while(u<=o)
{
for(int i=1;i<=m;i++)
b[w][i]=a[u][i];
num2[w++]=num[u++];
}
while(v<=r)
{
for(int i=1;i<=m;i++)
b[w][i]=a[v][i];
num2[w++]=num[v++];
}
for(;l<=r;l++)
{
for(int i=1;i<=m;i++)
a[l][i]=b[l][i];
num[l]=num2[l];
}
}
void solve()
{
read(n,m);
for(int i=1;i<=n;i++)
{
cnt[i]=0;
num[i]=i;
for(int j=1;j<=m;j++)
{
read(a[i][j]);
b[i][j]=0;
}
sort(a[i]+1,a[i]+1+m);
}
sot(1,n);
int now=-1;
for(int k=1;k<=m;k++)
for(int i=1;i<=n;i++)
{
++cnt[i];
if(a[i][cnt[i]]<=now)
{
puts("-1");
return;
}
now=a[i][cnt[i]];
}
for(int i=1;i<=n;i++)
{
write(num[i]);SP();
}LF();
}
int main()
{
// freopen("wjts.in","r",stdin);
// freopen("wjts.out","w",stdout);
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2060C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,m,a[N],vis[N],f[N];
void solve()
{
read(n,m);
for(int i=1;i<=n;i++)
{
read(a[i]);
vis[i]=false,f[i]=i;
}
sort(a+1,a+1+n);
int ans=0;
for(int i=1;i<n;i++)
{
if(vis[i])
continue;
if(a[i]<<1>m)
break;
int u=lower_bound(a+i+1,a+1+n,m-a[i])-a;
while(vis[f[u]])
f[u]++;
if(a[f[u]]!=m-a[i]||f[u]<=i||f[u]>n)
continue;
vis[f[u]++]=true,ans++;
}
write(ans);
LF();
}
int main()
{
// freopen("wjts.in","r",stdin);
// freopen("wjts.out","w",stdout);
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}
//1 1 2 3 3 3 4 5 5 5 6 7 8 9 9 9CF2060D
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,a[N];
void solve()
{
read(n);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<n;i++)
{
if(a[i]==a[i+1])
i++;
else
{
if(a[i]<a[i+1])
a[i+1]-=a[i];
else
{
puts("NO");
return;
}
}
}
puts("YES");
}
int main()
{
// freopen("wjts.in","r",stdin);
// freopen("wjts.out","w",stdout);
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2060E
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,m1,m2,f[2][N],u[N],v[N],x,y;
int Find(int p,int x)
{
return x==f[p][x]?x:f[p][x]=Find(p,f[p][x]);
}
void merge(int p,int x,int y)
{
int xx=Find(p,x),yy=Find(p,y);
if(xx!=yy)
f[p][xx]=yy;
}
void solve()
{
read(n,m1,m2);
for(int i=1;i<=n;i++)
{
f[0][i]=f[1][i]=i;
}
for(int i=1;i<=m1;i++)
read(u[i],v[i]);
for(int i=1;i<=m2;i++)
{
read(x,y);
merge(1,x,y);
}
int ans=0;
for(int i=1;i<=m1;i++)
{
x=u[i],y=v[i];
if(Find(1,x)==Find(1,y))
merge(0,x,y);
else
ans++;
}
for(int i=1;i<=n;i++)
{
x=Find(0,Find(1,i)),y=Find(0,i);
if(x!=y)
{
ans++;
merge(0,x,y);
}
}
write(ans);LF();
}
int main()
{
// freopen("wjts.in","r",stdin);
// freopen("wjts.out","w",stdout);
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}Hello 2025
CF2057A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,m;
void solve()
{
read(n,m);
write(max(n,m)+1);
LF();
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2057B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,m,a[N],vis[N];
void solve()
{
read(n,m);
for(int i=1;i<=n;i++)
read(a[i]);
sort(a+1,a+1+n);
int cnt=0;
for(int i=1;i<=n;i++)
{
if(a[i]>a[i-1])
vis[++cnt]=0;
vis[cnt]++;
}
sort(vis+1,vis+1+cnt);
int i=1;
for(;i<cnt&&m-vis[i]>=0;i++)m-=vis[i];
write(cnt-i+1);
LF();
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2057C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
ll n,m;
bool a[2][35];
void work(ll u,int k)
{
ll p=2147483648;
int o=31;
while(p)
{
if(u&p)
a[k][o]=true;
p>>=1,o--;
}
}
void solve()
{
memset(a,false,sizeof a);
read(n,m);
if(m-n==2)
{
write(n,n+1,m);
LF();
return;
}
work(n,0);
work(m,1);
bool flag=true;
ll w=0,a_=0,b_=n,c_=0;
for(int i=31;~i;i--)
{
if(flag&&a[0][i]==a[1][i])
{
if(a[0][i])
w+=(ll)(1)<<i;
continue;
}
flag=false;
if(!a_&&a[1][i])
a_=(ll)(1)<<i;
}
b_-=w;
c_=((a_<<1)-1)^(a_^b_);
if(c_+w<n||c_+w>m)
c_=a_-1;
if(b_==c_)
c_=a_+1;
write(a_+w,b_+w,c_+w);
LF();
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}
Codeforces Round 997 (Div. 2)
CF2056A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,m,x,y;
void solve()
{
read(n,m);
int xx=0,yy=0;
read(x,y);
for(int i=1;i<n;i++)
{
read(x,y);xx+=x,yy+=y;
}
write(xx+yy+(m<<1)<<1);LF();
}
int main()
{
// freopen("wjts.in","r",stdin);
// freopen("wjts.out","w",stdout);
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2056B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,ans[N],go[N];
char a[N][N];
void solve()
{
queue<int> q;
read(n);
for(int i=0;i<=n;i++)
go[i]=i,ans[i]=0;
for(int i=1;i<=n;i++)
scanf("%s",a[i]+1);
for(int i=n;i;i--)
{
int cnt=0;
for(int j=1;j<i;j++)
{
if(a[i][j]==49)
cnt++;
}
for(int j=0;j<n;j++)
{
if(!ans[j])
cnt--;
if(cnt==-1)
{
ans[j]=i;
break;
}
}
}
for(int i=0;i<n;i++)
{
write(ans[i]);SP();
}LF();
}
int main()
{
// freopen("wjts.in","r",stdin);
// freopen("wjts.out","w",stdout);
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2056C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n;
void solve()
{
read(n);
if(n==6)
puts("1 1 2 3 1 2");
else if(n==7)
puts("1 1 2 3 1 2 2");
else if(n==8)
puts("1 1 2 3 1 2 4 2");
else if(n<24)
{
printf("1 2 2 1 3 2 1 1 2 ");
int cnt=0,p=4;
for(int i=0;i<n-9;i++)
{
cnt++;
write(p);SP();
if(cnt==5)
cnt=0,p++;
}
LF();
}
else
{
printf("1 2 2 2 1 3 2 4 1 3 2 1 1 1 2 ");
int cnt=0,p=5;
for(int i=0;i<n-15;i++)
{
cnt++;
write(p);SP();
if(cnt==7)
cnt=0,p++;
}
LF();
}
}
int main()
{
// freopen("wjts.in","r",stdin);
// freopen("wjts.out","w",stdout);
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}Good Bye 2024: 2025 is NEAR
CF2053A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,a[N];
bool work()
{
for(int i=1;i<n;i++)
if((a[i]<<1)>a[i+1]&&(a[i+1]<<1)>a[i])
return true;
return false;
}
void solve()
{
read(n);
for(int i=1;i<=n;i++)
read(a[i]);
bool ans=work();
if(ans)
puts("YES");
else
puts("NO");
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2053B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,x[N],y[N],vis[N],sum[N];
void solve()
{
read(n);
for(int i=1;i<=n<<1;i++)
vis[i]=sum[i]=0;
for(int i=1;i<=n;i++)
{
read(x[i],y[i]);
if(x[i]==y[i])
vis[x[i]]++,sum[x[i]]=1;
}
for(int i=1;i<=n<<1;i++)
sum[i]+=sum[i-1];
for(int i=1;i<=n;i++)
{
int u=sum[y[i]]-sum[x[i]-1],v=y[i]-x[i]+1;
if((x[i]==y[i]&&vis[x[i]]<2)||u<v)
putchar(49);
else
putchar(48);
}
putchar(10);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2053C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
ll n,k,ans;
void solve()
{
ans=0;
read(n,k);
ll t=n,i=1;
while(true)
{
if(t<k)
break;
if(t&1)
ans+=i;
t>>=1,i<<=1;
}
write(ans*(1+n)>>1);
LF();
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2053D
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
const ll mod=998244353;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,q;
ll x,y,a[N],b[N],c[N],d[N];
ll qp(ll a,ll b){
ll res=1;
while(b){
if(b&1)
res=res*a%mod;
a=a*a%mod,b>>=1;
}
return res;
}
void solve()
{
read(n,q);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<=n;i++)
{
read(b[i]);
c[i]=a[i],d[i]=b[i];
}
sort(c+1,c+1+n);
sort(d+1,d+1+n);
ll ans=1;
for(int i=1;i<=n;i++)
ans=ans*min(c[i],d[i])%mod;
write(ans);
while(q--)
{
SP();
read(x,y);
if(x==1)
{
int u=upper_bound(c+1,c+1+n,a[y])-c-1;
c[u]++;
if(d[u]>a[y])
ans=(ans*qp(a[y],mod-2)%mod)*c[u]%mod;
a[y]++;
}
else
{
int u=upper_bound(d+1,d+1+n,b[y])-d-1;
d[u]++;
if(c[u]>b[y])
ans=(ans*qp(b[y],mod-2)%mod)*d[u]%mod;
b[y]++;
}
write(ans);
}
LF();
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}Codeforces Round 994 (Div. 2)
CF2049A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,a[N];
void solve()
{
scanf("%d",&n);
bool flag=false,ff=false,fr=false;
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
if(a[i]&&flag&&fr)
ff=true;
if(!a[i]&&flag)
fr=true;
if(a[i])
flag=true;
}
if(ff)
puts("2");
else if(flag)
puts("1");
else
puts("0");
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}CF2049B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n;
char s[N];
void solve()
{
scanf("%d%s",&n,s+1);
int l=0,r=n;
while(s[l+1]=='s'||s[l+1]=='.')
l++;
while(s[l]=='.')
l--;
if(l<=1)
{
while(s[r]=='p'||s[r]=='.')
r--;
if(l>=r)
puts("YES");
else
puts("NO");
}
else
{
while(s[l]=='s'||s[l]=='.')
l++;
if(l>=r)
puts("YES");
else
puts("NO");
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}
CF2049C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,x,y;
void solve()
{
scanf("%d%d%d",&n,&x,&y);
if(n&1)
{
int z=0;
for(int i=1;i<=n;i++)
{
if(i==x)
putchar(50);
else
{
putchar(z+48);
z^=1;
}
putchar(32);
}
}
else if(!(y-x&1))
{
int z=0;
for(int i=1;i<=n;i++)
{
if(i==x)
putchar(50);
else
putchar(z+48);
putchar(32);
z^=1;
}
}
else
{
int z=0;
for(int i=1;i<=n;i++)
{
putchar(48+z);
z^=1;
putchar(32);
}
}
putchar(10);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
solve();
return 0;
}Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
CF2034A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,m;
int gcd(int a,int b)
{
int t=a%b;
while(t)
a=b,b=t,t=a%b;
return b;
}
int lcm(int a,int b){return a*b/gcd(a,b);}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
printf("%d\n",lcm(n,m));
}
return 0;
}CF2034B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,m,k;
char s[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%s",&n,&m,&k,s+1);
int t=0,ans=0,v=0;
for(int i=1;i<=n;i++)
{
if(s[i]==48)
if(!v)
t++;
if(s[i]==49)
t=0;
if(t==m)
ans++,t=0,v=k;
if(v)
v--;
}
printf("%d\n",ans);
}
return 0;
}CF2034C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005,INF=0x3f3f3f3f;
int n,m,f[N*N];
char s[N][N];
bool vis[N*N];
int Find(int x)
{
return x==f[x]?x:f[x]=Find(f[x]);
}
void merge(int x,int y)
{
int xx=Find(x),yy=Find(y);
if(xx!=yy)
f[xx]=yy;
else
vis[xx]=true;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
for(int i=1;i<=m;i++)
s[0][i]=s[n+1][i]=0;
for(int i=1;i<=n;i++)
s[i][0]=s[i][m+1]=0;
for(int i=0;i<=n+1;i++)
for(int j=0;j<=m+1;j++)
f[i*(m+2)+j]=i*(m+2)+j,vis[i*(m+2)+j]=false;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int now=i*(m+2)+j;
if(s[i][j]=='U')
merge(now,(i-1)*(m+2)+j);
else if(s[i][j]=='L')
merge(now,i*(m+2)+j-1);
else if(s[i][j]=='D')
merge(now,(i+1)*(m+2)+j);
else if(s[i][j]=='R')
merge(now,i*(m+2)+j+1);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(s[i][j]=='?')
{
int now=i*(m+2)+j,a=Find((i-1)*(m+2)+j),b=Find(i*(m+2)+j-1),c=Find((i+1)*(m+2)+j),d=Find(i*(m+2)+j+1);
if(a==now||b==now||c==now||d==now||vis[a]||vis[b]||vis[c]||vis[d]||s[a/(m+2)][a%(m+2)]||s[b/(m+2)][b%(m+2)]||s[c/(m+2)][c%(m+2)]||s[d/(m+2)][d%(m+2)])
vis[now]=true;
}
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(vis[Find(i*(m+2)+j)])
ans++;
printf("%d\n",ans);
}
return 0;
}CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
CF2039A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
printf("%d ",(i<<1)-1);
putchar(10);
}
return 0;
}CF2039B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
string s;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
cin>>s;
int n=s.length();
bool flag=false;
for(int i=0;i<n;i++)
{
if(i&&s[i]==s[i-1])
{
putchar(s[i]);
putchar(s[i]);
flag=true;
break;
}
if(i>1&&s[i]!=s[i-2]&&s[i]!=s[i-1])
{
putchar(s[i-2]);
putchar(s[i-1]);
putchar(s[i]);
flag=true;
break;
}
}
if(!flag)
{
putchar(45);
putchar(49);
}
putchar(10);
}
return 0;
}CF2039C1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n;
ll m;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%lld",&n,&m);
int ans=0;
for(int i=1;i<=min(m,ll(n<<1));i++)
if(i!=n&&(i%(n^i)==0||n%(n^i)==0))
ans++;
printf("%d\n",ans);
}
return 0;
}CF2039C2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n;
ll m;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%lld",&n,&m);
if(n==1)
{
printf("%lld\n",m);
continue;
}
if(n==2)
{
printf("%lld\n",(m>>1)+1);
continue;
}
ll ans=m/n;
ll v=ans*n;
if((v^n)>m)
ans--;
while((v+n^n)<=m)
ans++,v+=n;
for(int i=1;i<=min(m,(ll)(n<<2));i++)
if((n^i)%i==0&&(n^i)&n)
ans++;
printf("%lld\n",ans);
}
return 0;
}CF2039D
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,INF=0x3f3f3f3f;
int n,m,a[N],dep[N];
int main()
{
int T;
scanf("%d",&T);
dep[1]=1;
for(int i=2;i<N;i++)
for(int j=1;j*j<=i;j++)
if(i%j==0)
dep[i]=max(dep[i],max(dep[j]+1,dep[i/j]+1));
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d",a+i);
sort(a+1,a+1+m,greater<int>());
int maxi=1;
for(int i=1;i<=n;i++)
maxi=max(maxi,dep[i]);
if(m<maxi)
puts("-1");
else
{
for(int i=1;i<=n;i++)
printf("%d ",a[dep[i]]);
putchar(10);
}
}
return 0;
}Codeforces Round 984 (Div. 3)
CF2036A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,a[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
bool flag=true;
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
int x=abs(a[i]-a[i-1]);
if(i>1&&x!=5&&x!=7)
flag=false;
}
if(flag)
puts("YES");
else puts("NO");
}
return 0;
}CF2036B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,k,b[N],c[N],vis[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++)
vis[i]=0;
for(int i=1;i<=k;i++)
{
scanf("%d%d",b+i,c+i);
vis[b[i]]+=c[i];
}
sort(vis+1,vis+1+k,greater<int>());
ll ans=0;
for(int i=1;i<=min(n,k);i++)
ans+=vis[i];
printf("%lld\n",ans);
}
return 0;
}CF2036C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int q,n,m,p;
bool vis[N];
char a[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s%d",a+1,&q);
n=strlen(a+1);
int cnt=0;
for(int i=1;i<=n;i++)
vis[i]=false;
for(int i=4;i<=n;i++)
{
if(a[i]==48&&a[i-1]==48&&a[i-2]==49&&a[i-3]==49)
vis[i]=true,cnt++;;
}
while(q--)
{
scanf("%d%d",&m,&p);
if(a[m]!=p+48)
{
if(p)
{
a[m]=49;
if(vis[m])
vis[m]=false,cnt--;
if(m+1<=n&&vis[m+1])
vis[m+1]=false,cnt--;
if(m+2<=n&&m>1&&a[m-1]==49&&a[m+1]==48&&a[m+2]==48)
vis[m+2]=true,cnt++;
if(m+3<=n&&a[m+1]==49&&a[m+2]==48&&a[m+3]==48)
vis[m+3]=true,cnt++;
}
else
{
a[m]=48;
if(m>3&&a[m-3]==49&&a[m-2]==49&&a[m-1]==48)
vis[m]=true,cnt++;
if(m+1<=n&&n>2&&vis[m+1]==0&&a[m-1]==49&&a[m-2]==49&&a[m+1]==48)
vis[m+1]=true,cnt++;
if(m+2<=n&&vis[m+2])
vis[m+2]=false,cnt--;
if(m+3<=n&&vis[m+3])
vis[m+3]=false,cnt--;
}
}
if(cnt)puts("YES");
else puts("NO");
}
}
return 0;
}CF2036D
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005,INF=0x3f3f3f3f;
int n,m,p[N>>1][N<<4],cnt[N>>1];
char a[N][N];
void fun(int u,int lx,int rx,int ly,int ry)
{
int c=0;
for(int i=ly;i<=ry;i++)
p[u][++c]=a[lx][i]-48;
for(int i=lx+1;i<=rx;i++)
p[u][++c]=a[i][ry]-48;
for(int i=ry-1;i>=ly;i--)
p[u][++c]=a[rx][i]-48;
for(int i=rx-1;i>lx;i--)
p[u][++c]=a[i][ly]-48;
for(int i=c+1;i<min(c+4,c<<1);i++)
p[u][i]=p[u][i-c];
cnt[u]=min(c+3,(c<<1)-1);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%s",a[i]+1);
int q=min(n,m)>>1;
for(int i=1;i<=q;i++)
fun(i,i,n-i+1,i,m-i+1);
int ans=0;
for(int i=1;i<=q;i++)
for(int j=1;j<cnt[i]-2;j++)
if(p[i][j]==1&&p[i][j+1]==5&&p[i][j+2]==4&&p[i][j+3]==3)
ans++;
printf("%d\n",ans);
}
return 0;
}Codeforces Round 979 (Div. 2)
CF2030A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,a[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int minn=N,maxn=0;
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
maxn=max(maxn,a[i]),minn=min(minn,a[i]);
}
printf("%d\n",(maxn-minn)*(n-1));
}
return 0;
}CF2030B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<n;i++)
putchar(48);
puts("1");
}
return 0;
}CF2030C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n;
char s[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%s",&n,s+1);
bool t=false,F=false;
if(s[1]==49||s[n]==49)
F=true;
for(int i=1;!F&&i<=n;i++)
{
if(s[i]==49)
{
if(t)
F=true;
else
t=true;
}
else
t=false;
}
if(F)
puts("YES");
else
puts("NO");
}
return 0;
}Codeforces Round 982 (Div. 2)
CF2027A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int a=0,b=0;
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a=max(a,x),b=max(b,y);
}
printf("%d\n",a+b<<1);
}
return 0;
}CF2027B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,a[N],b[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int ans=INF;
for(int i=1;i<=n;i++)
scanf("%d",a+i);
for(int i=1;i<=n;i++)
{
int cnt=0;
for(int j=1;j<i;j++)
if(a[i]!=a[j])cnt++;
for(int j=i+1;j<=n;j++)
if(a[i]<a[j])cnt++;
ans=min(ans,cnt);
}
printf("%d\n",ans);
}
return 0;
}CF2027C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n;
ll a[N];
pair<ll,ll> siz[N];
map<ll,bool> p;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",a+i);
siz[i].first=a[i]+(i-1<<1),siz[i].second=n-i+1;
}
sort(siz+1,siz+1+n);
p.clear();
p[n]=true;
for(int i=1;i<=n;i++)
if(p[siz[i].first-(n-siz[i].second)])
p[siz[i].first]=true;
map<ll,bool>::iterator it=p.end();
it--;
while(!it->second)
it--;
printf("%lld\n",it->first);
}
return 0;
}Codeforces Round 974 (Div. 3)
CF2014A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,m,a[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
int sum=0,ans=0;
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
if(a[i]>=m)sum+=a[i];
if(a[i]==0&&sum)sum--,ans++;
}
printf("%d\n",ans);
}
return 0;
}CF2014B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,k;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
k%=4;
n&=1;int ans=0;
for(int i=0;i<k;i++)ans+=n++;
if(ans&1)puts("NO");
else puts("YES");
}
return 0;
}CF2014C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,a[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
ll sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
sum=sum+a[i];
}
if(n<3)
{
puts("-1");continue;
}
sort(a+1,a+1+n);
ll v=(ll)a[n+2>>1]*n<<1;
if(sum>v)
puts("0");
else
printf("%lld\n",v-sum+1);
}
return 0;
}CF2014D
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,a[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
ll sum=0;
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
sum=sum+a[i];
}
if(n<3)
{
puts("-1");continue;
}
sort(a+1,a+1+n);
ll u=a[n+2>>1];
ll v=u*2*n;
if(sum>v)
puts("0");
else
printf("%lld\n",v-sum+1);
}
return 0;
}Codeforces Round 972 (Div. 2)
CF2005A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
char s[5]={'a','e','i','o','u'};
int n;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
if(n<6)
for(int i=0;i<n;i++)
putchar(s[i]);
else
{
int t=n/5;
n-=t;
for(int i=0;i<t;i++)
putchar(97);
t=n/4,n-=t;
for(int i=0;i<t;i++)
putchar(s[1]);
t=n/3,n-=t;
for(int i=0;i<t;i++)
putchar(s[2]);
t=n/2,n-=t;
for(int i=0;i<t;i++)
putchar(s[3]);
t=n;
for(int i=0;i<t;i++)
putchar(s[4]);
}
putchar('\n');
}
return 0;
}CF2005B1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,m,q,a[N],x;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;i++)
scanf("%d",a+i);
sort(a+1,a+1+m);
while(q--)
{
scanf("%d",&x);
int j=-1;
for(int i=1;i<=m;i++)
if(a[i]>=x)
{
j=i;
break;
}
if(a[j]==x)
{
putchar(48);putchar(10);
continue;
}
if(j==1)
{
printf("%d\n",a[j]-1);
continue;
}
if(j==-1)
{
printf("%d\n",n-a[m]);
continue;
}
printf("%d\n",a[j]-a[j-1]>>1);
}
}
return 0;
}CF2005B2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,m,q;
ll a[N],x;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%lld%d%d",&n,&m,&q);
set<ll> s;
for(int i=1;i<=m;i++)
{
scanf("%lld",a+i);
s.insert(a[i]);
}
m=0;
for(set<ll>::iterator it=s.begin();it!=s.end();it++)
a[++m]=(*it);
while(q--)
{
scanf("%lld",&x);
int j=upper_bound(a+1,a+1+m,x)-a;
if(a[j-1]==x)
{
putchar(48);putchar(10);
continue;
}
if(j==1)
{
printf("%lld\n",a[j]-1);
continue;
}
if(j==m+1)
{
printf("%lld\n",n-a[m]);
continue;
}
printf("%lld\n",a[j]-a[j-1]>>1);
}
}
return 0;
}Educational Codeforces Round 169 (Rated for Div. 2)
CF2004A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,x[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",x+i);
if(n<2||n==2&&abs(x[1]-x[2])>1)
puts("YES");
else
puts("NO");
}
return 0;
}CF2004B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int l,r,x,y;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&l,&r,&x,&y);
if(r<x||y<l)
puts("1");
else
{
int ans=min(r,y)-max(l,x);
if(min(l,x)<max(l,x))
ans++;
if(max(r,y)>min(r,y))
ans++;
printf("%d\n",ans);
}
}
return 0;
}
CF2004C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n;
ll m,a[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",a+i);
sort(a+1,a+1+n);
ll sum=0;
for(int i=n;i>1;i-=2)
if(m+a[i-1]<a[i])
sum+=a[i]-m-a[i-1],m=0;
else
m-=a[i]-a[i-1];
ll d=0;
if(n&1)
d=a[1];
printf("%lld\n",sum+d);
}
return 0;
}Codeforces Round 968 (Div. 2)
CF2003A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n;
char s[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%s",&n,&s);
if(s[0]!=s[n-1])
puts("YES");
else
puts("NO");
}
return 0;
}CF2003B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,a[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
sort(a+1,a+1+n);
printf("%d\n",a[n+2>>1]);
}
return 0;
}CF2003C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,a[26];
char s[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%s",&n,s);
for(int i=0;i<n;i++)
a[s[i]-97]++;
bool flag=true;
while(flag)
{
flag=false;
for(int i=0;i<26;i++)
{
if(a[i])
{
putchar(i+97);
a[i]--,flag=true;
}
}
}putchar(10);
}
return 0;
}CF2003D1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n;
ll u[N],v[N],m;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
set<ll> q;
ll maxn=0,ans=0;
scanf("%d%lld",&n,&m);
for(int i=1;i<=n;i++)
{
int len;u[i]=v[i]=-1;
scanf("%d",&len);
for(int j=0;j<len;j++)
{
ll y;
scanf("%lld",&y);
q.insert(y);
}
set<ll> ::iterator it=q.begin();
ll pre=0;
for(;it!=q.end();it++)
{
if(*it!=pre)
{
u[i]=pre++;
break;
}
pre++;
}
if(u[i]==-1)
u[i]=pre++;
for(;it!=q.end();it++)
{
if(*it!=pre)
{
v[i]=pre++;
break;
}
pre++;
}
if(v[i]==-1)
v[i]=pre++;
maxn=max(maxn,v[i]);
q.clear();
}
if(maxn<m)
ans=maxn*maxn+((maxn+m)*(m-maxn+1)>>1);
else
ans=maxn*(m+1);
printf("%lld\n",ans);
}
return 0;
}Codeforces Round 966 (Div. 3)
CF2000A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
char s[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",s);
if((strlen(s)>3||strlen(s)==3&&s[2]>49)&&s[2]>'0'&&s[0]=='1'&&s[1]=='0')
puts("YES");
else
puts("NO");
}
return 0;
}CF2000B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,a[N];
bool vis[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(vis,false,sizeof vis);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",a+i);
bool flag=false;
vis[a[1]]=true;
for(int i=2;i<=n;i++)
{
if(vis[a[i]-1]==false&&vis[a[i]+1]==false)
flag=true;
vis[a[i]]=true;
}
if(flag)
puts("NO");
else
puts("YES");
}
return 0;
}CF2000C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,INF=0x3f3f3f3f;
int n,m,a[N],aa[N],bi[27];
bool vis[N];
string s;
vector<int> G[27];
set<int> se;
map<int,int> p;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(vis,false,sizeof vis);
memset(bi,0,sizeof bi);
scanf("%d",&n);
s.clear(),se.clear(),p.clear();
int idx=1;
for(int i=1;i<=n;i++)
{
scanf("%d",a+i);
se.insert(a[i]);
}
for(set<int>::iterator it=se.begin();it!=se.end();it++)
p[*it]=idx++;
for(int i=1;i<=n;i++)
a[i]=p[a[i]];
idx=1;
for(int i=1;i<=n;i++)
{
if(!bi[a[i]])
bi[a[i]]=idx++;
a[i]=bi[a[i]];
}
scanf("%d",&m);
for(int i=0;i<26;i++)
G[i].clear();
for(int i=1;i<=m;i++)
{
cin>>s;
memset(bi,0,sizeof bi);
if(s.size()!=n||se.size()>26)
{
puts("NO");
continue;
}
idx=1;
for(int j=0;j<n;j++)
{
if(!bi[s[j]-96])
bi[s[j]-96]=idx++;
aa[j+1]=bi[s[j]-96];
}
bool flag=false;
for(int j=1;j<=n;j++)
{
if(a[j]!=aa[j])
flag=true;
}
if(flag)
puts("NO");
else
puts("YES");
}
}
return 0;
}CF2000D
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n;
ll a[N],sum[N];
char s[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
ll ans=0;
for(int i=1;i<=n;i++)
{
scanf("%lld",a+i);
sum[i]=sum[i-1]+a[i];
}
scanf("%s",s+1);
int l=1,r=n;
for(;l<r;)
{
while(l<r&&s[l]!='L')
l++;
while(l<r&&s[r]=='L')
r--;
if(l<r)
ans+=sum[r--]-sum[l-1],l++;
}
printf("%lld\n",ans);
}
return 0;
}CF2000E
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,m,k,w;
ll a[N],b[N];
vector<ll> v[N];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&n,&m,&k,&w);
for(int i=0;i<n;i++)
v[i].clear();
for(int i=1;i<=w;i++)
scanf("%lld",a+i);
sort(a+1,a+1+w);
int heng=m-k+1,shu=n-k+1,maxn;
for(int i=0;i<heng;i++)
if(i<k)
v[0].push_back(i+1),maxn=i+1;
else
v[0].push_back(k);
for(int i=heng;i<m;i++)
v[0].push_back(min(m-i,maxn));
maxn=1;
for(int i=1;i<shu;i++)
if(i<k)
v[i].push_back(i+1),maxn=i+1;
else
v[i].push_back(k);
for(int i=shu;i<n;i++)
v[i].push_back(min(n-i,maxn));
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
v[i].push_back(v[0][j]*v[i][0]);
int idx=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
b[++idx]=v[i][j];
sort(b+1,b+1+idx);
ll ans=0;
for(int i=w,j=idx;i;i--,j--)
ans+=a[i]*b[j];
printf("%lld\n",ans);
}
return 0;
}Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)
CF1994A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=15,INF=0x3f3f3f3f;
int n,m,a[N][N],b[N][N],vis[N*N];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",a[i]+j);
if(n==1&&m==1)
{
puts("-1");
continue;
}
b[1][1]=a[n][m];
int c=a[1][1];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if(i==1&&j==1)
continue;
b[i][j]=c,c=a[i][j];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
printf("%d ",b[i][j]);
putchar(10);
}
}
return 0;
}CF1994B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n;
char s[N],b[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%s%s",&n,s+1,b+1);
bool flag=true;
for(int i=1;i<=n;i++)
{
if(s[i]==49)
break;
if(s[i]==48&&s[i]!=b[i])
{
flag=false;
break;
}
}
if(flag)
puts("YES");
else
puts("NO");
}
return 0;
}CF1994C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
void LF(){putchar(10);}
void SP(){putchar(32);}
template<typename T>void read(T& x)
{
x=0;char ch=getchar();ll f=1;while(ch<48||ch>57){if(ch==45)f=-1;ch=getchar();}
while(ch>47&&ch<58)x=(x<<3)+(x<<1)+(ch&15),ch=getchar();x*=f;
}
template<typename T,typename... Args>void read(T& x,Args&... args){read(x);read(args...);}
template<typename T>void write(T x)
{
if(x<0){putchar(45);x=-x;}
if(x>9)write(x/10);
putchar(x%10|48);
}
template<typename T,typename... Ts>void write(T x,Ts... args){write(x);if(sizeof...(args)!=0){SP();write(args...);}}
int n,a[N];
ll x,sum[N],f[N];
bool check(int u,int v)
{
if(sum[v]-sum[u-1]>x)
return false;
return true;
}
int work(int u)
{
int l=u,r=n;
while(l<=r)
{
int o=l+r>>1;
if(check(u,o))
l=o+1;
else
r=o-1;
}
return l;
}
void solve()
{
read(n,x);
for(int i=1;i<=n;i++)
{
f[i]=0;
read(a[i]);
sum[i]=sum[i-1]+a[i];
}
f[n+1]=f[n+2]=0;
for(int i=n;i;i--)
{
int u=work(i);
f[i]=u-i+f[u+1];
}
ll ans=0;
for(int i=1;i<=n;i++)
ans+=f[i];
write(ans);
LF();
}
int main()
{
int T=1;
scanf("%d",&T);
while(T--)
solve();
return 0;
}Codeforces Round 957 (Div. 3)
CF1992A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int a,b,c;
priority_queue<int,vector<int>,greater<int> > q;
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&a,&b,&c);
q.push(a),q.push(b),q.push(c);
int u=5;
while(u--)
{
int t=q.top();
q.pop();
q.push(++t);
}
int ans=1;
while(q.size())
{
ans*=q.top();
q.pop();
}
printf("%d\n",ans);
}
return 0;
}CF1992B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,k;
ll a[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
ll maxn=0;
for(int i=1;i<=k;i++)
{
scanf("%lld",a+i);
if(a[i]>maxn)
swap(a[i],maxn);
}
ll ans=0;
for(int i=1;i<=k;i++)
if(a[i])
ans+=a[i]*2-1;
printf("%lld\n",ans);
}
return 0;
}CF1992C
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,m,k;
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
for(int i=n;i>m;i--)
printf("%d ",i);
for(int i=1;i<=m;i++)
printf("%d ",i);
putchar('\n');
}
return 0;
}CF1992D
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,m,k;
char s[N];
bool check()
{
int c=0,w=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='C')
c+=w+1,w=0;
else if(s[i]=='W')
w++;
else
{
if(c+w>m)
k-=c+w-m;
w=c=0;
}
if(c>m||k<0)
return false;
}
return true;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d%s",&n,&m,&k,s+1);
m--,s[++n]='L';
if(check())
puts("YES");
else
puts("NO");
}
return 0;
}CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)
CF1942A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,m;
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
if(m==1){
for(int i=1;i<=n;i++)
printf("%d ",i);
putchar(10);
}
else if(m==n){
for(int i=1;i<=n;i++)
printf("1 ");
putchar(10);
}
else
puts("-1");
}
return 0;
}CF1942B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,a[N],vis[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
vis[i-1]=false;
scanf("%d",a+i);
}
int minn=0;
for(int i=1;i<=n;i++){
if(a[i]>0){
vis[minn]=true;
printf("%d ",minn);
}
if(a[i]<0){
vis[minn-a[i]]=true;
printf("%d ",minn-a[i]);
}
while(vis[minn])
minn++;
}
putchar('\n');
}
return 0;
}CF1942C1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,INF=0x3f3f3f3f;
int n,x,y,a[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&x,&y);
for(int i=1;i<=x;i++){
scanf("%d",a+i);
}
int sum=x-2;
sort(a+1,a+1+x);
for(int i=2;i<=x;i++)
if(a[i]-a[i-1]==2)
sum++;
if(a[1]+n-a[x]==2)
sum++;
printf("%d\n",sum);
}
return 0;
}CF1942C2
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int n,x,y,a[N],b[N];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&x,&y);
for(int i=1;i<=x;i++)
scanf("%d",a+i);
int sum=x-2;
sort(a+1,a+1+x);
b[1]=a[1]+n-a[x]-1;
for(int i=2;i<=x;i++)
b[i]=a[i]-a[i-1]-1;
sort(b+1,b+1+x);
for(int i=1;i<=x;i++)
if(b[i]==1)
sum++;
for(int i=1;i<=x&&y;i++)
if(b[i]>1&&(b[i]&1)){
int p=b[i]>>1;
if(p<=y)
y-=p,sum+=2*p+1;
else
sum+=y*2,y=0;
}
for(int i=1;i<=x&&y;i++)
if(b[i]&&(!(b[i]&1))){
int p=b[i]>>1;
if(p<=y)
y-=p,sum+=2*p;
else
sum+=y*2,y=0;
}
printf("%d\n",sum);
}
return 0;
}