2195.md (9311B)
1 Source: https://codeforces.com/blog/entry/151174 2 3 I hope you enjoyed any number of problems in the contest! 4 5 Solution codes will be posted after the open hack phase. They have now been added. 6 7 ## [2195A - Sieve of Erato67henes](/contest/2195/problem/A "Codeforces Round 1080 (Div. 3)") 8 9 **Rate the problem!** 10 11 * Epic 12 * Good 13 * Moderate 14 * Bad 15 * Horrendous 16 17 **Editorial** 18 19 Tutorial is loading... 20 21 **Code** 22 23 ``` 24 for _ in range(int(input())): 25 n=int(input()) 26 a=[*map(int,input().split())] 27 if 67 in a: 28 print("YES") 29 else: 30 print("NO") 31 ``` 32 33 ## [2195B - Heapify 1](/contest/2195/problem/B "Codeforces Round 1080 (Div. 3)") 34 35 **Rate the problem!** 36 37 * Epic 38 * Good 39 * Moderate 40 * Bad 41 * Horrendous 42 43 **Editorial** 44 45 Tutorial is loading... 46 47 **Code** 48 49 ``` 50 #include<bits/stdc++.h> 51 using namespace std; 52 using ll=long long; 53 54 int main() 55 { 56 cin.tie(0)->sync_with_stdio(0); 57 int t;cin>>t; 58 while(t--) 59 { 60 int n;cin>>n; 61 vector<int>a(n+1); 62 for(int i=1;i<=n;i++) 63 { 64 cin>>a[i]; 65 } 66 for(int i=1;i<=n;i+=2) 67 { 68 for(int j=i;j<=n;j*=2) 69 { 70 for(int k=i*2;k<=n;k*=2) 71 { 72 if(a[k/2]>a[k])swap(a[k/2],a[k]); 73 } 74 } 75 } 76 if(is_sorted(begin(a),end(a)))cout<<"YES\n"; 77 else cout<<"NO\n"; 78 } 79 } 80 ``` 81 82 ## [2195C - Dice Roll Sequence](/contest/2195/problem/C "Codeforces Round 1080 (Div. 3)") 83 84 **Rate the problem!** 85 86 * Epic 87 * Good 88 * Moderate 89 * Bad 90 * Horrendous 91 92 **Editorial** 93 94 Tutorial is loading... 95 96 **Code** 97 98 ``` 99 #include <bits/stdc++.h> 100 using namespace std; 101 102 typedef long long int ll; 103 104 void solve() { 105 int n; 106 cin >> n; 107 vector<int> a(n); 108 for (int i = 0; i < n; i++) cin >> a[i]; 109 110 int ans = 0; 111 for (int i = 1; i < n; i++) { 112 if (a[i] + a[i-1] == 7 or a[i] == a[i-1]) ans++, i++; 113 } 114 115 cout << ans; 116 } 117 118 int main() { 119 ios::sync_with_stdio(0); cin.tie(0); 120 ll tc = 1; 121 cin >> tc; 122 for (ll i = 1; i <= tc; i++) { 123 solve(); 124 cout << '\n'; 125 } 126 } 127 ``` 128 129 ## [2195D - Absolute Cinema](/contest/2195/problem/D "Codeforces Round 1080 (Div. 3)") 130 131 **Rate the problem!** 132 133 * Epic 134 * Good 135 * Moderate 136 * Bad 137 * Horrendous 138 139 **Editorial** 140 141 Tutorial is loading... 142 143 **Code** 144 145 ``` 146 #include<bits/stdc++.h> 147 using namespace std; 148 using ll=long long; 149 150 vector<ll>solve(ll n,vector<ll>f) 151 { 152 vector<ll>vec(n); 153 for(int i=1;i+1<n;i++) 154 { 155 if((f[i+1]+f[i-1]-2*f[i])%2!=0)return {}; 156 vec[i]=(f[i+1]+f[i-1]-2*f[i])/2; 157 if(abs(vec[i])>1000)return {}; 158 } 159 auto g=[&](ll j) 160 { 161 ll w=f[j]; 162 for(int i=1;i+1<n;i++) 163 { 164 w-=vec[i]*abs(i-j); 165 } 166 return w; 167 }; 168 ll g1=g(0),gn=g(n-1); 169 if(gn%(n-1)!=0)return {}; 170 if(g1%(n-1)!=0)return {}; 171 vec[0]=gn/(n-1); 172 vec[n-1]=g1/(n-1); 173 if(abs(vec[0])>1000||abs(vec[n-1])>1000)return {}; 174 return vec; 175 } 176 177 int main() 178 { 179 int t;cin>>t; 180 while(t--) 181 { 182 ll n;cin>>n; 183 vector<ll>f(n); 184 for(ll&i:f)cin>>i; 185 auto a=solve(n,f); 186 assert(a.size()==n); 187 for(int i=0;i<n;i++)cout<<a[i]<<" \n"[i+1==n]; 188 } 189 } 190 ``` 191 192 ## [2195E - Idiot First Search](/contest/2195/problem/E "Codeforces Round 1080 (Div. 3)") 193 194 **Rate the problem!** 195 196 * Epic 197 * Good 198 * Moderate 199 * Bad 200 * Horrendous 201 202 **Editorial** 203 204 Tutorial is loading... 205 206 **Code** 207 208 ``` 209 #include<bits/stdc++.h> 210 using namespace std; 211 using ll=long long; 212 const ll md=1000000007; 213 214 int main() 215 { 216 int t;cin>>t; 217 while(t--) 218 { 219 ll n;cin>>n; 220 vector<ll>L(n),R(n); 221 for(int i=0;i<n;i++) 222 { 223 cin>>L[i]>>R[i]; 224 L[i]--;R[i]--; 225 } 226 vector<ll>dp(n); 227 auto dfs1=[&](auto dfs1,int x)->ll 228 { 229 if(L[x]==-1)return dp[x]=1; 230 else return dp[x]=(dfs1(dfs1,L[x])+dfs1(dfs1,R[x])+3)%md; 231 }; 232 dfs1(dfs1,0); 233 auto dfs2=[&](auto dfs2,int x)->void 234 { 235 if(L[x]==-1)return; 236 else 237 { 238 dp[L[x]]=(dp[L[x]]+dp[x])%md; 239 dp[R[x]]=(dp[R[x]]+dp[x])%md; 240 dfs2(dfs2,L[x]); 241 dfs2(dfs2,R[x]); 242 } 243 }; 244 dfs2(dfs2,0); 245 for(int i=0;i<n;i++)cout<<dp[i]<<" \n"[i+1==n]; 246 } 247 } 248 ``` 249 250 ## [2195F - Parabola Independence](/contest/2195/problem/F "Codeforces Round 1080 (Div. 3)") 251 252 **Rate the problem!** 253 254 * Epic 255 * Good 256 * Moderate 257 * Bad 258 * Horrendous 259 260 **Editorial** 261 262 Tutorial is loading... 263 264 **Code** 265 266 ``` 267 #include<bits/stdc++.h> 268 using namespace std; 269 using ll=long long; 270 271 struct Quad{ll a,b,c;}; // ax^2+bx+c 272 273 // f(x) < g(x) for all x 274 bool comp(Quad f,Quad g) 275 { 276 if(f.a>g.a)return false; 277 else if(f.a==g.a)return f.b==g.b&&f.c<g.c; 278 else 279 { 280 Quad Q{g.a-f.a,g.b-f.b,g.c-f.c}; 281 return Q.b*Q.b-4*Q.a*Q.c<0; 282 } 283 } 284 285 int main() 286 { 287 cin.tie(0)->sync_with_stdio(0); 288 int t;cin>>t; 289 while(t--) 290 { 291 int n;cin>>n; 292 vector<Quad>vec(n); 293 for(Quad&Q:vec)cin>>Q.a>>Q.b>>Q.c; 294 vector<vector<int>>adj1(n),adj2(n); 295 vector<int>id1(n),id2(n),dp1(n,1),dp2(n,1); 296 for(int i=0;i<n;i++) 297 { 298 for(int j=0;j<n;j++) 299 { 300 if(comp(vec[i],vec[j])) 301 { 302 adj1[i].push_back(j); 303 id1[j]++; 304 adj2[j].push_back(i); 305 id2[i]++; 306 } 307 } 308 } 309 queue<int>Q; 310 for(int i=0;i<n;i++)if(id1[i]==0)Q.push(i); 311 while(!Q.empty()) 312 { 313 int a=Q.front();Q.pop(); 314 for(int i:adj1[a]) 315 { 316 id1[i]--;dp1[i]=max(dp1[i],dp1[a]+1); 317 if(id1[i]==0)Q.push(i); 318 } 319 } 320 for(int i=0;i<n;i++)if(id2[i]==0)Q.push(i); 321 while(!Q.empty()) 322 { 323 int a=Q.front();Q.pop(); 324 for(int i:adj2[a]) 325 { 326 id2[i]--;dp2[i]=max(dp2[i],dp2[a]+1); 327 if(id2[i]==0)Q.push(i); 328 } 329 } 330 for(int i=0;i<n;i++)cout<<dp1[i]+dp2[i]-1<<" \n"[i+1==n]; 331 } 332 } 333 ``` 334 335 ## [2195G - Idiot First Search and Queries](/contest/2195/problem/G "Codeforces Round 1080 (Div. 3)") 336 337 **Rate the problem!** 338 339 * Epic 340 * Good 341 * Moderate 342 * Bad 343 * Horrendous 344 345 **Editorial** 346 347 Tutorial is loading... 348 349 **Code** 350 351 ``` 352 #include<bits/stdc++.h> 353 using namespace std; 354 using ll=long long; 355 356 int main() 357 { 358 ll t;cin>>t; 359 while(t--) 360 { 361 ll n,q;cin>>n>>q; 362 vector<ll>L(n),R(n),P(n,-1); 363 for(int i=0;i<n;i++)P[i]=i; 364 for(int i=0;i<n;i++) 365 { 366 cin>>L[i]>>R[i]; 367 L[i]--;R[i]--; 368 if(L[i]!=-1) 369 { 370 P[L[i]]=i; 371 P[R[i]]=i; 372 } 373 } 374 vector<ll>dp(n); 375 vector<array<int,20>>lift(n); 376 auto dfs1=[&](auto dfs1,int x)->ll 377 { 378 if(L[x]==-1)return dp[x]=1; 379 else return dp[x]=(dfs1(dfs1,L[x])+dfs1(dfs1,R[x])+3); 380 }; 381 dfs1(dfs1,0); 382 vector<ll>euler,tin(n); 383 auto dfs2=[&](auto dfs2,int x)->void 384 { 385 tin[x]=euler.size(); 386 lift[x][0]=P[x]; 387 for(int j=1;j<20;j++) 388 { 389 lift[x][j]=lift[lift[x][j-1]][j-1]; 390 } 391 if(L[x]==-1) 392 { 393 euler.push_back(x); 394 return; 395 } 396 else 397 { 398 dp[L[x]]=(dp[L[x]]+dp[x]); 399 dp[R[x]]=(dp[R[x]]+dp[x]); 400 euler.push_back(x); 401 dfs2(dfs2,L[x]); 402 euler.push_back(x); 403 dfs2(dfs2,R[x]); 404 euler.push_back(x); 405 } 406 }; 407 dfs2(dfs2,0); 408 while(q--) 409 { 410 ll v,k;cin>>v>>k; 411 v--; 412 ll w=v; 413 for(int j=19;j>=0;j--) 414 { 415 if(dp[v]-dp[lift[w][j]]<=k)w=lift[w][j]; 416 } 417 k-=dp[v]-dp[w]; 418 cout<<euler[tin[w]+k]+1<<" \n"[q==0]; 419 } 420 } 421 } 422 ``` 423 424 ## [2195H - Codeforces Heuristic Contest 001](/contest/2195/problem/H "Codeforces Round 1080 (Div. 3)") 425 426 **Rate the problem!** 427 428 * Epic 429 * Good 430 * Moderate 431 * Bad 432 * Horrendous 433 434 **Editorial** 435 436 Tutorial is loading... 437 438 **Code** 439 440 ``` 441 #include<bits/stdc++.h> 442 using namespace std; 443 using ll=long long; 444 445 string base[9]= 446 { 447 "AABBCCDEE", 448 "ABFFCDDGE", 449 "HHFIJKLLG", 450 "MHIJJKKLG", 451 "MMINNOOPP", 452 "QRNSOTTUP", 453 "QRRSSTVUU", 454 "WQXXYVVZ_", 455 "WWXYYZZ__" 456 }; 457 458 struct Point 459 { 460 ll x,y; 461 Point(ll xx,ll yy):x(xx),y(yy){} 462 }; 463 464 ostream& operator<<(ostream&os,const Point& P) 465 { 466 os<<P.x<<" "<<P.y; 467 return os; 468 } 469 470 using Pgon=vector<Point>; 471 472 vector<Pgon>basis(string b[],int n) 473 { 474 vector<Pgon>res; 475 map<char,Pgon>mp; 476 for(int i=0;i<n;i++) 477 { 478 for(int j=0;j<n;j++) 479 { 480 mp[b[i][j]].emplace_back(i+1,j+1); 481 } 482 } 483 for(auto[c,v]:mp)res.push_back(v); 484 return res; 485 } 486 487 void solve(int n) 488 { 489 if(n==1) 490 { 491 cout<<"2\n"; 492 cout<<"1 1 1 2 2 1\n"; 493 cout<<"2 3 3 2 3 3\n"; 494 } 495 else if(n%2==0) 496 { 497 cout<<3*n*n<<"\n"; 498 int cnt=0; 499 for(int i=1;i<=3*n;i+=3) 500 { 501 for(int j=1;j<=3*n;j+=2) 502 { 503 cout<<Point(i,j)<<" "<<Point(i,j+1)<<" "<<Point(i+1,j)<<"\n"; 504 cout<<Point(i+1,j+1)<<" "<<Point(i+2,j+1)<<" "<<Point(i+2,j)<<"\n"; 505 cnt+=2; 506 } 507 } 508 assert(cnt==3*n*n); 509 } 510 else 511 { 512 cout<<3*n*n<<"\n"; 513 int cnt=0; 514 for(auto p:basis(base,9)) 515 { 516 cout<<p[0]<<" "<<p[1]<<" "<<p[2]<<"\n"; 517 cnt++; 518 } 519 for(int i=1;i<=9;i+=3) 520 { 521 // 3*n-9=3*(n-3)=even 522 for(int j=10;j<=3*n;j+=2) 523 { 524 cout<<Point(i,j)<<" "<<Point(i,j+1)<<" "<<Point(i+1,j)<<"\n"; 525 cout<<Point(i+1,j+1)<<" "<<Point(i+2,j)<<" "<<Point(i+2,j+1)<<"\n"; 526 cnt+=2; 527 } 528 } 529 for(int i=10;i<=3*n;i+=2) 530 { 531 for(int j=1;j<=3*n;j+=3) 532 { 533 cout<<Point(i,j)<<" "<<Point(i,j+1)<<" "<<Point(i+1,j)<<"\n"; 534 cout<<Point(i+1,j+1)<<" "<<Point(i+1,j+2)<<" "<<Point(i,j+2)<<"\n"; 535 cnt+=2; 536 } 537 } 538 assert(cnt==3*n*n); 539 } 540 } 541 542 int main() 543 { 544 cin.tie(0)->sync_with_stdio(0); 545 int t;cin>>t; 546 while(t--) 547 { 548 int n;cin>>n; 549 solve(n); 550 } 551 } 552 ``` 553 554 Thank you for participating, and hope to see you again soon!