Submission #635170

#	Time	Username	Problem	Language	Result	Execution time	Memory
635170		Yahia_Emara	Spiderman (COCI20_spiderman)	C++17	70 / 70	127 ms	21128 KiB

spiderman

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ordered_set tree<pair<lng,lng>,null_type,less<pair<lng,lng>>,rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<double,null_type,less<double>,rb_tree_tag,tree_order_statistics_node_update>
#define rtr return 0
#define lng long long
#define double long double
#define endl "\n"
#define pb push_back
#define cmbntrcs fact[0]=1;for(int i=1;i<INF;i++){fact[i]=mul(i,fact[i-1]);}inv[INF-1]=mod_inv(fact[INF-1]);for(int i=INF-2;i>=0;i--){inv[i]=mul(inv[i+1],i+1);}
///#pragma GCC optimize(Ofast,unroll-all-loops)
const int INF=1e6+7,SZ=3e5+7,MSZ=1e5+3,MAXA=6e5+7;
int MOD=998244353;
int add(int x,int y){int z=x+y;if(z>=MOD){z-=MOD;}return z;}
int sub(int x,int y){int z=x-y;if(z<0){z+=MOD;}return z;}
int mul(int x,int y){return(x*1ll*y)%MOD;}
int pwr(int a,lng b)
{
 int rs=1;
 while(b>0){if(b&1){rs=mul(rs,a);}a=mul(a,a);b>>=1;}
 return rs;
}
int mod_inv(int a){return pwr(a,MOD-2);}
int fact[INF],inv[INF];
int nCr(int n,int r){if(r>n||r<0||n<0){return 0;}return mul(fact[n],mul(inv[r],inv[n-r]));}
int nPr(int n,int r){if(r>n||r<0||n<0){return 0;}return mul(fact[n],inv[n-r]);}
int nPrvc(vector<int>r)
{
 int den=1,n=0;
 for(int i=0;i<r.size();i++){den=mul(den,inv[r[i]]);n+=r[i];}
 return mul(fact[n],den);
}
int sb(int s,int b){if(s<0||b<0){return 0;}return nCr(s+b-1,s);}
int prfx(int i,int j){if(i<0||j<0){return 0;}return nCr(i+j,i);}
int nCrL(int x,int y)
{
 int rt=1;for(int i=x;i>x-y;i--){rt=mul(rt,i);}
 int dn=1;for(int i=1;i<=y;i++){dn=mul(dn,i);}
 return mul(rt,mod_inv(dn));
}
lng lcm(lng x,lng y){return((x/__gcd(x,y))*y);}
lng trig(lng x){return x*(x+1)/2;}
lng pent(lng x){return(x*((3*x)-1))/2;}
lng sigma(lng x,lng y){return trig(y)-trig(x-1);}
pair<double,double>quad(double a,double b,double c)
{
 double disc=(b*b)-(4*a*c);
 if(disc<0){return{-1e16,-1e16};}
 return{(sqrt(disc)-b)/(2*a),-(sqrt(disc)+b)/(2*a)};
}
double sigma_rev(double x){return quad(1,1,-2*x).first;}
lng cldv(lng a,lng b){return(a+b-1)/b;}
lng fp(lng a,lng b)
{
 lng rs=1;
 while(b>0){if(b&1){rs*=a;}a*=a;b>>=1;}
 return rs;
}
struct mtrx
{
 lng nx,mx;vector<vector<lng>>bd;
 void bld(vector<vector<lng>>obd){nx=obd.size(),mx=obd[0].size();bd=obd;}
 void outm(){for(lng i=0;i<nx;i++){for(lng j=0;j<mx;j++){cout << bd[i][j] << ' ';}cout << endl;}}
};
mtrx idnt(lng n)
{
 vector<vector<lng>>v;v.resize(n);
 for(lng i=0;i<n;i++){v[i].assign(n,0);v[i][i]=1;}
 return{n,n,v};
}
mtrx mulm(mtrx a,mtrx b)
{
 if(a.mx!=b.nx){return{1,1,{{0}}};}
 vector<vector<lng>>v;v.resize(a.nx);
 for(lng i=0;i<a.nx;i++)
 {
  v[i].resize(b.mx);
  for(lng j=0;j<b.mx;j++)
  {
   lng s=0;
   for(lng x=0;x<a.mx;x++)
   {
    s+=a.bd[i][x]*b.bd[x][j];
    s%=MOD;
   }
   v[i][j]=s;
  }
 }
 mtrx ret;ret.bld(v);
 return ret;
}
mtrx fpm(mtrx a,lng b)
{
 if(b==0){return idnt(a.nx);}
 mtrx ret=fpm(a,b/2);ret=mulm(ret,ret);
 if(b%2){ret=mulm(ret,a);}
 return ret;
}
lng rndm(lng a,lng b){return a+rng()%((b+1)-a);}
struct dsu
{
 vector<lng>p,sz;
 void init(lng n)
 {
  p.resize(n+1);sz.assign(n+1,1);
  for(lng i=0;i<=n;i++){p[i]=i;}
  return;
 }
 lng get(lng a)
 {
  if(p[a]==a){return a;}
  return p[a]=get(p[a]);
 }
 void unn(lng x,lng y)
 {
  if(cnct(x,y)){return;}
  x=get(x);y=get(y);
  if(sz[x]>sz[y]){swap(x,y);}
  p[x]=y;sz[y]+=sz[x];return;
 }
 bool cnct(lng x,lng y){return get(x)==get(y);}
 lng siz(lng a){return sz[get(a)];}
};
lng a[SZ],f[INF]{},ans[INF]{},n,k;
int main()
{
 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 cin >> n >> k;for(lng i=0;i<n;i++){cin >> a[i];f[a[i]]++;}
 for(lng i=k+1;i<INF;i++)
 {
  for(lng j=0;(i*j)+k<INF;j++){ans[(i*j)+k]+=f[i];}
 }
 for(int i=0;i<n;i++){cout << ans[a[i]]-int64_t(k==0) << ' ';}
 return 0;
}

Compilation message (stderr)

spiderman.cpp: In function 'int nPrvc(std::vector<int>)':
spiderman.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int i=0;i<r.size();i++){den=mul(den,inv[r[i]]);n+=r[i];}
      |              ~^~~~~~~~~

• Subtask 1: 70 / 70