Tutorial is loading...
Code
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#ifdef PRINTERS
#include "printers.hpp"
using namespace printers;
#define tr(a) cerr<<#a<<": "<<a<<endl;
#else
#define tr(a)
#endif
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define hell 1000000007
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
void solve(){
string a,b;
cin>>a>>b;
vector<string>taken;
int n;
cin>>n;
rep(i,0,n){
cout<<a<<" "<<b<<endl;
string c,d;
cin>>c>>d;
if(c==a)a=d;
else b=d;
}
cout<<a<<" "<<b<<endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
while(t--){
solve();
}
return 0;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
int sieve[100005];
int main()
{
int i, n, j;
cin>>n;
for(i=2; i<=n+1; i++)
{
if(!sieve[i])
for(j=2*i; j<=n+1; j+=i)
sieve[j]=1;
}
if(n>2)
cout<<"2\n";
else
cout<<"1\n";
for(i=2; i<=n+1; i++)
{
if(!sieve[i])
cout<<"1 ";
else
cout<<"2 ";
}
return 0;
}
Tutorial is loading...
Code
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#ifdef PRINTERS
#include "printers.hpp"
using namespace printers;
#define tr(a) cerr<<#a<<": "<<a<<endl;
#else
#define tr(a)
#endif
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define hell 1000000007
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
void solve(){
int N,k;
scanf("%d%d",&N,&k);
ll x[N+1];
x[0]=0;
rep(i,0,N)scanf("%lld",&x[i+1]);
partial_sum(x,x+N+1,x);
if(k==1){
ll ans=0;
map<ll,int>m;
for(int i=N;i>=0;i--){
if(m.find(x[i]+1)!=m.end())
ans+=m[x[i]+1];
m[x[i]]++;
}
printf("%lld\n",ans);
}
else if(k==-1){
ll ans=0;
map<ll,int>m;
for(int i=N;i>=0;i--){
if(m.find(x[i]+1)!=m.end())
ans+=m[x[i]+1];
if(m.find(x[i]-1)!=m.end())
ans+=m[x[i]-1];
m[x[i]]++;
}
printf("%lld\n",ans);
}
else{
ll ans=0;
map<ll,int>m;
for(int i=N;i>=0;i--){
ll cur=1;
while(true){
if(abs(cur)>=1e15)break;
if(m.find(x[i]+cur)!=m.end())
ans+=m[x[i]+cur];
cur*=k;
}
m[x[i]]++;
}
printf("%lld\n",ans);
}
}
signed main(){
int t=1;
while(t--){
solve();
}
return 0;
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x))
#define bitcount __builtin_popcountll
#define mod 1000000007
#define N 1000009
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ss(s) cin>>s;
#define si(x) scanf("%d",&x);
#define sl(x) cin>>x;
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define S second
#define F first
#define ll long long
int n,m;
vector<int> arr[N];
int arr1[N];
vector<pair<int,int > > adj[100008]; //max-size
void graph(int n){for(int i=1;i<=n;i++){
int x = arr[i][0];
int y = arr[i][1];
adj[x].push_back(mp(y,arr1[i] )); //arr1[i] stores th color of the edge
adj[y].push_back(mp(x,arr1[i]) );}
}
int col[N];
bool vis[N];
int main(){
//fast //uncomment on submission
cin>>n>>m;
assert(n>=2 && n<=100000);
assert(m>=2 && m<=100000);
for(int i =1;i<=n;i++)cin >> arr1[i];
for(int i = 1;i<=m;i++){
int sz;
cin >> sz;
for(int j =0;j<sz;j++){
int y ;
cin >> y;
arr[y].push_back(i);
}
}
graph(n);
mem(col,-1);
mem(vis,false);
bool p = true;
for(int i = 1;i<=m;i++){
if(!vis[i] && adj[i].size()){
col[i] = 0;
vis[i] = true;
queue <int > q;
q.push(i);
while(q.size()){
int node = q.front();
q.pop();
for(auto pi:adj[node]){
int co = col[node];
if(pi.S == 0){ //if the edge is 0 then give the opposite color.
co = 1 - co;
}
if(vis[pi.F] && col[pi.F] != co){
p = false;
}
if(!vis[pi.F]){
col[pi.F] = co;
vis[pi.F] = true;
q.push(pi.F);
}
}
}
}
}
if(!p)cout<<"NO";
else cout<<"YES";
}
Tutorial is loading...
Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define endl '\n'
#define PI 3.14159265359d
#define sz(x) (int)x.size()
ll phi(ll n)
{
ll i,res=n;
for(i=2;i*i<=n;i++)
if(n%i==0)
{
while(n%i==0)
n/=i;
res-=res/i;
}
if(n>1)
res-=res/n;
return res;
}
int main()
{
ll n,k,res;
cin>>n>>k;
res=n;
k=(k+1)/2;
while(k--)
{
res=phi(res);
if(res==1)
break;
}
cout<<res%MOD;
return 0;
}
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)
#define ll long long
#define mod 1000000007
#define bitcount __builtin_popcountll
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
pi arr[100005];
int n,m;
bool cmp(pi x, pi y)
{
int a=min(x.se-x.fi-1,n-2-(x.se-x.fi-1));
int b=min(y.se-y.fi-1,n-2-(y.se-y.fi-1));
return a<b;
}
vector<int>nodes[100005];
vector<int>v[100005],v2[100005];
int de[100005],siz[100005];
void dfs1(int node, int par)
{
siz[node]=1;
for(int i=0;i<v[node].size();i++)
{
if(de[v[node][i]]==0&&v[node][i]!=par)
{
dfs1(v[node][i],node);
siz[node]+=siz[v[node][i]];
}
}
}
int dfs2(int node, int par,int s)
{
int maxi=0,maxinode;
for(int i=0;i<v[node].size();i++)
{
if(de[v[node][i]]==0&&v[node][i]!=par&&siz[v[node][i]]>s/2)
{
return dfs2(v[node][i],node,s);
}
}
//printf("%d\n",node );
return node;
}
int decompose(int node)
{
dfs1(node,-1);
int cen=dfs2(node,-1,siz[node]);
// printf("%d\n",cen );
de[cen]=1;
for(int i=0;i<v[cen].size();i++)
{
if(de[v[cen][i]]==0)
{
int x=decompose(v[cen][i]);
//printf("%d\n", x);
v2[cen].pb(x);
v2[x].pb(cen);
}
}
return cen;
}
int level[100005];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int i,j,k;
sd(n);
sd(m);
for(i=1;i<=m;i++)
{
sd(arr[i].fi);
sd(arr[i].se);
if(arr[i].fi>arr[i].se)
{
swap(arr[i].fi,arr[i].se);
}
}
sort(arr+1,arr+m+1,cmp);
set<int>s;
for(i=1;i<=n;i++)
s.insert(i);
k=0;
for(i=1;i<=m;i++)
{
if(arr[i].se-arr[i].fi-1<=n-2-(arr[i].se-arr[i].fi-1))
{
nodes[k].pb(arr[i].fi);
set<int>::iterator it=s.upper_bound(arr[i].fi);
while((*it)!=arr[i].se)
{
nodes[k].pb(*it);
it++;
}
nodes[k].pb(arr[i].se);
for(j=1;j<nodes[k].size()-1;j++)
s.erase(nodes[k][j]);
}
else
{
while(*s.begin()!=arr[i].fi)
{
nodes[k].pb(*s.begin());
s.erase(s.begin());
}
nodes[k].pb(arr[i].fi);
nodes[k].pb(arr[i].se);
int l=nodes[k].size();
set<int>::iterator it=s.upper_bound(arr[i].se);
while(it!=s.end())
{
nodes[k].pb(*it);
it++;
}
for(;l<nodes[k].size();l++)
s.erase(nodes[k][l]);
}
reverse(nodes[k].begin(), nodes[k].end());
k++;
}
while(s.size()!=0)
{
nodes[k].pb(*s.begin());
s.erase(s.begin());
}
reverse(nodes[k].begin(), nodes[k].end());
k++;
sort(nodes,nodes+k);
map<pi,int>m1;
for(i=0;i<k;i++)
{
for(j=0;j<nodes[i].size()-1;j++)
{
if(nodes[i][j]==nodes[i][j+1]+1)
continue;
else if(m1.find(mp(nodes[i][j],nodes[i][j+1]))!=m1.end())
{
v[m1[mp(nodes[i][j],nodes[i][j+1])]].pb(i+1);
v[i+1].pb(m1[mp(nodes[i][j],nodes[i][j+1])]);
m1.erase(mp(nodes[i][j],nodes[i][j+1]));
}
else
{
m1[mp(nodes[i][j],nodes[i][j+1])]=i+1;
}
}
j=nodes[i].size()-1;
if(nodes[i][0]!=n||nodes[i][j]!=1)
{
if(m1.find(mp(nodes[i][0],nodes[i][j]))!=m1.end())
{
v[m1[mp(nodes[i][0],nodes[i][j])]].pb(i+1);
v[i+1].pb(m1[mp(nodes[i][0],nodes[i][j])]);
m1.erase(mp(nodes[i][0],nodes[i][j]));
}
else
{
m1[mp(nodes[i][0],nodes[i][j])]=i+1;
}
}
}
for(i=1;i<=n;i++)
level[i]=1e6;
int cen=decompose(1);
//printf("%d\n",cen );
queue<int>q;
i=0;
q.push(cen);
while(!q.empty())
{
j=q.size();
while(j--)
{
int z=q.front();
q.pop();
level[z]=i;
for(int l=0;l<v2[z].size();l++)
{
if(level[v2[z][l]]==1e6)
{
q.push(v2[z][l]);
}
}
}
i++;
}
for(i=1;i<=k;i++){
//printf("%d %d\n",v2[i].size(),level[i] );
printf("%d",level[i]+1 );
if(i!=k)
printf(" ");
}
printf("\n");
return 0;
}
Tutorial is loading...
Code
#include<bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%lld",&x)
#define slld(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)
#define ll long long
#define mod 65536
#define bitcount __builtin_popcountll
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define pi pair<int,int>
ll dp[17][65538][17];
char a[20];
ll b[20];
ll mo[1100005];
ll f(ll m,ll p,ll pos)
{
if(dp[m][p][pos]!=-1)
return dp[m][p][pos];
if(pos==0)
{
if(((1<<m)&p))
dp[m][p][pos]=1;
else
dp[m][p][pos]=0;
return dp[m][p][pos];
}
ll j=0;
for(ll i=0;i<=15;i++)
{
j+=f(max(m,i),mo[p*16+i],pos-1);
}
return dp[m][p][pos]=j;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ll t,n,i,j,k,l,r,m,p,ans1;
mo[0]=0;
for(i=1;i<=1100000;i++)
{
mo[i]=mo[i-1]+1;
if(mo[i]==mod)
mo[i]=0;
}
memset(dp,-1,sizeof dp);
f(0,0,16);
sd(t);
while(t--)
{
ss(a);
n=strlen(a);
l=0;
for(i=0;i<n;i++)
{
l=l*16;
if(a[i]>='0'&&a[i]<='9')
l+=a[i]-'0';
else
l+=a[i]-'a'+10;
}
ans1=0;
if(l>0)
{
l--;
j=l;
for(i=0;i<n;i++)
{
b[i]=j%16;
j/=16;
}
m=p=0;
for(j=n-1;j>=0;j--)
{
for(k=0;k<b[j];k++)
ans1-=dp[max(m,k)][mo[p*16+k]][j];
m=max(m,b[j]);
p=mo[p*16+b[j]];
}
ans1-=dp[m][p][0];
}
ss(a);
n=strlen(a);
r=0;
for(i=0;i<n;i++)
{
r=r*16;
if(a[i]>='0'&&a[i]<='9')
r+=a[i]-'0';
else
r+=a[i]-'a'+10;
}
j=r;
for(i=0;i<n;i++)
{
b[i]=j%16;
j/=16;
}
m=p=0;
for(j=n-1;j>=0;j--)
{
for(k=0;k<b[j];k++)
ans1+=dp[max(m,k)][mo[p*16+k]][j];
m=max(m,b[j]);
p=mo[p*16+b[j]];
}
ans1+=dp[m][p][0];
printf("%lld\n",ans1);
}
return 0;
}
