codeforces-scrape

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

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 ```