Tutorial is loading...
Author: crvineeth97
Testers: deepanshugarg, nir123
Author's code
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long ans=LLONG_MIN, n, x;
cin>>n;
for (long long i = 0; i < n; i++)
{
cin>>x;
for (long long j = 0; j*j<=x; j++)
if (j*j == x)
x = LLONG_MIN;
ans = max(ans, x);
}
cout << ans << endl;
return 0;
}
Tutorial is loading...
Author: RohanRTiwari
Tester: Superty
Author's code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int cnt[100005];
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
while(n--) {
int x;
cin >> x;
cnt[x]++;
}
for (int i = 1; i <= 1e5; i++) {
if (cnt[i] % 2 == 1) {
cout << "Conan\n";
return 0;
}
}
cout << "Agasa\n";
return 0;
}
Tutorial is loading...
Author: aman_shahi2
Tester: mprocks
Author's code
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
int dp[1004];
long long ncr[1004][1004];
int ones(int n)
{
int cnt = 0;
while(n)
{
if(n%2 == 1)
{
cnt++;
}
n /= 2;
}
return cnt;
}
void calcncr()
{
for(int i = 0; i <= 1000; i++)
{
ncr[i][0] = 1;
}
for(int i = 1; i <= 1000; i++)
{
for(int j = 1; j <= 1000; j++)
{
ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j])%MOD;
}
}
}
int main()
{
string n;
int k;
calcncr();
dp[1] = 0;
for(int i = 2; i <= 1000; i++)
{
dp[i] = dp[ones(i)] + 1;
}
cin >> n >> k;
if(k == 0)
{
cout << "1\n";
return 0;
}
long long nones = 0, ans = 0;
for(int i = 0; i < n.size(); i++)
{
if(n[i] == '0')
{
continue;
}
for(int j = max(nones, 1LL); j < 1000; j++)
{
if(dp[j] == k-1)
{
ans = (ans + ncr[n.size()-i-1][j-nones])%MOD;
if(i == 0 && k == 1)
{
ans = (ans+MOD-1)%MOD;
}
}
}
nones++;
}
int cnt = 0;
for(int i = 0; i < n.size(); i++)
{
if(n[i] == '1')
{
cnt++;
}
}
if(dp[cnt] == k-1)
{
ans = (ans + 1)%MOD;
}
cout << ans << endl;
return 0;
}
Tutorial is loading...
Author: RohanRTiwari
Testers: codelegend, Superty
Author's code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int tree[2000000];
int trstp = 1;
int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
void query(int root, int u, int v, int x, int s, int e, int& ans) {
if (e < s || v < u || e < u || v < s) {
return;
} else if (u <= s && e <= v) {
if (tree[root] % x == 0) {
return;
} else {
while (root < trstp) {
if (tree[2*root] % x != 0) {
if (tree[2*root + 1] % x != 0) {
ans += 2;
return;
}
root = 2*root;
} else {
root = 2*root + 1;
}
}
ans++;
return;
}
}
int mid = (s + e)/2;
query(2*root, u, v, x, s, mid, ans);
if (ans > 1) {
return;
}
query(2*root + 1, u, v, x, mid + 1, e, ans);
}
void update(int p, int x) {
p += trstp - 1;
tree[p] = x;
p /= 2;
while (p > 0) {
tree[p] = gcd(tree[2*p], tree[2*p + 1]);
p /= 2;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
while (trstp < n) {
trstp *= 2;
}
for (int i = trstp; i < trstp + n; i++) {
cin >> tree[i];
}
for (int i = trstp - 1; i >= 1; i--) {
tree[i] = gcd(tree[2*i], tree[2*i + 1]);
}
int q;
cin >> q;
while (q--) {
int t;
cin >> t;
if (t == 1) {
int l, r;
int x;
cin >> l >> r >> x;
int ans = 0;
query(1, l, r, x, 1, trstp, ans);
cout << (ans <= 1 ? "YES\n" : "NO\n");
} else {
int i;
int y;
cin >> i >> y;
update(i, y);
}
}
return 0;
}
Tutorial is loading...
Author: born2rule
Testers: devanshg27, FundamentalEq
Author's code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int L=200005,N=(1<<20);
//call dfsMCT,change solve and dfs1
vi vpart[L],ad[L]; bool vis[L];//par:parent in cent|H:depth
int SZ[L],par[L],part[L],H[L],cpart;//cpart:no of parts in cent
ll ans[L],dp[L];
string s;
int dfsSZ(int u,int p=-1)
{
SZ[u]=1;//vpart[i]:nodes in part i
for(int v:ad[u])
if(!vis[v] && v!=p)
SZ[u]+=dfsSZ(v,u);
return SZ[u];
}
int dfsFC(int u,int r,int p=-1)
{
for(int v:ad[u])
if(!vis[v] && v!=p)
{
if(SZ[v]>SZ[r]/2)
return dfsFC(v,r,u);
}
return u;
}
int cnt[N],val[L],tmp[N];
void dfs1(int u,int r,int p=-1)
{
dp[u]=0;
if(p==r)
{
part[u]=++cpart;
vpart[cpart].clear();
}
else if(p!=-1) part[u]=part[p];
if(p!=-1) vpart[cpart].pb(u);
for(int v1:ad[u])
if(!vis[v1]&&v1!=p)
{
H[v1]=H[u]+1;
val[v1]=(val[u]^(1<<(s[v1-1]-'a')));
dfs1(v1,r,u);
}
}
void dfs2(int u,int r,int par=-1)
{
dp[u]=cnt[val[u]];
rep(i,0,20)
dp[u]+=cnt[val[u]^(1<<i)];
for(int v1:ad[u])
{
if(vis[v1] || v1==par) continue;
dfs2(v1,r,u);
dp[u]+=dp[v1];
}
ans[u]+=dp[u];
}
void solve(int r,int szr)
{
H[r]=cpart=0;
val[r]=(1<<(s[r-1]-'a'));
dfs1(r,r);
rep(i,1,cpart+1)
for(int v1:vpart[i])
cnt[val[v1]]++;
cnt[val[r]]++;
rep(i,1,cpart+1)
{
for(int v1:vpart[i])
{
cnt[val[v1]]--;
val[v1]^=(1<<(s[r-1]-'a'));
tmp[val[v1]]++;
}
for(int v1:vpart[i])
{
if(tmp[val[v1]])
{
dp[r]+=(ll)tmp[val[v1]]*cnt[val[v1]];
rep(j,0,20)
dp[r]+=(ll)tmp[val[v1]]*cnt[val[v1]^(1<<j)];
tmp[val[v1]]=0;
}
}
dfs2(vpart[i][0],r,r);
for(int v1:vpart[i])
{
val[v1]^=(1<<(s[r-1]-'a'));
cnt[val[v1]]++;
}
}
cnt[val[r]]--;
dp[r]+=cnt[0];
rep(i,0,20)
dp[r]+=cnt[(1<<i)];
ans[r]+=dp[r]/2;
rep(i,1,cpart+1)
for(int v1:vpart[i]) cnt[val[v1]]--;
}
void dfsMCT(int u,int p=-1)
{
dfsSZ(u);
int r=dfsFC(u,u);
par[r]=p; solve(r,SZ[u]); vis[r]=true;
for(int v:ad[r])
if(!vis[v]) dfsMCT(v,r);
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL) ; cout.tie(NULL) ;
int n,x,y;
cin>>n;
rep(i,1,n)
{
cin>>x>>y;
ad[x].pb(y); ad[y].pb(x);
}
cin>>s;
dfsMCT(1);
rep(i,1,n+1) cout<<ans[i]+1<<" ";
cout<<endl;
return 0 ;
}
Tutorial is loading...
There was an unexpected solution that involved bitset that runs in complexity O(N2 / 32). Have a look at Syloviaely 's code: 34364964
Author: RohanRTiwari
Testers: born2rule, devanshg27, additya1998, virus_1010, nir123
Author's code
#include <bits/stdc++.h>
#define fr(x) scanf("%d", &x)
#define SQRN 150
using namespace std;
const int sa = 2 * SQRN + 10;
const int LEN = 100010;
char s[LEN], sq[LEN], zstring[2*LEN];
int z[2*LEN];
string temps;
struct SuffixAutomaton {
int edges[26][sa], link[sa], length[sa], isTerminal[sa], dp1[sa], last;
int sz;
SuffixAutomaton() {
last = 0;
sz = 0;
}
void set(int k) {
for(int i = 0; i < 26; ++i) edges[i][k] = -1;
}
void build(string &s) {
link[0] = -1;
length[0] = 0;
last = 0;
sz = 1;
set(0);
for(int i=0;i<s.size();i++) {
set(sz);
length[sz] = i+1;
link[sz] = 0;
int r = sz;
++sz;
int p = last;
while(p >= 0 && edges[s[i]-'a'][p] == -1) {
edges[s[i] - 'a'][p] = r;
p = link[p];
}
if(p != -1) {
int q = edges[s[i] - 'a'][p];
if(length[p] + 1 == length[q]) {
link[r] = q;
} else {
for(int i = 0; i < 26; ++i) {
edges[i][sz] = edges[i][q];
}
length[sz] = length[p] + 1;
link[sz] = link[q];
int qq = sz;
++sz;
link[q] = qq;
link[r] = qq;
while(p >= 0 && edges[s[i] - 'a'][p] == q) {
edges[s[i] - 'a'][p] = qq;
p = link[p];
}
}
}
last = r;
}
for(int i = 0; i < sz; ++i) isTerminal[i] = 0, dp1[i] = -1;
int p = last;
while(p > 0) {
isTerminal[p] = 1;
p = link[p];
}
}
int solve(int pos) {
if(dp1[pos] != -1) return dp1[pos];
dp1[pos] = isTerminal[pos];
for(int i=0; i<26; ++i){
if(edges[i][pos] != -1) dp1[pos] += solve(edges[i][pos]);
}
return dp1[pos];
}
int run() {
int cur = 0;
for(int i=1; sq[i] != '\0'; ++i) {
auto it = edges[sq[i] - 'a'][cur];
if(it == -1) return 0;
else cur = it;
}
return solve(cur);
}
} SA[800];
void computeZ() {
int l, r;
z[0] = 0;
l = r = -1;
for(int i=1; zstring[i] != '\0'; ++i) {
z[i]=0;
if(r>i) {
z[i]=min(z[i-l], r-i+1);
}
while(zstring[i+z[i]] == zstring[z[i]]) ++z[i];
if(i+z[i]-1 > r) {
r = i+z[i]-1;
l = i;
}
}
}
int computeBrute(int l, int r, int sqlen) {
int zslen = 0, ans = 0;
for(int i=1; i<=sqlen; ++i) {
zstring[zslen++] = sq[i];
}
zstring[zslen++] = '$';
for(int i=l; i<=r; ++i) {
zstring[zslen++] = s[i];
}
zstring[zslen] = '\0';
computeZ();
for(int i=1; i<zslen; ++i) {
if(z[i] >= sqlen) {
++ans;
}
}
return ans;
}
int main() {
int q, typ, l, r, slen;
char ch;
scanf(" %s", &s[1]);
slen = strlen(&s[1]);
fr(q);
for(int i=0; i<=slen; i+=SQRN) {
temps = "";
int tempr = min(i+SQRN-1, slen);
for(int j=max(1, i); j<=tempr; ++j) {
temps += s[j];
}
SA[i/SQRN].build(temps);
}
while(q--) {
fr(typ);
if(typ == 1) {
scanf("%d %c", &l, &ch);
s[l] = ch;
temps = "";
int bkt = l/SQRN;
int tempr = min(slen, (bkt+1)*SQRN-1);
for(int i=max(1,bkt*SQRN); i<=tempr; ++i) {
temps += s[i];
}
SA[bkt].build(temps);
}
else {
scanf("%d %d %s", &l, &r, &sq[1]);
int sqlen = strlen(&sq[1]);
if(sqlen >= SQRN || r-l <= 2*SQRN) {
printf("%d\n", computeBrute(l, r, sqlen));
}
else {
int lbkt = l/SQRN, rbkt = r/SQRN, ans = 0;
for(int i=lbkt+1; i<rbkt; ++i) {
ans += SA[i].run();
}
ans += computeBrute(l, (lbkt+1)*SQRN-1, sqlen);
ans += computeBrute(rbkt*SQRN, r, sqlen);
for(int i=lbkt+1; i<=rbkt; ++i) {
ans += computeBrute(max(l, i*SQRN - sqlen + 1), min(r, i*SQRN + sqlen - 2), sqlen);
}
printf("%d\n", ans);
}
}
}
return 0;
}
Tutorial is loading...
Author: FundamentalEq
Tester: born2rule
Author's code
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define db long double
#define ii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define mp make_pair
#define FN(i, n) for (int i = 0; i < (int)(n); ++i)
#define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repv(i,a,b) for(int i=b-1;i>=a;i--)
#define SET(A, val) memset(A, val, sizeof(A))
typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
// order_of_key (val): returns the no. of values less than val
// find_by_order (k): returns the kth largest element.(0-based)
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int L = 17 ;
const int L2 = 1<<L ;
const int mod = 1e9+7 ;
int sbits[L2] ;
vi oddbits ;
inline int add(int x,int y)
{
x+=y;
if(x>=mod) x-=mod;
if(x<0) x+=mod;
return x;
}
inline int mult(int x,int y)
{
ll tmp=(ll)x*y;
if(tmp>=mod) tmp%=mod;
return tmp;
}
inline int pwmod(int x,int y)
{
int ans=1;
while(y){if(y&1)ans=mult(ans,x);y>>=1;x=mult(x,x);}
return ans;
}
vector<ii> nus[L] ;
void zeta(int A[L2])
{
FN(i,L)
{
for(ii m:nus[i]) A[m.fi]=add(A[m.fi],A[m.se]) ;
}
}
void meu(int A[L2])
{
for(int i:oddbits) A[i] = mod - A[i] ;
zeta(A) ;
for(int i:oddbits) A[i] = mod - A[i] ;
}
void conv(int A[L2],int B[L2])
{
zeta(A), zeta(B);//return
FN(i,L2) A[i]=mult(A[i],B[i]);
meu(A);
}
int t[L+1][L2],t1[L2] ;
void subsetconv(int A[L2],int ans[L2])
{
FN(i,L2) t[sbits[i]][i] = A[i] ;
FN(i,L+1) zeta(t[i]) ;
FN(c,L+1) FN(a,c+1)
{
int *t2 = t[a], *t3 = t[c-a] ;
FN(i,L2) t1[i]=mult(t2[i],t3[i]) ;
meu(t1) ;
FN(i,L2) if(sbits[i] == c) ans[i]=add(ans[i],t1[i]) ;
}
}
vector<ii> su[L] ;
void transform(int p[L2],bool inv=false){ int u,v;
for(int len=1,l=2;l<=L2;len<<=1,l<<=1)for(int
i=0;i<L2;i+=l) FN(j,len){
u=p[i+j],v=p[i+j+len] ;
if(inv) {p[i+j]=add(u,v),p[i+j+len]=add(u,-v);}
else {p[i+j]=add(u,v),p[i+j+len]=add(u,-v);}}
if(inv){int d=pwmod(L2,mod-2);FN(i,L2)p[i]=mult(p[i],d);} }
int cnt[L2],fib[L2],A[L2],B[L2],C[L2],a[L2],b[L2],c[L2] ;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL) ; cout.tie(NULL) ;
FN(i,L2)
{
sbits[i] = __builtin_popcount(i) ;
if(sbits[i] & 1) oddbits.emplace_back(i) ;
FN(j,L)
{
if(i&(1<<j)) nus[j].emplace_back(mp(i,i^(1<<j))) ;
if((i&(1<<j)) == 0) su[j].emplace_back(mp(i,i^(1<<j))) ;
}
}
FN(i,L) reverse(all(su[i])) ;
fib[1] = 1 ; rep(i,2,L2) fib[i] = add(fib[i-1],fib[i-2]) ;
int N,x ; cin>>N ;
FN(i,N)
{
cin>>x, ++cnt[x] ;
}
subsetconv(cnt,A) ;
FN(i,L2) A[i]=mult(A[i],fib[i]) ;
FN(i,L2) B[i]=mult(cnt[i],fib[i]);
FN(i,L2) C[i]=cnt[i] ;
transform(C) ;
FN(i,L2) C[i]=mult(C[i],C[i]) ;
transform(C,1) ;
FN(i,L2) C[i]=mult(C[i],fib[i]) ;
int ans = 0 ;
FN(p,L)
{
FN(i,L2) a[i]=b[i]=c[i]=0 ;
for(ii m:nus[p]) a[m.se]=A[m.fi],b[m.se]=B[m.fi],c[m.se]=C[m.fi] ;
FN(i,L)
{
for(ii m:su[i])
{
a[m.fi]=add(a[m.fi],a[m.se]) ;
b[m.fi]=add(b[m.fi],b[m.se]) ;
c[m.fi]=add(c[m.fi],c[m.se]) ;
}
}
FN(i,L2) a[i]=mult(a[i],mult(b[i],c[i])) ;
meu(a) ;
ans = add(ans,a[(1<<L)-1]) ;
}
ans = ans == 0 ? 0 : mod - ans ;
cout << ans << "\n" ;
return 0 ;
}
Tutorial is loading...
Author: Superty
Tester: codelegend
Author's code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll mod;
const int maxn = 2e2 + 2;
ll tree[maxn][maxn][maxn];
ll c[maxn][maxn];
int main() {
ios::sync_with_stdio(false);
int n, d;
cin >> n >> d >> mod;
c[0][0] = 1;
for (int i = 1; i <= n; i++) {
c[i][0] = 1;
for (int j = 1; j <= i; j++) {
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
tree[1][1][0] = 1;
for (int i = 1; i < n; i++) { // adding trees of size i
for (int j = 1; j <= n; j++) {
for (int k = 0; k <= d; k++) {
tree[i + 1][j][k] = tree[i][j][k];
}
}
ll tree_i = 0;
for (int j = 0; j < d; j++) {
tree_i = (tree_i + tree[i][i][j]) % mod;
}
ll ways = 1;
for (int j = 1; i*j <= n && j <= d; j++) { // adding j such trees
ways = (ways * c[i*j - 1][i - 1]) % mod; // ((ij)! tree[i]^(j-1))/(i!^j j!)
for (int k = 1; k + i*j <= n; k++) { // adding to trees of size k
ll cc = (ways * c[k + i*j - 1][k - 1]) % mod;
for (int deg = 0; deg + j <= d; deg++) {
tree[i + 1][k + i*j][deg + j] = (tree[i + 1][k + i*j][deg + j] + cc*((tree[i][k][deg]*tree_i) % mod)) % mod;
}
}
ways = (ways * tree_i) % mod;
}
}
ll total_trees = 0;
for (int i = 0; i <= n - 1; i++) { // there are i vertices lying on paths increasing from the root
for (int j = 0; j <= d; j++) {
for (int k = 0; j + k <= d; k++) {
if (k == 1) {
continue;
}
total_trees = (total_trees + ((tree[n][i + 1][j]*tree[n][n - i][k]) % mod)) % mod;
}
}
}
cout << (2*((n*(n-1)) % mod)*total_trees) % mod << '\n';
return 0;
}