Idea: FieryPhoenix
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n,x;
int w[101];
cin>>n>>x;
int sum=0;
for (int i=0;i<n;i++){
cin>>w[i];
sum+=w[i];
}
//if the sum is x, we cannot avoid the explosion
if (sum==x){
cout<<"NO"<<endl;
return;
}
cout<<"YES"<<endl;
//otherwise, the answer always exists
//we will keep adding elements from left to right
//if we can't add element i, we add element i+1 first by swapping the two
for (int i=0;i<n;i++){
if (x==w[i]){
//i+1 will always be less than n because otherwise, the total sum would be x
swap(w[i],w[i+1]);
}
cout<<w[i]<<' ';
x-=w[i];
}
cout<<endl;
return;
}
int main(){
int T; cin>>T;
while (T--)
solve();
return 0;
}
Idea: FieryPhoenix
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
bool isSquare(int x){
int y=sqrt(x);
return y*y==x;
}
void solve(){
int n;
cin>>n;
if (n%2==0 && isSquare(n/2))
cout<<"YES"<<endl;
else if (n%4==0 && isSquare(n/4))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
int main(){
int t; cin>>t;
while (t--)
solve();
}
Idea: FieryPhoenix
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int N,M,X;
int H[100001];
void solve(){
cin>>N>>M>>X;
cout<<"YES"<<endl;
set<pair<int,int>>s; //stores pairs of (height, index)
for (int i=1;i<=M;i++)
s.insert({0,i});
for (int i=0;i<N;i++){
cin>>H[i];
pair<int,int>p=*s.begin();
s.erase(p);
cout<<p.second<<' ';
s.insert({p.first+H[i],p.second});
}
cout<<endl;
}
int main(){
int T; cin>>T;
while (T--)
solve();
}
Idea: FieryPhoenix
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int N,L,R;
int C[200001];
int lcnt[200001],rcnt[200001];
void solve(){
cin>>N>>L>>R;
for (int i=1;i<=N;i++){
lcnt[i]=0;
rcnt[i]=0;
}
for (int i=1;i<=N;i++){
cin>>C[i];
if (i<=L)
lcnt[C[i]]++;
else
rcnt[C[i]]++;
}
//remove pairs that are already matching
for (int i=1;i<=N;i++){
int mn=min(lcnt[i],rcnt[i]);
lcnt[i]-=mn;
rcnt[i]-=mn;
L-=mn;
R-=mn;
}
if (L<R){
swap(lcnt,rcnt);
swap(L,R);
}
//now, there are at least as many left socks as right socks
int ans=0;
for (int i=1;i<=N;i++){
int extra=L-R; //always even
int canDo=lcnt[i]/2;
int Do=min(canDo*2,extra);
//turn "Do"/2 left socks of color i into right socks
ans+=Do/2;
L-=Do;
}
//turn extra lefts into rights, then adjust all colors
ans+=(L-R)/2+(L+R)/2;
cout<<ans<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
int T; cin>>T;
while (T--)
solve();
return 0;
}
Idea: FieryPhoenix
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD;
int N;
ll dp[405][405];
ll fastexp(ll b, ll exp){
if (exp==0)
return 1;
ll temp=fastexp(b,exp/2);
temp=(temp*temp)%MOD;
if (exp%2==1)
temp*=b;
return temp%MOD;
}
ll fact[405],inv[405],choose[405][405],pow2[405];
void precompute(){
fact[0]=1;
inv[0]=1;
for (int i=1;i<=N;i++){
fact[i]=(fact[i-1]*i)%MOD;
inv[i]=fastexp(fact[i],MOD-2);
}
for (int i=0;i<=N;i++)
for (int j=0;j<=i;j++)
choose[i][j]=((fact[i]*inv[j])%MOD*inv[i-j])%MOD;
for (int i=0;i<=N;i++)
pow2[i]=fastexp(2,i);
}
int main()
{
cin>>N>>MOD;
precompute();
dp[0][0]=1;
for (int i=0;i<N;i++){
for (int j=0;j<=i;j++){
for (int k=1;i+k<=N;k++){
dp[i+k+1][j+k]+=((dp[i][j]*pow2[k-1])%MOD*choose[j+k][k]);
dp[i+k+1][j+k]%=MOD;
}
}
}
ll ans=0;
for (int i=0;i<=N;i++)
ans=(ans+dp[N+1][i])%MOD;
cout<<ans<<endl;
return 0;
}
1515F - Phoenix and Earthquake
Idea: dragonslayerintraining
Tutorial
Tutorial is loading...
Solution
// Fix a spanning tree
// Pick a leaf, either merge it into its parent or postpone it to the end
#include <cstdio>
#include <vector>
#include <algorithm>
const int MAXV=300005;
const int MAXE=300005;
int N,M,X;
long long as[MAXV];
int elist[MAXE*2];
int head[MAXV];
int prev[MAXE*2];
int tot=0;
bool vis[MAXV];
int ans[MAXV];
int front,back;
void dfs(int u){
vis[u]=true;
for(int e=head[u];e!=-1;e=prev[e]){
int v=elist[e^1];
if(vis[v]) continue;
dfs(v);
if(as[u]+as[v]>=X){
as[u]+=as[v]-X;
ans[front++]=e>>1;
}else{
ans[--back]=e>>1;
}
}
}
int main(){
scanf("%d %d %d",&N,&M,&X);
long long total=0;
for(int i=0;i<N;i++){
scanf("%lld",&as[i]);
total+=as[i];
}
if(total<1LL*(N-1)*X){
printf("NO\n");
return 0;
}
std::fill(head,head+N,-1);
for(int i=0;i<M*2;i++){
int U;
scanf("%d",&U);
U--;
prev[i]=head[U];
head[U]=i;
elist[i]=U;
}
back=N-1;
dfs(0);
printf("YES\n");
for(int i=0;i<N-1;i++){
printf("%d\n",ans[i]+1);
}
}
Idea: dragonslayerintraining
Tutorial
Tutorial is loading...
Solution
#include <cstdio>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cmath>
using ll = long long;
std::vector<std::pair<int,int> > fwd[200005];
std::vector<std::pair<int,int> > rev[200005];
int vis[200005];
int cc[200005];
ll offset[200005];
int ncc;
ll loop[200005];
std::vector<int> ord;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
void dfs_fwd(int x){
vis[x]=1;
for(auto e:fwd[x]){
int y=e.first;
if(vis[y]!=1){
dfs_fwd(y);
}
}
ord.push_back(x);
}
void dfs_rev(int x){
vis[x]=2;
for(auto e:rev[x]){
int y=e.first,l=e.second;
if(vis[y]!=2){
cc[y]=cc[x];
offset[y]=offset[x]+l;
dfs_rev(y);
}else if(cc[y]==cc[x]){
loop[cc[x]]=gcd(loop[cc[x]],std::llabs(offset[x]+l-offset[y]));
}
}
}
int main(){
int N,M;
scanf("%d %d",&N,&M);
for(int i=0;i<M;i++){
int A,B,L;
scanf("%d %d %d",&A,&B,&L);
A--,B--;
fwd[A].push_back({B,L});
rev[B].push_back({A,L});
}
for(int i=0;i<N;i++){
if(vis[i]!=1){
dfs_fwd(i);
}
}
std::reverse(ord.begin(),ord.end());
for(int i:ord){
if(vis[i]!=2){
cc[i]=ncc++;
offset[i]=0;
dfs_rev(i);
}
}
int Q;
scanf("%d",&Q);
for(int i=0;i<Q;i++){
int V,S,T;
scanf("%d %d %d",&V,&S,&T);
V--;
assert(0<=S&&S<T);
if(S%gcd(loop[cc[V]],T)==0){
printf("YES\n");
}else{
printf("NO\n");
}
}
}
Idea: dragonslayerintraining
Tutorial
Tutorial is loading...
Solution
#include <cstdio>
#include <cassert>
#include <utility>
#include <functional>
//numbers up to 2^MAXLOGX-1
const int MAXLOGX=20;
template<int k>
struct Trie{
Trie<k-1>* chd[2];
int cnt;
int lazy;
int has[2];
int get_cnt(){
assert(this!=NULL);
return cnt;
}
int get_has(int d){
assert(this!=NULL);
push();
assert(has[d]<(1<<(k+1)));
return has[d];
}
Trie(Trie<k-1>* l,Trie<k-1>* r):chd{l,r},cnt(0),lazy(0),has{0,0}{
if(l){
cnt+=l->get_cnt();
has[0]|=l->get_has(0)|(1<<k);
has[1]|=l->get_has(1);
}
if(r){
cnt+=r->get_cnt();
has[0]|=r->get_has(0);
has[1]|=r->get_has(1)|(1<<k);
}
assert(has[0]<(1<<(k+1)));
assert(has[1]<(1<<(k+1)));
}
void push(){
assert(lazy<(1<<(k+1)));
if(!lazy) return;
//handle kth bit
if(lazy&(1<<k)){
std::swap(chd[0],chd[1]);
if((has[0]^has[1])&(1<<k)){
has[0]^=(1<<k);
has[1]^=(1<<k);
}
lazy^=(1<<k);
}
//handle rest of bits
int flip=(has[0]^has[1])&lazy;
has[0]^=flip;
has[1]^=flip;
if(chd[0]) chd[0]->lazy^=lazy;
if(chd[1]) chd[1]->lazy^=lazy;
lazy=0;
assert(has[0]<(1<<(k+1)));
assert(has[1]<(1<<(k+1)));
}
};
template<>
struct Trie<-1>{
int lazy;
Trie():lazy(0){
}
int get_cnt(){
assert(this!=NULL);
return 1;
}
int get_has(int d){
assert(this!=NULL);
return 0;
}
};
template<int k>
Trie<k>* create(int x){
if(x&(1<<k)){
return new Trie<k>(NULL,create<k-1>(x));
}else{
return new Trie<k>(create<k-1>(x),NULL);
}
}
template<>
Trie<-1>* create(int x){
return new Trie<-1>();
}
template<int k>
std::pair<Trie<k-1>*,Trie<k-1>*> destruct(Trie<k>* a){
assert(a!=NULL);
a->push();
auto res=std::make_pair(a->chd[0],a->chd[1]);
delete a;
return res;
}
template<int k>
Trie<k>* join(Trie<k-1>* l,Trie<k-1>* r){
if(l==NULL&&r==NULL) return NULL;
return new Trie<k>(l,r);
}
template<int k>
Trie<k>* merge(Trie<k>* a,Trie<k>* b){
if(!a) return b;
if(!b) return a;
auto aa=destruct(a);
auto bb=destruct(b);
Trie<k-1>* l=merge<k-1>(aa.first,bb.first);
Trie<k-1>* r=merge<k-1>(aa.second,bb.second);
return join<k>(l,r);
}
template<>
Trie<-1>* merge<-1>(Trie<-1>* a,Trie<-1>* b){
if(!a) return b;
if(!b) return a;
delete b;
return a;
}
template<int k>
//<thres and >=thres
std::pair<Trie<k>*,Trie<k>*> split(Trie<k>* a,int thres){
if(a==NULL){
return {NULL,NULL};
}
if(thres<=0) return {NULL,a};
if(thres>=(1<<(k+1))) return {a,NULL};
assert(k>=0);
auto aa=destruct(a);
if(thres<(1<<k)){
Trie<k-1>* l,*r;
std::tie(l,r)=split<k-1>(aa.first,thres);
return std::make_pair(join<k>(l,NULL),join<k>(r,aa.second));
}else if(thres>(1<<k)){
Trie<k-1>* l,*r;
std::tie(l,r)=split<k-1>(aa.second,thres-(1<<k));
return std::make_pair(join<k>(aa.first,l),join<k>(NULL,r));
}else{
return std::make_pair(join<k>(aa.first,NULL),join<k>(NULL,aa.second));
}
}
template<>
std::pair<Trie<-1>*,Trie<-1>*> split<-1>(Trie<-1>* a,int thres){
assert(0);
}
template<int k>
Trie<k>* update(Trie<k>* a,int val){
if(a==NULL) return NULL;
a->push();
assert(val<(1<<(k+1)));
if((val&a->has[0]&a->has[1])==0){
a->lazy^=(val&a->has[0]);
return a;
}
Trie<k-1>* l,*r;
std::tie(l,r)=destruct(a);
l=update<k-1>(l,val&~(1<<k));
r=update<k-1>(r,val&~(1<<k));
if(val&(1<<k)){
return join<k>(NULL,merge<k-1>(l,r));
}else{
return join<k>(l,r);
}
}
template<>
Trie<-1>* update<-1>(Trie<-1>* a,int val){
return a;
}
int main(){
Trie<MAXLOGX-1>* root=NULL;
int N,Q;
scanf("%d %d",&N,&Q);
for(int i=0;i<N;i++){
int A;
scanf("%d",&A);
root=merge(root,create<MAXLOGX-1>(A));
}
for(int i=0;i<Q;i++){
int T,L,R;
scanf("%d %d %d",&T,&L,&R);
Trie<MAXLOGX-1>* left,*right;
std::tie(left,root)=split(root,L);
std::tie(root,right)=split(root,R+1);
if(T==4){
printf("%d\n",root?root->cnt:0);
}else{
int X;
scanf("%d",&X);
if(root!=NULL){
if(T==1){
root->lazy^=((1<<MAXLOGX)-1);
root=update(root,X^((1<<MAXLOGX)-1));
root->lazy^=((1<<MAXLOGX)-1);
}else if(T==2){
root=update(root,X);
}else if(T==3){
assert(X<(1<<MAXLOGX));
root->lazy^=X;
}
}
}
root=merge(root,left);
root=merge(root,right);
}
}
Idea: dragonslayerintraining
Tutorial
Tutorial is loading...
Solution
#include <cstdio>
#include <algorithm>
#include <functional>
#include <utility>
#include <numeric>
#include <cassert>
using ll=long long;
const ll INF=1e18+7;
struct Diamond{
int w,v,t;
ll a;
}diamonds[200005];
int index[200005];
int N;
struct Node{
ll sum_w[31];//sum of weights of all diamonds with weight <2^k
ll sum_v[31];//sum of values of all diamonds with weight <2^k
ll one_w[31];//sum of weights of light+first heavy when restricted to <2^k
ll one_v[31];//sum of values of light+first heavy when restricted to <2^k
}st[800005];
void rebuild(int w,int L,int R,int a,int b){
if(a>=R||b<=L) return;
if(R-L==1){
for(int k=1;k<=30;k++){
st[w].sum_w[k]=diamonds[L].a*diamonds[L].w*(diamonds[L].w<(1<<k));
st[w].sum_v[k]=diamonds[L].a*diamonds[L].v*(diamonds[L].w<(1<<k));
st[w].one_w[k]=INF;//query capacity never exceed INF
st[w].one_v[k]=INF;
if(diamonds[L].w>=(1<<(k-1))&&diamonds[L].w<(1<<k)&&diamonds[L].a>0){
st[w].one_w[k]=diamonds[L].w;
st[w].one_v[k]=diamonds[L].v;
}
}
}else{
int M=(L+R)/2;
rebuild(w*2+1,L,M,a,b);
rebuild(w*2+2,M,R,a,b);
for(int k=1;k<=30;k++){
st[w].sum_w[k]=st[w*2+1].sum_w[k]+st[w*2+2].sum_w[k];
st[w].sum_v[k]=st[w*2+1].sum_v[k]+st[w*2+2].sum_v[k];
if(st[w*2+1].one_w[k]<st[w*2+1].sum_w[k-1]+st[w*2+2].one_w[k]){
st[w].one_w[k]=st[w*2+1].one_w[k];
st[w].one_v[k]=st[w*2+1].one_v[k];
}else{
st[w].one_w[k]=st[w*2+1].sum_w[k-1]+st[w*2+2].one_w[k];
st[w].one_v[k]=st[w*2+1].sum_v[k-1]+st[w*2+2].one_v[k];
}
}
}
}
//only consider weights <2^k
//take maximal prefix possible
void query_all(int w,int L,int R,int& i,int k,ll& cap,ll& value){
assert(i>=L&&i<=R);
assert(R-L>0);
if(i==R) return;
if(i==L&&st[w].sum_w[k]<=cap){
cap-=st[w].sum_w[k];
value+=st[w].sum_v[k];
i=R;
}else if(R-L>1){
int M=(L+R)/2;
if(i<M){
query_all(w*2+1,L,M,i,k,cap,value);
}
if(i>=M){
query_all(w*2+2,M,R,i,k,cap,value);
}
}
}
std::array<ll,2> query_one_range_simpl(int w,int L,int R,int a,int b,int k){
if(a>=R||b<=L) return {INF,0};
if(a<=L&&b>=R){
return {st[w].one_w[k],st[w].sum_w[k-1]};
}else{
int M=(L+R)/2;
std::array<ll,2> lsum,rsum;
lsum=query_one_range_simpl(w*2+1,L,M,a,b,k);
rsum=query_one_range_simpl(w*2+2,M,R,a,b,k);
if(lsum[0]<lsum[1]+rsum[0]){
return {lsum[0],lsum[1]+rsum[1]};
}else{
return {lsum[1]+rsum[0],lsum[1]+rsum[1]};
}
}
}
std::array<ll,4> query_one_range(int w,int L,int R,int a,int b,int k){
if(a>=R||b<=L) return {INF,INF,0,0};
if(a<=L&&b>=R){
return {st[w].one_w[k],st[w].one_v[k],st[w].sum_w[k-1],st[w].sum_v[k-1]};
}else{
int M=(L+R)/2;
std::array<ll,4> lsum,rsum;
lsum=query_one_range(w*2+1,L,M,a,b,k);
rsum=query_one_range(w*2+2,M,R,a,b,k);
if(lsum[0]<lsum[2]+rsum[0]){
return {lsum[0],lsum[1],lsum[2]+rsum[2],lsum[3]+rsum[3]};
}else{
return {lsum[2]+rsum[0],lsum[3]+rsum[1],lsum[2]+rsum[2],lsum[3]+rsum[3]};
}
}
}
//returns min j such that one_w[i..j) <= cap, or -1 if none exist
//reduce cap by weight of light in [max(i,L),R)
int query_one_range_search_(int w,int L,int R,int& i,int k,ll& cap){
assert(i>=L&&i<=R);
assert(R-L>0);
if(i==R) return -1;
if(i==L&&st[w].one_w[k]>cap){
cap-=st[w].sum_w[k-1];
i=R;
return -1;
}else if(R-L==1){
assert(i==L);
assert(st[w].one_w[k]<=cap);
cap-=st[w].sum_w[k-1];
i=R;
return R;
}else{
int M=(L+R)/2;
int res=-1;
if(i<M){
res=query_one_range_search_(w*2+1,L,M,i,k,cap);
}
if(res!=-1) return res;
if(i>=M){
res=query_one_range_search_(w*2+2,M,R,i,k,cap);
}
return res;
}
}
int query_one_range_search(int i,int k,ll cap){
//note this copy of cap will be modified
return query_one_range_search_(0,0,N,i,k,cap);
}
void query_one(int& L,int k,ll& cap,ll& value){
int high=query_one_range_search(L,k,cap);
//v[high]<=cap
if(high!=-1){
auto v=query_one_range(0,0,N,L,high,k);
L=high;
cap-=v[0];
value+=v[1];
}
}
ll query(ll cap){
ll value=0;
int i=0;
for(int k=30;k>0;k--){
query_all(0,0,N,i,k,cap,value);
if(i==N) break;
ll take=std::min(diamonds[i].a,cap/diamonds[i].w);
cap-=take*diamonds[i].w;
value+=take*diamonds[i].v;
i++;
query_one(i,k,cap,value);
}
return value;
}
int main(){
int Q;
scanf("%d %d",&N,&Q);
for(int i=0;i<N;i++){
scanf("%lld %d %d",&diamonds[i].a,&diamonds[i].w,&diamonds[i].v);
diamonds[i].t=i;
}
std::sort(diamonds,diamonds+N,[](Diamond x,Diamond y){
return (x.v!=y.v)?(x.v>y.v):(x.w<y.w);
});
for(int i=0;i<N;i++){
index[diamonds[i].t]=i;
}
rebuild(0,0,N,0,N);
for(int i=0;i<Q;i++){
int T;
scanf("%d",&T);
if(T==1){
int K,D;
scanf("%d %d",&K,&D);
D--;
diamonds[index[D]].a+=K;
rebuild(0,0,N,index[D],index[D]+1);
}else if(T==2){
int K,D;
scanf("%d %d",&K,&D);
D--;
diamonds[index[D]].a-=K;
assert(diamonds[index[D]].a>=0);
rebuild(0,0,N,index[D],index[D]+1);
}else{
ll C;
scanf("%lld",&C);
printf("%lld\n",query(C));
}
}
}