We are really sorry that C is tough and E is easier than D. But anyway hope you can enjoy the problems themselves and learn something from them.
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
const int maxn=500005;
const int inf=0x3f3f3f3f;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--) {
int a,b,c,d;
cin>>a>>b>>c>>d;
if(b<=d&&c<=a+d-b) {
cout<<(d-b)+(a+d-b-c)<<"\n";
} else {
cout<<"-1\n";
}
}
}
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
const int maxn=200005;
const int inf=0x3f3f3f3f;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
int sum0=0;
bool f=false;
for(int i=1;i<=n;i++) {
int x;
cin>>x;
if(x==0) {
sum0++;
} else if(x>=2) {
f=true;
}
}
if(sum0<=(n+1)/2) {
cout<<"0\n";
} else if(f||sum0==n) {
cout<<"1\n";
} else {
cout<<"2\n";
}
}
}
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
const int maxn=400005;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll a[maxn];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
ll ans=0,sum=0;
for(int i=1;i<=n*2;i++) {
cin>>a[i];
ans+=abs(a[i]);
sum+=abs(a[i]-(-1));
}
if(n==1) {
ans=min(ans,abs(a[1]-a[2]));
}
if(n==2) {
ans=min(ans,abs(a[1]-2)+abs(a[2]-2)+abs(a[3]-2)+abs(a[4]-2));
}
if(n%2==0) {
for(int i=1;i<=n*2;i++) {
ans=min(ans,sum-abs(a[i]-(-1))+abs(a[i]-n));
}
}
cout<<ans<<"\n";
}
}
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
const int maxn=500005;
const int inf=0x3f3f3f3f;
const int mod=998244353;
int a[maxn];
int f[maxn];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--) {
int n;
cin>>n;
for(int i=1;i<=n-1;i++) {
cin>>a[i];
}
f[1]=1;
for(int i=1;i<=n-1;i++) {
f[i+1]=1ll*f[i]*(i-a[i])%mod;
}
int ans=0;
for(int i=1;i<=n-1;i++) {
ans=(1ll*ans*i+(!a[i])*f[i])%mod;
cout<<ans<<" ";
}
cout<<"\n";
}
}
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
const int maxn=100005;
const int sqrtn=325;
const int B=320;
const int inf=0x3f3f3f3f;
int n,q;
int a[maxn];
int h[maxn];
int fa[maxn];
int cnt[maxn];
int depth[maxn];
ll f[maxn][sqrtn];
vector<int> tree[maxn];
void dfs(int x,int d) {
h[x]=++cnt[d],depth[x]=d;
for(int to:tree[x]) {
dfs(to,d+1);
}
}
ll ask(int x,int y) {
if(!x&&!y) {
return 0;
}
if(cnt[depth[y]]<=B&&f[x][h[y]]) {
return f[x][h[y]];
}
ll ans=ask(fa[x],fa[y])+1ll*a[x]*a[y];
if(cnt[depth[y]]<=B) {
f[x][h[y]]=ans;
}
return ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++) {
cin>>a[i];
}
for(int i=2;i<=n;i++) {
cin>>fa[i];
tree[fa[i]].push_back(i);
}
dfs(1,0);
while(q--) {
int x,y;
cin>>x>>y;
cout<<ask(x,y)<<"\n";
}
}
1806F2 - GCD Master (hard version)
Solution
Tutorial is loading...
Code
#include<bits/stdc++.h>
#define ll long long
#define int128 __int128
#define fir first
#define sec second
#define pii pair<int,int>
using namespace std;
const int maxn=1000005;
const ll inf=9e18;
const int128 inf128=(int128)(inf)*(int128)(inf);
ll a[maxn];
ll b[maxn];
ll g[maxn];
ll ra[maxn];
int128 suma[maxn];
int128 sumb[maxn];
int128 ans[maxn];
ll gcd(ll x,ll y) {
return !y?x:gcd(y,x%y);
}
void print(int128 x) {
if(!x) {
return ;
}
print(x/10);
cout<<(int)(x%10);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin>>T;
while(T--) {
int n,k;
ll m;
cin>>n>>m>>k;
for(int i=1;i<=n;i++) {
cin>>a[i];
}
sort(a+1,a+n+1);
int t=0,r=0;
for(int i=1;i<=n;i++) {
if(i>1&&a[i]==a[i-1]) {
b[++r]=a[i];
} else {
ra[++t]=a[i];
}
}
n=t;
for(int i=1;i<=n;i++) {
a[i]=ra[i];
g[i]=gcd(g[i-1],a[i]);
suma[i]=suma[i-1]+a[i];
}
for(int i=0;i<=k;i++) {
ans[i]=-inf128;
}
for(int l=1;l<=n;) {
int r=l;
while(r<=n&&g[r]==g[l]) {
r++;
}
r--;
ll Max=-inf;
for(int i=r+1;i<=n;i++) {
a[i]=gcd(a[i],g[l]);
Max=max(Max,a[i]-ra[i]);
}
for(int i=r;i>=l;i--) {
ans[i]=suma[n]-suma[i]+Max;
a[i]=gcd(a[i],g[l]);
Max=max(Max,a[i]-ra[i]);
}
l=r+1;
}
for(int i=1;i<=r;i++) {
sumb[i]=sumb[i-1]+b[i];
}
int128 final=-inf128;
if(k<=r) {
final=suma[n]+sumb[r]-sumb[k];
}
for(int i=0;i<=r&&i<=k;i++) {
final=max(final,sumb[r]-sumb[i]+ans[k-i]);
}
print(final);
cout<<"\n";
}
}