By Cocoly1990

// Time complexity O(nlogn) because of map
#include <bits/stdc++.h>

const int MX = 100 + 5;

int main() {
  int t;
  std::cin >> t;
  while (t--) {
    int n;
    std::cin >> n;
    std::map<int ,int> occ;
    for (int i = 1; i <= n; ++i) {
      int x;
      std::cin >> x;
      occ[x]++;
    }
    if (occ.size() >= 3) puts("No");
    else {
      if (std::abs(occ.begin()->second - occ.rbegin()->second) <= 1) {
        puts("Yes");
      } else {
        puts("No");
      }
    }
  }
  return 0;
}

By Imakf

#include <bits/stdc++.h>

bool ok(std::string s) {
  for (size_t i = 1; i < s.length(); ++i)
    if (s[i] == s[i - 1])
      return false;
  return true;
}

void solve() {
  std::string s, t;
  int l1, l2;
  std::cin >> l1 >> l2;
  std::cin >> s >> t;
  if (ok(s)) {
    std::cout << "Yes" << std::endl;
    return;
  }

  if (!ok(t) || *t.begin() != *t.rbegin()) {
    std::cout << "No" << std::endl;
    return;
  }

  int zz = 0, oo = 0;
  for (size_t i = 1; i < s.length(); ++i) {
    if (s[i] == s[i - 1]) {
      if (s[i] == '0') zz = true;
      if (s[i] == '1') oo = true;
    }
  }

  if (zz && t[0] == '0') {
    std::cout << "No" << std::endl;
    return;
  }
  if (oo && t[0] == '1') {
    std::cout << "No" << std::endl;
    return;
  }  

  std::cout << "Yes" << std::endl;
  return;
}

int main() {
  int t;
  std::cin >> t;
  while (t--) solve();
  return 0;
}

By Imakf

#include <bits/stdc++.h>

bool ok(std::string s) {
  for (size_t i = 1; i < s.length(); ++i)
    if (s[i] == s[i - 1])
      return false;
  return true;
}


std::string s;
void solve() {
  int n; std::cin >> n;
  std::cin >> s;
  int cnt0 = 0, cnt1 = 0;
  for (int i = 0; i < s.length(); ++i) {
    cnt0 += s[i] == '0';
    cnt1 += s[i] == '1';
  }
  if (cnt0 != cnt1) {
    std::cout << -1 << std::endl;
    return;
  }
  std::vector<int> z;
  std::deque<char> q;
  for (int i = 0; i < s.length(); ++i)
    q.push_back(s[i]);
  
  int d = 0;
  while (!q.empty()) {
    if (q.front() == q.back()) {
      if (q.front() == '0') {
        q.push_back('0');
        q.push_back('1');
        z.push_back(n - d);
      } else {
        q.push_front('1');
        q.push_front('0');
        z.push_back(0 + d);
      }
      n += 2;
    }
    while (!q.empty() && q.front() != q.back()) {
      q.pop_back();
      q.pop_front();
      ++d;
    }
  }

  std::cout << z.size() << std::endl;
  for (int i = 0; i < z.size(); ++i) {
    std::cout << z[i];
    if (i + 1 == z.size()) std::cout << std::endl;
    else std::cout << " ";
  }
}

int main() {
  int t;
  std::cin >> t;
  while (t--) solve();
  return 0;
}

By Cocoly1990

#include<bits/stdc++.h>
using i64 = long long;
using namespace std;
const int N = 5e5 + 7;
int T, n, C, p[N]; i64 a[N];
void solve () {
	cin >> n >> C;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	iota (p + 1, p + n + 1, 1);
	sort (p + 1, p + n + 1, [&] (const int &u, const int &v) {
		return 1ll * u * C - a[u] < 1ll * v * C - a[v];
	});
	i64 now = a[1];
	for (int i = 1, u; i <= n; i ++) {
		u = p[i];
		if (u == 1) continue;
		if (1ll * u * C > now + a[u]) return cout << "No\n", void ();
		now += a[u];
	}
	return cout << "Yes\n", void ();
}
int main () {
	ios :: sync_with_stdio (false); cin.tie (0); cout.tie (0);
	cin >> T; while (T --) solve ();
}

By Imakf

#include <bits/stdc++.h>

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define LL long long

const int MX = 2e5 + 23;
const int INF = 1e9;

void chkmax(int &x, int y) {
  x = std::max(x, y);
}

struct Interval {
  int l, r;
} I[MX];

bool cmp(int x, int y) {
  return I[x].l > I[y].l;
}

std::vector<int> add[MX], del[MX];
int n, m, k, ban[MX];

int st[21][MX][18], lg[MX];

int query(int d, int l, int r) {
  int len = lg[r - l + 1];
  return std::max(st[d][l][len], st[d][r - (1 << len) + 1][len]);
}

void change(int d, int p, int val) {
  chkmax(st[d][p][0], val);
  for (int i = 1; p - (1 << i) + 1 >= 0; ++i) {
    st[d][p - (1 << i) + 1][i] = std::max(
          st[d][p - (1 << i) + 1][i - 1],
          st[d][p - (1 << (i - 1)) + 1][i - 1]);
  }
}

void init() {
  lg[0] = -1;
  for (int i = 1; i <= n + 1; ++i)
    lg[i] = lg[i - 1] + ((i & -i) == i); 
  for (int i = 1; i <= m; ++i) ban[i] = false;
  for (int i = 1; i <= n + 1; ++i) {
    add[i].clear();
    del[i].clear();
  }
  for (int i = 0; i <= k; ++i)
    for (int j = 0; j <= n; ++j)
      for (int _k = 0; _k < 18; ++_k)
        st[i][j][_k] = -INF;
}

void solve() {
  scanf("%d%d%d", &n, &m, &k);
  init();
  for (int i = 1; i <= m; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    I[i] = (Interval){l, r};
    add[l].push_back(i);
    del[r + 1].push_back(i);
  }
  
  std::vector<int> cur, tmp;

  change(0, 0, 0);
  
  int uncover = 0, ans = 0;
  int cnti = 0;
  for (int i = 1; i <= n; ++i) {
    for (auto j : add[i]) {
      cur.push_back(j);
      ++cnti;
    }

    for (auto j : del[i]) {
      ban[j] = true;
      --cnti;
    }

    if (cnti > k) {
      for (int j = 0; j <= k; ++j)
        change(j, i, -INF);
      continue;
    }

    tmp.clear();
    for (auto j : cur) {
      if (!ban[j]) {
        tmp.push_back(j);
      }
    }
    cur = tmp;
    std::sort(cur.begin(), cur.end(), cmp);
    
    if (cur.empty()) {
      for (int j = 0; j <= k; ++j)
        change(j, i, -INF);
      ++uncover;
      continue;
    }
    
    if (I[cur[0]].l <= i - 1)
      for (int g = 0; g <= k; ++g) {
        int z = query(g, I[cur[0]].l, i - 1);
        chkmax(ans, z + 1);
        change(g, i, z + 1);
      }
    else {
      for (int g = 0; g <= k; ++g) {
        change(g, i, -INF);
      }
    }
    int cp = I[cur[0]].l - 1;
    

    for (int j = 0; j < cur.size(); ++j) {
      if (j + 1 != cur.size() && I[cur[j]].l == I[cur[j + 1]].l)
        continue;
      int np = (j + 1 == cur.size() ? 0 : I[cur[j + 1]].l);
      for (int g = j + 1; g <= k; ++g) {
        int z = query(g - (j + 1), np, cp);
        chkmax(ans, z + 1);
        change(g, i, z + 1);
        // change(root[g], i, z + 1);
      }
      cp = np - 1;
    }
  }
  printf("%d\n", ans + uncover);
}

int main() {
  int t; scanf("%d", &t);

  while (t--) solve();
  return 0;
}

By waaitg

#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100005;
stack<int>s[maxn];
int re[maxn],st[maxn],vis[maxn],tp;
int dfs(int u){
    if(re[u])
        return re[u];
    if(s[u].empty())
        return u;
    if(vis[u]){
        st[tp+1]=0;
        while(st[tp+1]!=u){
            s[st[tp]].pop();
            vis[st[tp]]=0;
            --tp;
        }
        return dfs(u);
    }
    st[vis[u]=++tp]=u;
    return dfs(s[u].top());
}
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int k;scanf("%d",&k);
        while(k--){
            int c;scanf("%d",&c);
            s[i].push(c);
        }
    }
    for(int i=1;i<=n;++i){
        tp=0;int ok=dfs(i);
        for(int j=1;j<=tp;++j)
            re[st[j]]=ok;
        printf("%d%c",ok," \n"[i==n]);
    }
    return 0;
}

By waaitg

#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100005;
struct Edge{
    int v,nt;
    Edge(int v=0,int nt=0):
        v(v),nt(nt){}
}eG[maxn*160];
int hdG[maxn*40],numG;
void qwqG(int u,int v){
    eG[++numG]=Edge(v,hdG[u]);hdG[u]=numG;
}
int tot;
struct AnTree{
    struct Edge{
        int v,nt;
        Edge(int v=0,int nt=0):
            v(v),nt(nt){}
    }e[maxn*2];
    int hd[maxn],num;
    void qwq(int u,int v){
        e[++num]=Edge(v,hd[u]),hd[u]=num;
    }
    int n;
    void init(int n){
        this->n=n;
        for(int i=1;i<n;++i){
            int u,v;
            scanf("%d%d",&u,&v);
            qwq(u,v);qwq(v,u);
        }
    }
    int pa[maxn][20],id[maxn][20],dp[maxn];
    void dfs(int u,int p){
        if(p==0)dp[u]=0;
        for(int i=1;(1<<i)<=dp[u];++i)
            pa[u][i]=pa[pa[u][i-1]][i-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;
            pa[v][0]=u;
            id[v][0]=++tot;
            dfs(v,u);
        }
    }
    int getid(int u,int d){
        int&re=id[u][d];
        if(re)return re;
        re=++tot;
        qwqG(re,getid(u,d-1));
        qwqG(re,getid(pa[u][d-1],d-1));
        return re;
    }
    void link(int x,int u,int v){
        if(dp[u]<dp[v])swap(u,v);
        for(int t=dp[u]-dp[v],cn=0;t;t>>=1,++cn)
            if(t&1)qwqG(x,getid(u,cn)),u=pa[u][cn];
        if(u==v)return;
        int t=0;while(dp[u]>>t)++t;
        while(t--){
            if(pa[u][t]!=pa[v][t]){
                qwqG(x,getid(u,t));
                qwqG(x,getid(v,t));
                u=pa[u][t];v=pa[v][t];
            }
        }
        qwqG(x,getid(u,0));
        qwqG(x,getid(v,0));
    }
    void erase(void){
        for(int i=1;i<=n;++i){
            hd[i]=0,dp[i]=0;int j=0;
            while(pa[i][j])pa[i][j++]=0;
            j=0;while(id[i][j])id[i][j++]=0;
        }
        num=0;
    }
    int parent(int u){
        return pa[u][0];
    }
    int identity(int u){
        return id[u][0];
    }
}T1,T2;
int dfn[maxn*40],low[maxn*40],cnt;
int st[maxn*40],tp,in[maxn*40];
int scc[maxn*40],scn;
int vis[maxn*40];
void tarjan(int u){
    dfn[u]=low[u]=++cnt;
    in[st[++tp]=u]=true;
    for(int i=hdG[u];i;i=eG[i].nt){
        int v=eG[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++scn;
        st[tp+1]=0;
        while(st[tp+1]!=u){
            in[st[tp]]=false;
            scc[st[tp]]=scn;
            --tp;
        }
    }
}
const int mod=1e9+7;
int power(int a,int x){
    int re=1;
    while(x){
        if(x&1)re=1ll*re*a%mod;
        a=1ll*a*a%mod,x>>=1;
    }
    return re;
}
void solve(void){
    int n;scanf("%d",&n);
    T1.init(n);T2.init(n);
    T1.dfs(1,0);T2.dfs(1,0);
    int rec=tot;
    for(int i=2;i<=n;++i){
        T2.link(T1.identity(i),i,T1.parent(i));
        T1.link(T2.identity(i),i,T2.parent(i));
    }
    for(int i=1;i<=tot;++i)
        if(!dfn[i])tarjan(i);
    for(int i=1;i<=rec;++i)
        ++vis[scc[i]];
    int ANS=0;
    for(int i=1;i<=scn;++i){
        if(vis[i])++ANS;
        vis[i]=0;
    }
    for(int u=1;u<=rec;++u){
        if(eG[hdG[u]].nt==0){
            int v=eG[hdG[u]].v;
            if(u<v&&eG[hdG[v]].nt==0){
                if(eG[hdG[v]].v==u){
                    --ANS;
                }
            }
        }
    }
    ANS=power(2,ANS);
    printf("%d\n",ANS);
    for(int i=1;i<=tot;++i){
        hdG[i]=0;
        dfn[i]=low[i]=scc[i]=0;
    }
    tot=cnt=scn=numG=0;
    T1.erase();T2.erase();
}
int main(){
    // freopen("test","r",stdin);
    // freopen("out","w",stdout);
    int T;scanf("%d",&T);
    while(T--)solve();
    return 0;
}

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]);
}
long long gcd(long long a,long long b){
	if(b==0)return a;
	return gcd(b,a%b);
}
struct Frac{
	long long a;
	int b;// a/b
	Frac(long long a=0,int b=1):
		a(a),b(b){}
	bool operator < (const Frac o)const{
		return a*o.b<o.a*b;
	}
	bool operator > (const Frac o)const{
		return a*o.b>o.a*b;
	}
	bool operator == (const Frac o)const{
		return a*o.b==o.a*b;
	}
	void output(){
		printf("%lld/%d",a,b);
	}
};
const int inf=0x3f3f3f3f;
struct Val{
	int p1,p2;Frac v1,v2;
	Val(int p1=inf,int p2=inf,Frac v1=Frac(),Frac v2=Frac()):
		p1(p1),p2(p2),v1(v1),v2(v2){}
	void output(void){
		printf("%d : ",p1);v1.output();puts("");
		printf("%d : ",p2);v2.output();puts("\n");
	}
};
Val Comb(Val A,Val B){
	if(A.p1>B.p1)swap(A,B);
	if(B.v1==A.v1)
		return Val(A.p1,A.p2<B.p2?A.p2:B.p2,A.v1,A.p2<B.p2?A.v2:B.v2);
	return Val(A.p1,A.p2<B.p1?A.p2:B.p1,A.v1,A.p2<B.p1?A.v2:B.v1);
}
const int maxn=10005,maxk=505;
struct Edge{
	int v,nt;
	Edge(int v=0,int nt=0):
		v(v),nt(nt){}
}e[maxn*2];
int hd[maxn],num;
void qwq(int u,int v){
	e[++num]=Edge(v,hd[u]),hd[u]=num;
}
long long sm[maxn];int sz[maxn];
int dp[maxn][maxk],wp[maxn][maxk],k,n;
Val va[maxn][maxk];
void Merge(int x,int l,int r,int L,int R){
	wp[x][0]=0;
	va[x][0]=Comb(va[l][0],va[r][0]);
	L=min(L,k);R=min(R,k);
	int up=min(L+R,k);
	for(int i=1;i<=up;++i){
		int t=wp[x][i]=min(L,i),cl=inf,cr=inf;
		while(t>0&&i-t<R){
			cl=min(cl,dp[l][t]);--t;
			cr=min(cr,dp[r][i-t]);
			if(cr<cl)wp[x][i]=t,cl=cr=inf;
		}
		t=wp[x][i-1];cl=cr=inf;
		if(wp[x][i-1]<wp[x][i]){
			while(t<wp[x][i])cl=min(cl,dp[l][++t]);
			dp[x][i]=cl;
		}
		else{
			while(i-t-1<i-wp[x][i])cr=min(cr,dp[r][i-(t--)]);
			dp[x][i]=cr;
		}
		va[x][i]=Comb(va[l][wp[x][i]],va[r][i-wp[x][i]]);
	}
}
int MN[maxn],rsz[maxn];
long long val[maxn];
void dfs(int u,int p){
	int l=0,fa=0;sm[u]=val[u];
	sz[u]=0;rsz[u]=1;MN[u]=0;
	for(int i=hd[u];i;i=e[i].nt){
		int v=e[i].v;
		if(v==p){fa=i;continue;}dfs(v,u);
		Merge(i,i^1,l,sz[v],sz[u]);
		sm[u]+=sm[v],sz[u]+=sz[v];
		rsz[u]+=rsz[v];
		l=i;
	}
	if(sz[u]==0){
		++sz[u];MN[u]=1;
		va[fa][0]=va[fa][1]=Val(u,inf,val[u]);
		dp[fa][1]=inf;
	}
	else{
		int up=min(sz[u],k);
		for(int i=0;i<=up;++i)
			va[fa][i]=Comb(va[l][i],Val(u,inf,val[u])),dp[fa][i]=dp[l][i];
		Frac tmp(sm[u],rsz[u]);
		for(int i=1;i<=up;++i)
			if(va[fa][i].v1>tmp||(va[fa][i].v1==tmp&&va[fa][i].v2>tmp))
				va[fa][i]=Val(va[fa][i].p1,inf,tmp),MN[u]=i;
		if(MN[u]){
			if(va[fa][0].v1==va[fa][1].v1)
				dp[fa][1]=va[fa][0].p2;
			else
				dp[fa][1]=va[fa][0].p1;
			for(int i=2;i<=MN[u];++i)
				dp[fa][i]=inf;
			if(MN[u]<up){
				if(va[fa][MN[u]].v1==va[fa][MN[u]+1].v1)
					dp[fa][MN[u]+1]=va[fa][MN[u]+1].p2;
				else
					dp[fa][MN[u]+1]=va[fa][MN[u]+1].p1;
			}
		}
	}/*
	int up=min(sz[u],k);
	printf("%d MN:%d\n",u,MN[u]);
	for(int i=1;i<=up;++i)
		printf("dp %d = %d\n",i,dp[fa][i]);*/
}
int st[maxn],ts;
int que[maxn],cnt;
void solve(int u,int p,int sk){
	if(sk==0)return;sk=min(sk,sz[u]);
	if(sk<=MN[u])return st[++ts]=u,void();
	int tnc=cnt;
	for(int i=hd[u];i;i=e[i].nt){
		int v=e[i].v;
		if(v==p)continue;
		que[cnt++]=i;
	}
	for(int j=cnt-1;j>=tnc;--j){
		int i=que[j];
		solve(e[i].v,u,wp[i][sk]);
		sk-=wp[i][sk];
	}
}
void imple(void){
	int r;
	read(n),read(r),read(k);
	for(int i=1;i<=n;++i)
		read(val[i]);
	qwq(r,0);
	for(int i=1;i<n;++i){
		int u,v;read(u),read(v);
		qwq(u,v);qwq(v,u);
	}
	dfs(r,0);
	solve(r,0,k);
	printf("%d\n",ts);
	for(int i=1;i<=ts;++i)
		printf("%d%c",st[i]," \n"[i==ts]);
	for(int i=0;i<=n;++i)hd[i]=0;
	num=cnt=ts=0;
}
int main(){
	// freopen("test","r",stdin);
	int T;read(T);
	while(T--)imple();
	return 0;
}