CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)
A. Beautiful Sequence
int a[N],poi[N]; void solve(){ int n=read(),ans=0; for(int i=1;i<=n;i++){ a[i]=read(); } for(int i=1;i<=n;i++){ if(a[i]<=i)ans=1; } puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
void solve(){ int n=read(),cnt=0; vector<int>ans; if(n%2==0){ cout<<"-1\n"; return ; } while(n>1){ cnt++; n/=2; if(n%2)ans.push_back(2); else ans.push_back(1); } cout<<cnt<<'\n'; for(int i=ans.size()-1;i>=0;i--){ cout<<ans[i]<<' '; } cout<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
#define int long long int a[N]; void solve(){ int n=read(),c=read(),d=read(); map<int,int>mp; for(int i=1;i<=n;i++){ a[i]=read(); // mp[a[i]]++; } sort(a+1,a+1+n); int ans=INF,use=0,lost=0,last=0; for(int i=1;i<=n;i++){ if(last<a[i]){ lost+=a[i]-last-1; use++; last=a[i]; }else { } ans=min(ans,(n-use)*c+lost*d); } ans=min(ans,n*c+d); cout<<ans<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
D. Climbing the Tree
#define int long long void solve(){ int n=read(),trhl=1,trhr=INF; while(n--){ int op=read(); if(op==1){ int a=read(),b=read(),n=read(); int templ=max(1ll,(n-2)*(a-b)+a+1),tempr=(n-1)*(a-b)+a; if(n==1)templ=1; if(templ>trhr||tempr<trhl){ cout<<0<<" "; }else{ cout<<1<<" "; trhl=max(templ,trhl); trhr=min(tempr,trhr); } }else { int a=read(),b=read(); int l=max(trhl-a-1,0ll)/(a-b)+1+1,r=max(trhr-a-1,0ll)/(a-b)+1+1; if(trhl<=a)l=1; if(trhr<=a)r=1; if(l==r){ cout<<l<<' '; }else cout<<-1<<' '; } } cout<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
E. Monsters
原来以为暴力会超时 结果题解说是O(nlog^2n)的
说是一个点 不会出现超过logn次
vector<int>e[N]; int st[N],a[N],n,m; bool bfs(int u){ set< PII > se; se.insert({a[u] , u}); int df=0; while (se.size()){ int t = (*se.begin()).first, s= (*se.begin()).second; st[s]=u; if(t>df){ return df==n; } se.erase(se.begin()); df++; for (auto j:e[s]){ if (st[j]<u){ se.insert({a[j],j}); } } } return df==n; } void solve(){ n=read(),m=read(); int ans=0; for(int i=1;i<=n;i++){ a[i]=read(); st[i]=0; e[i].clear(); } for(int i=1;i<=m;i++){ int x=read(),y=read(); e[x].push_back(y); e[y].push_back(x); } for(int i=1;i<=n;i++){ if(a[i]==0&&st[i]==0){ if(bfs(i)){ puts("YES"); return ; } } } puts("NO"); //puts(ans>0?"Yes":"No"); }