codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1806.md (5746B)


      1 Source: https://codeforces.com/blog/entry/114048
      2 
      3 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.
      4 
      5 [1806A - Walking Master](/contest/1806/problem/A "Codeforces Round 858 (Div. 2)")
      6 
      7 **Solution**
      8 
      9 Tutorial is loading...
     10 
     11 **Code**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 #define ll long long
     16 #define fir first
     17 #define sec second
     18 #define pii pair<int,int>
     19 using namespace std;
     20 
     21 const int maxn=500005;
     22 const int inf=0x3f3f3f3f;
     23 
     24 signed main() {
     25 	ios::sync_with_stdio(false);
     26 	cin.tie(0),cout.tie(0);
     27 	int T;
     28 	cin>>T;
     29 	while(T--) {
     30 		int a,b,c,d;
     31 		cin>>a>>b>>c>>d;
     32 		if(b<=d&&c<=a+d-b) {
     33 			cout<<(d-b)+(a+d-b-c)<<"\n";
     34 		} else {
     35 			cout<<"-1\n";
     36 		}
     37 	}
     38 }
     39 ```
     40 
     41 [1806B - Mex Master](/contest/1806/problem/B "Codeforces Round 858 (Div. 2)")
     42 
     43 **Solution**
     44 
     45 Tutorial is loading...
     46 
     47 **Code**
     48 
     49 ```
     50 #include<bits/stdc++.h>
     51 #define ll long long
     52 #define fir first
     53 #define sec second
     54 #define pii pair<int,int>
     55 using namespace std;
     56 
     57 const int maxn=200005;
     58 const int inf=0x3f3f3f3f;
     59 
     60 signed main() {
     61 	ios::sync_with_stdio(false);
     62 	cin.tie(0),cout.tie(0);
     63 	int T;
     64 	cin>>T;
     65 	while(T--) {
     66 		int n;
     67 		cin>>n;
     68 		int sum0=0;
     69 		bool f=false;
     70 		for(int i=1;i<=n;i++) {
     71 			int x;
     72 			cin>>x;
     73 			if(x==0) {
     74 				sum0++;
     75 			} else if(x>=2) {
     76 				f=true;
     77 			}
     78 		}
     79 		if(sum0<=(n+1)/2) {
     80 			cout<<"0\n";
     81 		} else if(f||sum0==n) {
     82 			cout<<"1\n";
     83 		} else {
     84 			cout<<"2\n";
     85 		}
     86 	}
     87 }
     88 ```
     89 
     90 [1806C - Sequence Master](/contest/1806/problem/C "Codeforces Round 858 (Div. 2)")
     91 
     92 **Solution**
     93 
     94 Tutorial is loading...
     95 
     96 **Code**
     97 
     98 ```
     99 #include<bits/stdc++.h>
    100 #define ll long long
    101 #define fir first
    102 #define sec second
    103 #define pii pair<int,int>
    104 using namespace std;
    105 
    106 const int maxn=400005;
    107 const ll inf=0x3f3f3f3f3f3f3f3f;
    108 
    109 ll a[maxn];
    110 
    111 signed main() {
    112 	ios::sync_with_stdio(false);
    113 	cin.tie(0),cout.tie(0);
    114 	int T;
    115 	cin>>T;
    116 	while(T--) {
    117 		int n;
    118 		cin>>n;
    119 		ll ans=0,sum=0;
    120 		for(int i=1;i<=n*2;i++) {
    121 			cin>>a[i];
    122 			ans+=abs(a[i]);
    123 			sum+=abs(a[i]-(-1));
    124 		}
    125 		if(n==1) {
    126 			ans=min(ans,abs(a[1]-a[2]));
    127 		}
    128 		if(n==2) {
    129 			ans=min(ans,abs(a[1]-2)+abs(a[2]-2)+abs(a[3]-2)+abs(a[4]-2));
    130 		}
    131 		if(n%2==0) {
    132 			for(int i=1;i<=n*2;i++) {
    133 				ans=min(ans,sum-abs(a[i]-(-1))+abs(a[i]-n));
    134 			}
    135 		}
    136 		cout<<ans<<"\n";
    137 	}
    138 }
    139 ```
    140 
    141 [1806D - DSU Master](/contest/1806/problem/D "Codeforces Round 858 (Div. 2)")
    142 
    143 **Solution**
    144 
    145 Tutorial is loading...
    146 
    147 **Code**
    148 
    149 ```
    150 #include<bits/stdc++.h>
    151 #define ll long long
    152 #define fir first
    153 #define sec second
    154 #define pii pair<int,int>
    155 using namespace std;
    156  
    157 const int maxn=500005;
    158 const int inf=0x3f3f3f3f;
    159 const int mod=998244353;
    160 
    161 int a[maxn];
    162 int f[maxn];
    163 
    164 signed main() {
    165 	ios::sync_with_stdio(false);
    166 	cin.tie(0),cout.tie(0);
    167 	int T;
    168 	cin>>T;
    169 	while(T--) {
    170 		int n;
    171 		cin>>n;
    172 		for(int i=1;i<=n-1;i++) {
    173 			cin>>a[i];
    174 		}
    175 		f[1]=1;
    176 		for(int i=1;i<=n-1;i++) {
    177 			f[i+1]=1ll*f[i]*(i-a[i])%mod;
    178 		}
    179 		int ans=0;
    180 		for(int i=1;i<=n-1;i++) {
    181 			ans=(1ll*ans*i+(!a[i])*f[i])%mod;
    182 			cout<<ans<<" ";
    183 		}
    184 		cout<<"\n";
    185 	}
    186 }
    187 ```
    188 
    189 [1806E - Tree Master](/contest/1806/problem/E "Codeforces Round 858 (Div. 2)")
    190 
    191 **Solution**
    192 
    193 Tutorial is loading...
    194 
    195 **Code**
    196 
    197 ```
    198 #include<bits/stdc++.h>
    199 #define ll long long
    200 #define fir first
    201 #define sec second
    202 #define pii pair<int,int>
    203 using namespace std;
    204 
    205 const int maxn=100005;
    206 const int sqrtn=325;
    207 const int B=320;
    208 const int inf=0x3f3f3f3f;
    209 
    210 int n,q;
    211 int a[maxn];
    212 int h[maxn];
    213 int fa[maxn];
    214 int cnt[maxn];
    215 int depth[maxn];
    216 ll f[maxn][sqrtn];
    217 vector<int> tree[maxn]; 
    218 
    219 void dfs(int x,int d) {
    220 	h[x]=++cnt[d],depth[x]=d;
    221 	for(int to:tree[x]) {
    222 		dfs(to,d+1);
    223 	}
    224 }
    225 
    226 ll ask(int x,int y) {
    227 	if(!x&&!y) {
    228 		return 0;
    229 	}
    230 	if(cnt[depth[y]]<=B&&f[x][h[y]]) {
    231 		return f[x][h[y]];
    232 	}
    233 	ll ans=ask(fa[x],fa[y])+1ll*a[x]*a[y];
    234 	if(cnt[depth[y]]<=B) {
    235 		f[x][h[y]]=ans;
    236 	}
    237 	return ans;
    238 }
    239 
    240 signed main() {
    241 	ios::sync_with_stdio(false);
    242 	cin.tie(0),cout.tie(0);
    243 	cin>>n>>q;
    244 	for(int i=1;i<=n;i++) {
    245 		cin>>a[i];
    246 	}
    247 	for(int i=2;i<=n;i++) {
    248 		cin>>fa[i];
    249 		tree[fa[i]].push_back(i);
    250 	}
    251 	dfs(1,0);
    252 	while(q--) {
    253 		int x,y;
    254 		cin>>x>>y;
    255 		cout<<ask(x,y)<<"\n";
    256 	}
    257 }
    258 ```
    259 
    260 [1806F2 - GCD Master (hard version)](/contest/1806/problem/F2 "Codeforces Round 858 (Div. 2)")
    261 
    262 **Solution**
    263 
    264 Tutorial is loading...
    265 
    266 **Code**
    267 
    268 ```
    269 #include<bits/stdc++.h>
    270 #define ll long long
    271 #define int128 __int128
    272 #define fir first
    273 #define sec second
    274 #define pii pair<int,int>
    275 using namespace std;
    276 
    277 const int maxn=1000005;
    278 const ll inf=9e18;
    279 const int128 inf128=(int128)(inf)*(int128)(inf);
    280 
    281 ll a[maxn];
    282 ll b[maxn];
    283 ll g[maxn];
    284 ll ra[maxn];
    285 int128 suma[maxn];
    286 int128 sumb[maxn];
    287 int128 ans[maxn];
    288 
    289 ll gcd(ll x,ll y) {
    290 	return !y?x:gcd(y,x%y);
    291 }
    292 
    293 void print(int128 x) {
    294 	if(!x) {
    295 		return ;
    296 	}
    297 	print(x/10);
    298 	cout<<(int)(x%10);
    299 }
    300 
    301 signed main() {
    302 	ios::sync_with_stdio(false);
    303 	cin.tie(0),cout.tie(0);
    304 	int T;
    305 	cin>>T;
    306 	while(T--) {
    307 		int n,k;
    308 		ll m;
    309 		cin>>n>>m>>k;
    310 		for(int i=1;i<=n;i++) {
    311 			cin>>a[i];
    312 		}
    313 		sort(a+1,a+n+1);
    314 		int t=0,r=0;
    315 		for(int i=1;i<=n;i++) {
    316 			if(i>1&&a[i]==a[i-1]) {
    317 				b[++r]=a[i];
    318 			} else {
    319 				ra[++t]=a[i];
    320 			}
    321 		}
    322 		n=t;
    323 		for(int i=1;i<=n;i++) {
    324 			a[i]=ra[i];
    325 			g[i]=gcd(g[i-1],a[i]);
    326 			suma[i]=suma[i-1]+a[i];
    327 		}
    328 		for(int i=0;i<=k;i++) {
    329 			ans[i]=-inf128;
    330 		}
    331 		for(int l=1;l<=n;) {
    332 			int r=l;
    333 			while(r<=n&&g[r]==g[l]) {
    334 				r++;
    335 			}
    336 			r--;
    337 			ll Max=-inf;
    338 			for(int i=r+1;i<=n;i++) {
    339 				a[i]=gcd(a[i],g[l]);
    340 				Max=max(Max,a[i]-ra[i]);
    341 			}
    342 			for(int i=r;i>=l;i--) {
    343 				ans[i]=suma[n]-suma[i]+Max;	
    344 				a[i]=gcd(a[i],g[l]);
    345 				Max=max(Max,a[i]-ra[i]);
    346 			}
    347 			l=r+1;
    348 		}
    349 		for(int i=1;i<=r;i++) {
    350 			sumb[i]=sumb[i-1]+b[i];
    351 		}
    352 		int128 final=-inf128;
    353 		if(k<=r) {
    354 			final=suma[n]+sumb[r]-sumb[k];
    355 		}
    356 		for(int i=0;i<=r&&i<=k;i++) {
    357 			final=max(final,sumb[r]-sumb[i]+ans[k-i]);
    358 		}
    359 		print(final);
    360 		cout<<"\n";
    361 	}
    362 }
    363 ```