idea: Imakf
Solution
Tutorial is loading...
Code
By Imakf
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define LL long long
const LL MOD = 1e9 + 7;
const int MX = 1e5 + 23;
int read(){
char k = getchar(); LL x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
int n ,a[MX];
void solve(){
n = read();
for(int i = 1 ; i <= n ; ++i) a[i] = read();
int ok = 1;
for(int i = 1 ; i <= n ; ++i){
if(a[i] % a[1]) ok = false;
}
puts(ok ? "YES" : "NO");
}
int main(){
int T = read();
while(T--) solve();
return 0;
}
idea: waaitg
Solution
Tutorial is loading...
Code
By Imakf
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)\
freopen(#x".in" ,"r" ,stdin);\
freopen(#x".out" ,"w" ,stdout)
#define LL long long
const int MX = 1e5 + 23;
const LL MOD = 998244353;
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
int a[MX];
void solve(){
int n = read() ,l = read() ,r = read();
int ok = 1;
for(int i = 1 ; i <= n ; ++i){
a[i] = ((l - 1) / i + 1) * i;
ok = ok && a[i] <= r;
}
if(ok){
puts("YES");
for(int i = 1 ; i <= n ; ++i)
printf("%d%c" ,a[i] ," \n"[i == n]);
}
else puts("NO");
}
int main(){
int T = read();
for(int i = 1 ; i <= T ; ++i){
solve();
}
return 0;
}
idea: Imakf
Solution
Tutorial is loading...
Code of solution 1
By Imakf
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)\
freopen(#x".in" ,"r" ,stdin);\
freopen(#x".out" ,"w" ,stdout)
#define LL long long
const int MX = 5e5 + 23;
const LL MOD = 998244353;
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
int n ,a[MX] ,q ,choose[MX];
bool check(int mid){
for(int i = 1 ; i <= n ; ++i) choose[i] = 0;
int iq = q;
for(int i = 1 ; i < mid ; ++i)
if(a[i] <= iq) choose[i] = 1;
for(int i = mid ; i <= n ; ++i){
choose[i] = 1;
if(iq == 0) return 0;
if(a[i] > iq) --iq;
}
if(iq < 0) return 0;
return 1;
}
void solve(){
n = read() ,q = read();
for(int i = 1 ; i <= n ; ++i)
a[i] = read();
int l = 1 ,r = n ,mid;
while(l <= r){
mid = (l + r) >> 1;
if(check(mid)) r = mid - 1;
else l = mid + 1;
}
// [r + 1 ,n] is selected
check(r + 1);
for(int i = 1 ; i <= n ; ++i)
printf("%d" ,choose[i]);
puts("");
}
int main(){
int T = read();
for(int i = 1 ; i <= T ; ++i){
solve();
}
return 0;
}
Code of solution 2
By waaitg
#include<cstdio>
int a[100005],b[100005];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n,iq;
scanf("%d%d",&n,&iq);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
int sum=0,nq=0;
for(int i=n;i>=1;--i){
if(a[i]<=nq)b[i]=1;
else if(nq<iq)++nq,b[i]=1;
else b[i]=0;
}
for(int i=1;i<=n;++i)
printf("%d",b[i]);
puts("");
}
return 0;
}
Unfortunately, a harder version of this problem has appeared in a codechef contest here.
In fact, this problem was come up with more than 1 year ago, earlier than the problem in that codechef contest. We are sorry again.
Solution
Tutorial is loading...
Code
By waaitg
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int maxn=100005;
int a[maxn];
int main(){
int T;read(T);
while(T--){
int n;read(n);
for(int i=1;i<=n;++i)read(a[i]);
for(int i=n-1;i>=1;--i){
int pre=a[i+1],ok=false;
for(int j=i;j>=1;--j){
ok=(a[j]==0);
pre-=(a[j]=pre-a[j]);
if(ok){
sort(a+j,a+i+1);
break;
}
}
if(!ok)
sort(a+1,a+i+1);
}
write(a[1]),pc('\n');
}
return 0;
}
/*
_|_|_|_| _|_| _| _| _|_|_|_|_| _|_|_|_|_| _|
_| _| _| _| _|_| _| _| _| _|
_| _| _| _| _| _| _| _| _| _|
_| _| _|_|_|_|_| _| _| _| _| _|_|_|_|_| _|
_| _| _| _| _| _| _| _| _| _|
_| _| _| _| _| _|_| _| _| _|
_|_|_|_| _| _| _| _| _|_|_|_|_| _|_|_|_|_| _|_|_|_|_|
_|_|_|_|_| _| _| _|_|_|_| _| _|
_| _| _| _| _| _| _|
_| _| _| _| _| _| _|
_| _|_| _| _| _|_|
_| _| _| _| _| _|
_| _| _| _| _| _|
_| _| _| _|_|_|_| _|
_| _|_|_| _| _| _|_|_|_|_|
_| _| _| _| _| _|
_| _| _| _| _| _|
_| _| _| _| _| _|_|_|_|_|
_| _| _| _| _| _|
_| _| _| _|_| _|
_|_|_|_|_| _|_|_| _| _|_|_|_|_|
_|_|_|_|_| _| _| _|_|_|_|_|
_| _| _| _|
_| _| _| _|
_| _|_| _|
_| _| _|
_| _| _|
_| _| _|
Created by xiaolilsq.
*/
idea: waaitg
Solution
Tutorial is loading...
Code
By waaitg
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int maxn=100005,maxm=200005;
int par[maxn];
int AC(int x){
return par[x]==x?x:par[x]=AC(par[x]);
}
struct Edge{
int v,nt;
Edge(int v=0,int nt=0):
v(v),nt(nt){}
}e[maxn*2],es[maxm];
int hd[maxn],num;
void qwq(int u,int v){
e[++num]=Edge(v,hd[u]),hd[u]=num;
}
int dp[maxn];
int pa[maxn][20];
void dfs(int u,int p){
pa[u][0]=p;
for(int j=1;(1<<j)<=dp[u];++j)
pa[u][j]=pa[pa[u][j-1]][j-1];
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(v==p)continue;
dp[v]=dp[u]+1;dfs(v,u);
}
}
int jump(int x,int t){
for(int cn=0;t;t>>=1,++cn)
if(t&1)x=pa[x][cn];
return x;
}
int lca(int x,int y){
if(dp[x]>dp[y])x=jump(x,dp[x]-dp[y]);
if(dp[y]>dp[x])y=jump(y,dp[y]-dp[x]);
if(x==y)return x;
for(int t=19;t>=0;--t)
if(pa[x][t]!=pa[y][t])
x=pa[x][t],y=pa[y][t];
return pa[x][0];
}
int vis[maxn];
char s[maxn];
void pushdown(int u,int p){
if(vis[u]==0)s[u]='1';
else s[u]='0';
for(int i=hd[u];i;i=e[i].nt){
int v=e[i].v;
if(v==p)continue;
vis[v]+=vis[u];
pushdown(v,u);
}
}
int main(){
int n,m;
read(n),read(m);
for(int i=1;i<=n;++i)
par[i]=i;
int tp=0;
for(int i=1;i<=m;++i){
int u,v;
read(u),read(v);
if(AC(u)==AC(v)){
es[++tp]=Edge(u,v);
}
else{
par[AC(u)]=AC(v);
qwq(u,v),qwq(v,u);
}
}
int root=1;
dfs(root,0);
for(int i=1;i<=tp;++i){
int u=es[i].v,v=es[i].nt;
if(dp[u]>dp[v])u^=v^=u^=v;
int w=lca(u,v);
if(u==w){
--vis[v];
++vis[jump(v,dp[v]-dp[u]-1)];
}
else{
++vis[root];
--vis[u];
--vis[v];
}
}
pushdown(root,0);
s[n+1]='\0';
printf("%s\n",s+1);
return 0;
}
Solution
Tutorial is loading...
Code
By Imakf
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)\
freopen(#x".in" ,"r" ,stdin);\
freopen(#x".out" ,"w" ,stdout)
#define LL long long
const int MX = 2000 + 23;
LL MOD;
using namespace std;
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
int head[MX] ,tot = 1;
struct edge{
int node ,next;
}h[MX << 1];
void addedge(int u ,int v ,int flg = 1){
// if(flg) debug("%d %d\n" ,u ,v);
h[++tot] = (edge){v ,head[u]} ,head[u] = tot;
if(flg) addedge(v ,u ,false);
}
int n ,dp[MX][MX] ,S[MX][MX] ,suf[MX][MX] ,pre[MX][MX];
void dapai(int x ,int f){
int ch = 0;
for(int i = head[x] ,d ; i ; i = h[i].next){
if((d = h[i].node) == f) continue;
dapai(d ,x);
}
for(int i = head[x] ,d ; i ; i = h[i].next){
if((d = h[i].node) == f) continue;
++ch;
for(int j = 0 ; j <= n ; ++j){
suf[ch][j] = pre[ch][j] = S[d][j];
}
}
if(!ch){
for(int i = 1 ; i <= n ; ++i){
dp[x][i] = 1 % MOD;
S[x][i] = (S[x][i - 1] + dp[x][i]) % MOD;
}
return ;
}
for(int j = 0 ; j <= n ; ++j){
for(int i = 1 ; i <= ch ; ++i)
pre[i][j] = 1LL * pre[i][j] * pre[i - 1][j] % MOD;
for(int i = ch ; i >= 1 ; --i)
suf[i][j] = 1LL * suf[i][j] * suf[i + 1][j] % MOD;
}
for(int i = 1 ; i <= n ; ++i) dp[x][i] = pre[ch][i];
if(x != 1) for(int i = head[x] ,d ,c = 0 ; i ; i = h[i].next){
if((d = h[i].node) == f) continue;
++c;
LL sum = 0;
for(int mx = 1 ; mx <= n ; ++mx){
dp[x][mx] = (dp[x][mx] + sum * dp[d][mx]) % MOD;
sum = (sum + 1LL * pre[c - 1][mx] * suf[c + 1][mx]) % MOD;
}
}
for(int i = 1 ; i <= ch ; ++i)
for(int j = 0 ; j <= n ; ++j)
suf[i][j] = pre[i][j] = 1 % MOD;
for(int i = 1 ; i <= n ; ++i)
S[x][i] = (S[x][i - 1] + dp[x][i]) % MOD;
}
int C[MX][MX];
void init(){
for(int i = 0 ; i < MX ; ++i) C[i][0] = 1 % MOD;
for(int i = 1 ; i < MX ; ++i)
for(int j = 1 ; j < MX ; ++j)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
int main(){
n = read() ,MOD = read();
init();
for(int i = 0 ; i < MX ; ++i)
for(int j = 0 ; j < MX ; ++j)
suf[i][j] = pre[i][j] = 1 % MOD;
for(int i = 2 ; i <= n ; ++i){
addedge(read() ,read());
// addedge(rand() % (i - 1) + 1 ,i);
}
dapai(1 ,0);
for(int i = 1 ; i < n ; ++i){
LL ans = 0;
for(int j = 1 ; j <= i ; ++j){
ans += ((i - j) & 1 ? -1LL : 1LL) * C[i][j] * dp[1][j] % MOD;
}
ans = (ans % MOD + MOD) % MOD;
printf("%lld%c" ,ans ," \n"[i == n]);
}
return 0;
}
Solution
Tutorial is loading...
Code
By waaitg
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
static char c;static int f;
for(f=1,c=ch();c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch()){x=x*10+(c&15);}x*=f;
}
template<typename T>void write(T x){
static char q[64];int cnt=0;
if(x==0)return pc('0'),void();
if(x<0)pc('-'),x=-x;
while(x)q[cnt++]=x%10+'0',x/=10;
while(cnt--)pc(q[cnt]);
}
const int maxn=100005,maxq=100005,maxt=34;
const int inf=0x3f3f3f3f;
int a[maxn];
struct Segment{
int l,r;
Segment(int l=inf,int r=-inf):
l(l),r(r){}
Segment operator * (const Segment o)const{
return Segment(min(l,o.l),max(r,o.r));
}
bool operator != (const Segment o)const{
return l!=o.l||r!=o.r;
}
void input(void){
read(l),read(r);
}
}sg[maxt][maxn],tr[maxn],qy[maxq];
int n;
void res(void){
for(int i=1;i<n;++i)
tr[i]=Segment();
}
void add(int p,Segment v){
while(p<n){
tr[p]=tr[p]*v;
p+=(p&(-p));
}
}
Segment ask(int p){
Segment re;
while(p){
re=re*tr[p];
p^=(p&(-p));
}
return re;
}
struct Edge{
int v,w,nt;
Edge(int v=0,int w=0,int nt=0):
v(v),w(w),nt(nt){}
}e[maxn];
int num,hd[maxn];
void ins(int u,int v,int w){
e[++num]=Edge(v,w,hd[u]),hd[u]=num;
}
int st[maxq],tp;
long long Ans[maxq];
int main(){
int q;read(n),read(q);
if(n==1){while(q--)puts("0");return 0;}
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1;i<n;++i){
if(a[i]<=a[i+1])
sg[0][i]=Segment(a[i],a[i+1]);
else
sg[0][i]=Segment(a[i+1],a[i]);
}
for(int i=1;i<maxt;++i){
for(int j=1;j<n;++j){
if(sg[i-1][j].l>=sg[i-1][j].r)sg[i][j]=Segment();
else ins(sg[i-1][j].l,sg[i-1][j].r-1,j);
}
res();
for(int j=n-1;j>=1;--j){
add(j,sg[i-1][j]);
for(int k=hd[j];k;k=e[k].nt){
sg[i][e[k].w]=ask(e[k].v);
}
hd[j]=0;
}
num=0;
}
for(int i=1;i<=q;++i){
qy[i].input();
if(qy[i].l==qy[i].r)Ans[i]=-2;
else ins(qy[i].l,qy[i].r-1,i);
}
res();
for(int i=n-1;i>=1;--i){
add(i,sg[maxt-1][i]);
for(int j=hd[i];j;j=e[j].nt){
if(i==1&&e[j].v==n-1)
Ans[e[j].w]=-1;
else if(ask(e[j].v)!=Segment(1,n))
Ans[e[j].w]=-2;
else
st[++tp]=e[j].w;
}
hd[i]=0;
}
num=0;
for(int i=maxt-2;~i;--i){
for(int j=1;j<=tp;++j){
ins(qy[st[j]].l,qy[st[j]].r-1,st[j]);
}
res();
for(int j=n-1;j>=1;--j){
add(j,sg[i][j]);
for(int k=hd[j];k;k=e[k].nt){
Segment tmp=ask(e[k].v);
int id=e[k].w;
if(tmp!=Segment(1,n))
Ans[id]|=(1ll<<i),qy[id]=tmp;
}
hd[j]=0;
}
num=0;
}
for(int i=1;i<=q;++i)
write(++Ans[i]),pc('\n');
return 0;
}
This is a noun almost one year ago when this problem came out.
Solution
Tutorial is loading...
Code
By waaitg
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<assert.h>
#define ch() getchar()
#define pc(x) putchar(x)
template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
const int maxn=20000005;
struct Count{
int pos,val;
Count(int pos=-1,int val=-1):
pos(pos),val(val){}
};
int plus(int x,int y){
return (x<0||y<0)?-1:x+y;
}
Count operator + (const Count A,const Count B){
int Ap=A.pos,Bp=B.pos,va=plus(A.val,B.val);
if(~Ap&&~Bp)return Ap^Bp?Count():Count(Ap|Bp,va);
if(~Ap||~Bp)return Count(Ap&Bp,va);
return Count(-1,va);
}
Count operator * (const Count A,const Count B){
int Ap=A.pos,Bp=B.pos,va=plus(A.val,B.val);
if(~Ap&&~Bp)return Count(Ap^Bp,va);
if(~Ap||~Bp)return Count(-1,va);
return Count(-1,plus(va,1));
}
int c[maxn];
int tn,Op[maxn],Cn[maxn];
Count dp[maxn];
int t,hb[maxn],rev[maxn];
void pushup(int p){
int l=p<<1,r=l|1;
dp[p]=((t&hb[p])?(dp[l]+dp[r]):(dp[l]*dp[r]));
}
int va1,sum;
void ins(int i){
int p=rev[(i&(tn-1))];
if(~c[i])Op[p]^=c[i];else ++Cn[p];
if(dp[p+tn].pos>0)--va1;else sum-=dp[p+tn].val;
dp[p+tn]=(Cn[p]?Count(-1,Cn[p]-1):Count(Op[p],0));
if(dp[p+tn].pos>0)++va1;else sum+=dp[p+tn].val;
}
void del(int i){
int p=rev[(i&(tn-1))];
if(~c[i])Op[p]^=c[i];else --Cn[p];
}
int power(int a,int x,int p){
if(x==-1)return 0;
int re=1;
while(x){
if(x&1)re=1ll*re*a%p;
a=1ll*a*a%p;x>>=1;
}
return re;
}
int main(){
int n,m,w;
read(n),read(m),read(t),read(w);
memset(c,-1,sizeof c);
for(int i=1;i<=m;++i){
int d;read(d);--d;read(c[d]);
}
tn=(n&(-n));
hb[0]=0;hb[1]=1;
for(int i=2;i<tn*2;++i)
hb[i]=(hb[i>>1]<<1);
int cn=-1;for(;(1<<(cn+1))<tn;++cn);
for(int i=1;i<tn;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)<<cn);
for(int i=0;i<tn;++i)dp[i+tn].val=0;
for(int i=0;i<n;++i)ins(i);
if(t<tn)for(int i=tn-1;i>=1;--i)pushup(i);
int q;read(q);
while(q--){
int f;read(f);--f;
del(f);read(c[f]);ins(f);
int p;read(p);
if(t>=tn){
write(va1?0:power((1<<w)%p,sum,p));
}
else{
int now=(rev[(f&(tn-1))]|tn);while(now>>=1)pushup(now);
write(power((1<<w)%p,plus(dp[1].val,dp[1].pos==-1),p));
}
pc('\n');
}
return 0;
}