776.md (12127B)
1 Source: https://codeforces.com/blog/entry/50622 2 3 Tutorial is loading... 4 5 **Code** 6 7 ``` 8 #include <algorithm> 9 #include <bitset> 10 #include <cassert> 11 #include <climits> 12 #include <cmath> 13 #include <cstdio> 14 #include <cstdlib> 15 #include <cstring> 16 #include <deque> 17 #include <iomanip> 18 #include <iostream> 19 #include <map> 20 #include <numeric> 21 #include <queue> 22 #include <set> 23 #include <stack> 24 #include <string> 25 26 #ifdef PRINTERS 27 #include "printers.hpp" 28 using namespace printers; 29 #define tr(a) cerr<<#a<<": "<<a<<endl; 30 #else 31 #define tr(a) 32 #endif 33 34 #define ll long long 35 #define pb push_back 36 #define mp make_pair 37 #define pii pair<int,int> 38 #define vi vector<int> 39 #define all(a) (a).begin(),(a).end() 40 #define F first 41 #define S second 42 #define sz(x) (int)x.size() 43 #define hell 1000000007 44 #define endl '\n' 45 #define rep(i,a,b) for(int i=a;i<b;i++) 46 using namespace std; 47 48 void solve(){ 49 string a,b; 50 cin>>a>>b; 51 vector<string>taken; 52 int n; 53 cin>>n; 54 rep(i,0,n){ 55 cout<<a<<" "<<b<<endl; 56 string c,d; 57 cin>>c>>d; 58 if(c==a)a=d; 59 else b=d; 60 } 61 cout<<a<<" "<<b<<endl; 62 } 63 64 int main(){ 65 ios_base::sync_with_stdio(false); 66 cin.tie(0); 67 cout.tie(0); 68 int t=1; 69 while(t--){ 70 solve(); 71 } 72 return 0; 73 } 74 ``` 75 76 Tutorial is loading... 77 78 **Code** 79 80 ``` 81 #include <bits/stdc++.h> 82 using namespace std; 83 84 int sieve[100005]; 85 86 int main() 87 { 88 int i, n, j; 89 cin>>n; 90 for(i=2; i<=n+1; i++) 91 { 92 if(!sieve[i]) 93 for(j=2*i; j<=n+1; j+=i) 94 sieve[j]=1; 95 } 96 97 if(n>2) 98 cout<<"2\n"; 99 else 100 cout<<"1\n"; 101 102 for(i=2; i<=n+1; i++) 103 { 104 if(!sieve[i]) 105 cout<<"1 "; 106 else 107 cout<<"2 "; 108 } 109 110 return 0; 111 } 112 ``` 113 114 Tutorial is loading... 115 116 **Code** 117 118 ``` 119 #include <algorithm> 120 #include <bitset> 121 #include <cassert> 122 #include <climits> 123 #include <cmath> 124 #include <cstdio> 125 #include <cstdlib> 126 #include <cstring> 127 #include <deque> 128 #include <iomanip> 129 #include <iostream> 130 #include <map> 131 #include <numeric> 132 #include <queue> 133 #include <set> 134 #include <stack> 135 #include <string> 136 137 #ifdef PRINTERS 138 #include "printers.hpp" 139 using namespace printers; 140 #define tr(a) cerr<<#a<<": "<<a<<endl; 141 #else 142 #define tr(a) 143 #endif 144 #define ll long long 145 #define pb push_back 146 #define mp make_pair 147 #define pii pair<int,int> 148 #define vi vector<int> 149 #define all(a) (a).begin(),(a).end() 150 #define F first 151 #define S second 152 #define sz(x) (int)x.size() 153 #define hell 1000000007 154 #define endl '\n' 155 #define rep(i,a,b) for(int i=a;i<b;i++) 156 using namespace std; 157 158 void solve(){ 159 int N,k; 160 scanf("%d%d",&N,&k); 161 ll x[N+1]; 162 x[0]=0; 163 rep(i,0,N)scanf("%lld",&x[i+1]); 164 partial_sum(x,x+N+1,x); 165 if(k==1){ 166 ll ans=0; 167 map<ll,int>m; 168 for(int i=N;i>=0;i--){ 169 if(m.find(x[i]+1)!=m.end()) 170 ans+=m[x[i]+1]; 171 m[x[i]]++; 172 } 173 printf("%lld\n",ans); 174 } 175 else if(k==-1){ 176 ll ans=0; 177 map<ll,int>m; 178 for(int i=N;i>=0;i--){ 179 if(m.find(x[i]+1)!=m.end()) 180 ans+=m[x[i]+1]; 181 if(m.find(x[i]-1)!=m.end()) 182 ans+=m[x[i]-1]; 183 184 m[x[i]]++; 185 } 186 printf("%lld\n",ans); 187 } 188 else{ 189 ll ans=0; 190 map<ll,int>m; 191 for(int i=N;i>=0;i--){ 192 ll cur=1; 193 while(true){ 194 if(abs(cur)>=1e15)break; 195 if(m.find(x[i]+cur)!=m.end()) 196 ans+=m[x[i]+cur]; 197 cur*=k; 198 } 199 m[x[i]]++; 200 } 201 printf("%lld\n",ans); 202 } 203 } 204 205 signed main(){ 206 int t=1; 207 while(t--){ 208 solve(); 209 } 210 return 0; 211 } 212 ``` 213 214 Tutorial is loading... 215 216 **Code** 217 218 ``` 219 #include <bits/stdc++.h> 220 using namespace std; 221 #define mem(x,y) memset(x,y,sizeof(x)) 222 #define bitcount __builtin_popcountll 223 #define mod 1000000007 224 #define N 1000009 225 #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 226 #define ss(s) cin>>s; 227 #define si(x) scanf("%d",&x); 228 #define sl(x) cin>>x; 229 #define pb push_back 230 #define mp make_pair 231 #define all(v) v.begin(),v.end() 232 #define S second 233 #define F first 234 #define ll long long 235 int n,m; 236 vector<int> arr[N]; 237 int arr1[N]; 238 vector<pair<int,int > > adj[100008]; //max-size 239 void graph(int n){for(int i=1;i<=n;i++){ 240 int x = arr[i][0]; 241 int y = arr[i][1]; 242 adj[x].push_back(mp(y,arr1[i] )); //arr1[i] stores th color of the edge 243 adj[y].push_back(mp(x,arr1[i]) );} 244 245 } 246 int col[N]; 247 bool vis[N]; 248 int main(){ 249 //fast //uncomment on submission 250 cin>>n>>m; 251 assert(n>=2 && n<=100000); 252 assert(m>=2 && m<=100000); 253 for(int i =1;i<=n;i++)cin >> arr1[i]; 254 for(int i = 1;i<=m;i++){ 255 int sz; 256 cin >> sz; 257 for(int j =0;j<sz;j++){ 258 int y ; 259 cin >> y; 260 arr[y].push_back(i); 261 } 262 } 263 graph(n); 264 mem(col,-1); 265 mem(vis,false); 266 bool p = true; 267 for(int i = 1;i<=m;i++){ 268 if(!vis[i] && adj[i].size()){ 269 col[i] = 0; 270 vis[i] = true; 271 queue <int > q; 272 q.push(i); 273 274 while(q.size()){ 275 int node = q.front(); 276 q.pop(); 277 278 for(auto pi:adj[node]){ 279 int co = col[node]; 280 if(pi.S == 0){ //if the edge is 0 then give the opposite color. 281 co = 1 - co; 282 283 } 284 if(vis[pi.F] && col[pi.F] != co){ 285 p = false; 286 } 287 if(!vis[pi.F]){ 288 col[pi.F] = co; 289 vis[pi.F] = true; 290 q.push(pi.F); 291 292 } 293 } 294 } 295 } 296 } 297 298 if(!p)cout<<"NO"; 299 else cout<<"YES"; 300 301 } 302 ``` 303 304 Tutorial is loading... 305 306 **Code** 307 308 ``` 309 #include <bits/stdc++.h> 310 using namespace std; 311 #define ll long long 312 #define MOD 1000000007 313 #define ll long long 314 #define pb push_back 315 #define pii pair<int,int> 316 #define vi vector<int> 317 #define all(a) (a).begin(),(a).end() 318 #define F first 319 #define S second 320 #define endl '\n' 321 #define PI 3.14159265359d 322 #define sz(x) (int)x.size() 323 ll phi(ll n) 324 { 325 ll i,res=n; 326 for(i=2;i*i<=n;i++) 327 if(n%i==0) 328 { 329 while(n%i==0) 330 n/=i; 331 res-=res/i; 332 } 333 if(n>1) 334 res-=res/n; 335 return res; 336 } 337 int main() 338 { 339 ll n,k,res; 340 cin>>n>>k; 341 res=n; 342 k=(k+1)/2; 343 while(k--) 344 { 345 res=phi(res); 346 if(res==1) 347 break; 348 } 349 cout<<res%MOD; 350 return 0; 351 } 352 ``` 353 354 Tutorial is loading... 355 356 **Code** 357 358 ``` 359 #include<bits/stdc++.h> 360 using namespace std; 361 #define sd(x) scanf("%d",&x) 362 #define slld(x) scanf("%lld",&x) 363 #define ss(x) scanf("%s",x) 364 #define ll long long 365 #define mod 1000000007 366 #define bitcount __builtin_popcountll 367 #define pb push_back 368 #define fi first 369 #define se second 370 #define mp make_pair 371 #define pi pair<int,int> 372 pi arr[100005]; 373 int n,m; 374 bool cmp(pi x, pi y) 375 { 376 int a=min(x.se-x.fi-1,n-2-(x.se-x.fi-1)); 377 int b=min(y.se-y.fi-1,n-2-(y.se-y.fi-1)); 378 return a<b; 379 } 380 vector<int>nodes[100005]; 381 vector<int>v[100005],v2[100005]; 382 int de[100005],siz[100005]; 383 void dfs1(int node, int par) 384 { 385 siz[node]=1; 386 for(int i=0;i<v[node].size();i++) 387 { 388 if(de[v[node][i]]==0&&v[node][i]!=par) 389 { 390 dfs1(v[node][i],node); 391 siz[node]+=siz[v[node][i]]; 392 } 393 } 394 } 395 int dfs2(int node, int par,int s) 396 { 397 int maxi=0,maxinode; 398 for(int i=0;i<v[node].size();i++) 399 { 400 if(de[v[node][i]]==0&&v[node][i]!=par&&siz[v[node][i]]>s/2) 401 { 402 return dfs2(v[node][i],node,s); 403 } 404 } 405 //printf("%d\n",node ); 406 return node; 407 } 408 int decompose(int node) 409 { 410 dfs1(node,-1); 411 int cen=dfs2(node,-1,siz[node]); 412 // printf("%d\n",cen ); 413 de[cen]=1; 414 for(int i=0;i<v[cen].size();i++) 415 { 416 if(de[v[cen][i]]==0) 417 { 418 int x=decompose(v[cen][i]); 419 //printf("%d\n", x); 420 v2[cen].pb(x); 421 v2[x].pb(cen); 422 } 423 } 424 425 return cen; 426 } 427 int level[100005]; 428 int main() 429 { 430 //freopen("in.txt","r",stdin); 431 //freopen("out.txt","w",stdout); 432 int i,j,k; 433 sd(n); 434 sd(m); 435 for(i=1;i<=m;i++) 436 { 437 sd(arr[i].fi); 438 sd(arr[i].se); 439 if(arr[i].fi>arr[i].se) 440 { 441 swap(arr[i].fi,arr[i].se); 442 } 443 } 444 sort(arr+1,arr+m+1,cmp); 445 set<int>s; 446 for(i=1;i<=n;i++) 447 s.insert(i); 448 k=0; 449 for(i=1;i<=m;i++) 450 { 451 if(arr[i].se-arr[i].fi-1<=n-2-(arr[i].se-arr[i].fi-1)) 452 { 453 nodes[k].pb(arr[i].fi); 454 set<int>::iterator it=s.upper_bound(arr[i].fi); 455 while((*it)!=arr[i].se) 456 { 457 nodes[k].pb(*it); 458 it++; 459 } 460 nodes[k].pb(arr[i].se); 461 for(j=1;j<nodes[k].size()-1;j++) 462 s.erase(nodes[k][j]); 463 } 464 else 465 { 466 while(*s.begin()!=arr[i].fi) 467 { 468 nodes[k].pb(*s.begin()); 469 s.erase(s.begin()); 470 } 471 nodes[k].pb(arr[i].fi); 472 nodes[k].pb(arr[i].se); 473 int l=nodes[k].size(); 474 set<int>::iterator it=s.upper_bound(arr[i].se); 475 while(it!=s.end()) 476 { 477 nodes[k].pb(*it); 478 it++; 479 } 480 for(;l<nodes[k].size();l++) 481 s.erase(nodes[k][l]); 482 } 483 reverse(nodes[k].begin(), nodes[k].end()); 484 k++; 485 } 486 while(s.size()!=0) 487 { 488 nodes[k].pb(*s.begin()); 489 s.erase(s.begin()); 490 } 491 reverse(nodes[k].begin(), nodes[k].end()); 492 k++; 493 sort(nodes,nodes+k); 494 map<pi,int>m1; 495 for(i=0;i<k;i++) 496 { 497 for(j=0;j<nodes[i].size()-1;j++) 498 { 499 if(nodes[i][j]==nodes[i][j+1]+1) 500 continue; 501 else if(m1.find(mp(nodes[i][j],nodes[i][j+1]))!=m1.end()) 502 { 503 v[m1[mp(nodes[i][j],nodes[i][j+1])]].pb(i+1); 504 v[i+1].pb(m1[mp(nodes[i][j],nodes[i][j+1])]); 505 m1.erase(mp(nodes[i][j],nodes[i][j+1])); 506 } 507 else 508 { 509 m1[mp(nodes[i][j],nodes[i][j+1])]=i+1; 510 } 511 } 512 j=nodes[i].size()-1; 513 if(nodes[i][0]!=n||nodes[i][j]!=1) 514 { 515 if(m1.find(mp(nodes[i][0],nodes[i][j]))!=m1.end()) 516 { 517 v[m1[mp(nodes[i][0],nodes[i][j])]].pb(i+1); 518 v[i+1].pb(m1[mp(nodes[i][0],nodes[i][j])]); 519 m1.erase(mp(nodes[i][0],nodes[i][j])); 520 } 521 else 522 { 523 m1[mp(nodes[i][0],nodes[i][j])]=i+1; 524 } 525 } 526 } 527 for(i=1;i<=n;i++) 528 level[i]=1e6; 529 int cen=decompose(1); 530 //printf("%d\n",cen ); 531 queue<int>q; 532 i=0; 533 q.push(cen); 534 while(!q.empty()) 535 { 536 j=q.size(); 537 while(j--) 538 { 539 int z=q.front(); 540 q.pop(); 541 level[z]=i; 542 for(int l=0;l<v2[z].size();l++) 543 { 544 if(level[v2[z][l]]==1e6) 545 { 546 q.push(v2[z][l]); 547 } 548 } 549 } 550 i++; 551 } 552 for(i=1;i<=k;i++){ 553 //printf("%d %d\n",v2[i].size(),level[i] ); 554 printf("%d",level[i]+1 ); 555 if(i!=k) 556 printf(" "); 557 } 558 printf("\n"); 559 return 0; 560 } 561 ``` 562 563 Tutorial is loading... 564 565 **Code** 566 567 ``` 568 #include<bits/stdc++.h> 569 using namespace std; 570 #define sd(x) scanf("%lld",&x) 571 #define slld(x) scanf("%lld",&x) 572 #define ss(x) scanf("%s",x) 573 #define ll long long 574 #define mod 65536 575 #define bitcount __builtin_popcountll 576 #define pb push_back 577 #define fi first 578 #define se second 579 #define mp make_pair 580 #define pi pair<int,int> 581 ll dp[17][65538][17]; 582 char a[20]; 583 ll b[20]; 584 ll mo[1100005]; 585 ll f(ll m,ll p,ll pos) 586 { 587 if(dp[m][p][pos]!=-1) 588 return dp[m][p][pos]; 589 if(pos==0) 590 { 591 if(((1<<m)&p)) 592 dp[m][p][pos]=1; 593 else 594 dp[m][p][pos]=0; 595 return dp[m][p][pos]; 596 } 597 ll j=0; 598 for(ll i=0;i<=15;i++) 599 { 600 j+=f(max(m,i),mo[p*16+i],pos-1); 601 } 602 return dp[m][p][pos]=j; 603 } 604 int main() 605 { 606 //freopen("in.txt","r",stdin); 607 //freopen("out.txt","w",stdout); 608 ll t,n,i,j,k,l,r,m,p,ans1; 609 mo[0]=0; 610 for(i=1;i<=1100000;i++) 611 { 612 mo[i]=mo[i-1]+1; 613 if(mo[i]==mod) 614 mo[i]=0; 615 } 616 memset(dp,-1,sizeof dp); 617 f(0,0,16); 618 sd(t); 619 while(t--) 620 { 621 ss(a); 622 n=strlen(a); 623 l=0; 624 for(i=0;i<n;i++) 625 { 626 l=l*16; 627 if(a[i]>='0'&&a[i]<='9') 628 l+=a[i]-'0'; 629 else 630 l+=a[i]-'a'+10; 631 } 632 ans1=0; 633 if(l>0) 634 { 635 l--; 636 j=l; 637 for(i=0;i<n;i++) 638 { 639 b[i]=j%16; 640 j/=16; 641 } 642 m=p=0; 643 for(j=n-1;j>=0;j--) 644 { 645 for(k=0;k<b[j];k++) 646 ans1-=dp[max(m,k)][mo[p*16+k]][j]; 647 m=max(m,b[j]); 648 p=mo[p*16+b[j]]; 649 } 650 ans1-=dp[m][p][0]; 651 } 652 ss(a); 653 n=strlen(a); 654 r=0; 655 for(i=0;i<n;i++) 656 { 657 r=r*16; 658 if(a[i]>='0'&&a[i]<='9') 659 r+=a[i]-'0'; 660 else 661 r+=a[i]-'a'+10; 662 } 663 j=r; 664 for(i=0;i<n;i++) 665 { 666 b[i]=j%16; 667 j/=16; 668 } 669 m=p=0; 670 for(j=n-1;j>=0;j--) 671 { 672 for(k=0;k<b[j];k++) 673 ans1+=dp[max(m,k)][mo[p*16+k]][j]; 674 m=max(m,b[j]); 675 p=mo[p*16+b[j]]; 676 } 677 ans1+=dp[m][p][0]; 678 printf("%lld\n",ans1); 679 } 680 return 0; 681 } 682 ```