C - Infinite Replacement
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define int long long
const int N = 200010,mod = 1e18;
int qmi(int a,int b){int res=1;a=a%mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res%mod;}
void solve()
{
string s,t;
cin>>s>>t;
if(t=="a"){cout<<1<<'\n';return ;}
int cnt=0;
for(int i=0;i<t.size();i++)cnt+=t[i]=='a';
if(cnt>0){cout<<-1<<'\n';return ;}
cout<<qmi(2,(int)s.size())<<'\n';
}
signed main()
{
int T;cin>>T;
while(T--)solve();
}
D. A-B-C Sort
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 200010;
int a[N],b[N];
void solve()
{
int n;cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
for(int i=n-1,l=0,r=n-1;i>=0;i-=2)
{
b[l++]=a[i];
if(i>=1)b[r--]=a[i-1];
}
vector<int>vec;
for(int i=n-1,j=0;j<=i;i--,j++)
{
if(i==j)vec.push_back(b[i]);
else
{
if(b[i]>b[j])swap(b[i],b[j]);
vec.push_back(b[j]);
vec.push_back(b[i]);
}
}
int minv=1e9;
for(auto x :vec)
{
if(x<=minv)minv=x;
else
{
cout<<"NO"<<'\n';
return ;
}
}
cout<<"YES"<<'\n';
}
signed main()
{
int T;cin>>T;
while(T--)solve();
}
E. Breaking the Wall
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 200010;
int a[N];
void solve()
{
int n;cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
int minv=1e9;
for(int i=1;i<n;i++)
{
int w=a[i-1],v=a[i];
if(w>v)swap(w,v);
if(v>=2*w)minv=min(minv,(v+1)/2);
else minv=min(minv,(v+w+2)/3);
}
for(int i=1;i<n-1;i++)
{
int w=a[i-1],v=a[i+1];
if((w&1)&&(v&1))minv=min(minv,(w+v)/2);
}
sort(a,a+n);
minv=min(minv,(a[0]+1)/2+(a[1]+1)/2);
cout<<minv<<'\n';
}
signed main()
{
int T;T=1;
while(T--)solve();
}
F. Desktop Rearrangement
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1010;
char g[N][N];
int col[N];
signed main()
{
int n,m,q,sum=0;
cin>>n>>m>>q;
for(int i=0;i<n;i++)scanf("%s",g[i]);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
col[j]+=g[i][j]=='*',sum+=g[i][j]=='*';
while(q--)
{
int x,y;
cin>>x>>y;
x--,y--;
if(g[x][y]=='*')col[y]--,sum--,g[x][y]='.';
else col[y]++,sum++,g[x][y]='*';
int c=sum/n,r=sum%n;
int t=0;
for(int i=0;i<c;i++)t+=col[i];
for(int i=0;i<r;i++)t+=g[i][c]=='*';
cout<<sum-t<<'\n';
}
}
G. Remove Directed Edges
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
const int N = 200010;
int f[N],din[N],dout[N];
vector<int>g[N];
signed main()
{
int n,m;
cin>>n>>m;
for(int i=1,x,y;i<=m;i++)
{
cin>>x>>y;
g[x].push_back(y);
din[y]++;
dout[x]++;
}
int res=0;
function<void(int)> dfs = [&](int u)
{
if(f[u])return ;
f[u]=1;
if(dout[u]<=1)return ;
for(auto v : g[u])
{
dfs(v);
if(din[v]>=2)f[u]=max(f[u],f[v]+1);
}
};
for(int i=1;i<=n;i++)dfs(i);
for(int i=1;i<=n;i++)res=max(res,f[i]);
cout<<res<<'\n';
}
|
