1316A - Grade Allocation
Author: gaurav172
Development: gaurav172, firebolt, night_fury208
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ll test;
cin>>test;
while(test--)
{
ll n,m;
cin>>n>>m;
ll s=0;
for(ll i=1;i<=n;i++)
{
ll x;
cin>>x;
s=s+x;
}
cout<<min(s,m)<<"\n";
}
return 0;
}
1316B - String Modification
Author: preet_t
Development: preet_t, shaanknight, night_fury208
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
string modified(string& s, int n, int k) {
string result_prefix = s.substr(k - 1, n - k + 1);
string result_suffix = s.substr(0, k - 1);
if (n % 2 == k % 2)
reverse(result_suffix.begin(), result_suffix.end());
return result_prefix + result_suffix;
}
int main () {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
string s, best_s, temp;
int t, n, best_k;
cin >> t;
while (t--) {
cin >> n >> s;
best_s = modified(s, n, 1);
best_k = 1;
for (int k = 2; k <= n; ++k) {
temp = modified(s, n, k);
if (temp < best_s) {
best_s = temp;
best_k = k;
}
}
cout << best_s << '\n' << best_k << '\n';
}
return 0;
}
1316C - Primitive Primes
Author: lazyneuron
Development: lazyneuron, shaanknight,firebolt
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
ll n,i,m,x,a,p,fir,sec;
cin >> n >> m >> p;
a=0;
for(i=0;i<n;i++)
{
cin >> x;
if(x%p && !a)
{
a=1;
fir=i;
}
}
a=0;
for(i=0;i<m;i++)
{
cin >> x;
if(x%p && !a)
{
a=1;
sec=i;
}
}
cout << fir+sec << endl;
return 0;
}
1316D - Nash Matrix
Author: shaanknight
Development: shaanknight, riz_1_, coder_h,Altitude
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
const int M = (1<<10)+5;
char mat[M][M];
int x[M][M],y[M][M];
int n;
bool connect(int p,int q,int r,int s,char d1,char d2)
{
if(x[r][s] == -1)
{
mat[p][q] = d1;
if(mat[r][s] == '\0') mat[r][s] = d2;
return 1;
}
else
return 0;
}
void dfs(int p,int q,char d)
{
if(mat[p][q] != '\0') return;
mat[p][q] = d;
if(x[p][q] == x[p+1][q] && y[p][q] == y[p+1][q])
dfs(p+1,q,'U');
if(x[p][q] == x[p-1][q] && y[p][q] == y[p-1][q])
dfs(p-1,q,'D');
if(x[p][q] == x[p][q+1] && y[p][q] == y[p][q+1])
dfs(p,q+1,'L');
if(x[p][q] == x[p][q-1] && y[p][q] == y[p][q-1])
dfs(p,q-1,'R');
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int i,j;
cin >> n;
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
cin >> x[i][j] >> y[i][j];
}
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
if(x[i][j] == -1)
{
bool res = (mat[i][j] != '\0');
if(res == 0) res = connect(i,j,i+1,j,'D','U');
if(res == 0) res = connect(i,j,i,j+1,'R','L');
if(res == 0) res = connect(i,j,i-1,j,'U','D');
if(res == 0) res = connect(i,j,i,j-1,'L','R');
if(res == 0)
{
cout << "INVALID" << "\n";
return 0;
}
}
else if(x[i][j] == i && y[i][j] == j)
dfs(i,j,'X');
}
}
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
if(mat[i][j] == '\0')
{
cout << "INVALID" << "\n";
return 0;
}
}
}
cout << "VALID" << "\n";
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
{
cout << mat[i][j];
}
cout << "\n";
}
return 0;
}
1316E - Team Building
Author: gaurav172
Development: gaurav172, shaanknight, coder_h, madlad
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const ll M=1e5+5;
ll dp[M][(1<<7)+1],skill[M][7];
ll ind[M],a[M];
bool cmp(ll p,ll q)
{
return a[p]>a[q];
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n,p,k;
cin>>n>>p>>k;
memset(dp,-1,sizeof(dp));
for(ll i=1;i<=n;i++)
cin>>a[i];
for(ll i=1;i<=n;i++)
for(ll j=0;j<p;j++)
cin>>skill[i][j];
for(ll i=1;i<=n;i++)
ind[i]=i;
sort(ind+1,ind+n+1,cmp);
dp[0][0]=0;
for(ll i=1;i<=n;i++)
{
ll x=ind[i];
for(ll mask=0;mask<(1<<p);mask++)
{
ll ct=0;
for(ll j=0;j<p;j++)
if((mask&(1<<j)))
ct++;
ll z=(i-1)-ct;
if(z<k)
{
if(dp[i-1][mask]!=-1)
dp[i][mask]=dp[i-1][mask]+a[x];
}
else
{
if(dp[i-1][mask]!=-1)
dp[i][mask]=dp[i-1][mask];
}
for(ll j=0;j<p;j++)
{
if((mask&(1<<j)) && dp[i-1][(mask^(1<<j))]!=-1)
{
ll z=dp[i-1][(mask^(1<<j))]+skill[x][j];
if(z>dp[i][mask])
dp[i][mask]=z;
}
}
}
}
cout<<dp[n][(1<<p)-1]<<"\n";
return 0;
}
1316F - Battalion Strength
Author: gaurav172
Development: gaurav172, shaanknight
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) (ll)(a.size())
const ll M=6e5+6;
const ll mod=1e9+7;
ll val[4*M],lt[4*M],rt[4*M];
int no[4*M];
ll pw[M],ipw[M];
int P[M],idx[M],qr[M],n,q;
vector<pair<int,int> > v;
ll power(ll a,ll b)
{
ll val=1;
while(b)
{
if(b%2)
val=(val*a)%mod;
b/=2;
a=(a*a)%mod;
}
return val;
}
void build(int i,int s,int e)
{
if(s==e)
{
if(v[s].ss>n)
return;
val[i]=0;
lt[i]=v[s].ff;
rt[i]=(v[s].ff*ipw[1])%mod;
no[i]=1;
return;
}
int m=(s+e)/2;
int lc=2*i,rc=2*i+1;
build(lc,s,m);
build(rc,m+1,e);
ll tp=(ipw[no[lc]]*rt[rc])%mod;
tp=(tp*lt[lc])%mod;
val[i]=(val[lc]+val[rc]+tp)%mod;
lt[i]=(lt[lc]+pw[no[lc]]*lt[rc])%mod;
rt[i]=(rt[lc]+ipw[no[lc]]*rt[rc])%mod;
no[i]=(no[lc]+no[rc]);
}
void update(int i,int s,int e,int x,int y)
{
if(s==e)
{
if(y==-1)
{
val[i]=0;
lt[i]=0;
rt[i]=0;
no[i]=0;
}
else
{
val[i]=0;
lt[i]=v[s].ff;
rt[i]=(v[s].ff*ipw[1])%mod;
no[i]=1;
}
return;
}
int m=(s+e)/2;
int lc=(i<<1),rc=(lc|1);
if(x<=m)
update(lc,s,m,x,y);
else
update(rc,m+1,e,x,y);
ll tp=(ipw[no[lc]]*rt[rc])%mod;
tp=(tp*lt[lc])%mod;
val[i]=(val[lc]+val[rc]+tp)%mod;
lt[i]=(lt[lc]+pw[no[lc]]*lt[rc])%mod;
rt[i]=(rt[lc]+ipw[no[lc]]*rt[rc])%mod;
no[i]=(no[lc]+no[rc]);
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
pw[0]=1;
ipw[0]=1;
ll inv=power(2,mod-2);
for(int i=1;i<M;i++)
{
pw[i]=(pw[i-1]*2)%mod;
ipw[i]=(ipw[i-1]*inv)%mod;
}
cin>>n;
v.pb({-1LL,-1});
for(int i=1;i<=n;i++)
{
cin>>P[i];
v.pb({P[i],i});
}
cin>>q;
for(int i=1;i<=q;i++)
{
cin>>idx[i]>>qr[i];
v.pb({qr[i],n+i});
}
sort(all(v));
std::vector<int> pos(n+q+1,0);
for(int i=1;i<sz(v);i++)
pos[v[i].ss]=i;
build(1,1,n+q);
cout<<val[1]<<"\n";
for(int i=1;i<=q;i++)
{
update(1,1,n+q,pos[idx[i]],-1);
pos[idx[i]]=pos[n+i];
update(1,1,n+q,pos[idx[i]],1);
cout<<val[1]<<"\n";
}
return 0;
}