Codeforces 744 div3 solutions

744_3.cpp

void solveA(){
	string s; cin>>s;
	int a[3] = {};
	f(i,0,sz(s)){
		if(s[i]=='A') a[0]++;
		else if(s[i]=='B') a[1]++;
		else a[2]++;
	}
	bool ok = a[1] == (a[0]+a[2]);
	if(ok) cout<<"YES\n"; else cout<<"NO\n"; 
}

int mod=1e9+7;
const int mxn=101000;
bool use[mxn];
int a[mxn],b[mxn];
 
void solveB(){
    int n; cin>>n;
    f(i,0,n) cin>>a[i]; f(i,0,n) b[i] = a[i];
    vector<array<int,3>> ans;
    f(i,0,n) use[i]=0;
    sort(b,b+n);
    f(i,0,n){
        if(a[i]==b[i]) continue;
        int idx = -1;
        f(j,i+1,n) {
            if(a[j]==b[i]) {
                idx = j;
                break;
            }
        }
        assert(idx!=-1);
        ans.pb({i+1,idx+1,idx-i});
        for(int j=idx;j>i;--j) a[j] = a[j-1];
        a[i] = b[i];
    }
    cout<<sz(ans)<<"\n";
    for(auto it : ans) cout<<it[0]<<" "<<it[1]<<" "<<it[2]<<"\n";
}


string s[40];
bool vis[40][40];
int n,m,k; 
 
int ck(int x,int y){
    for(int i=0;;++i){
        if((x-i)>=0 && (y-i)>=0 && (y+i)<m && s[x-i][y-i]=='*' && s[x-i][y+i]=='*') continue;
        return i-1;
    }
}
 
void solveC(){
    cin>>n>>m>>k;
    f(i,0,n) cin>>s[i];
    f(i,0,n) f(j,0,m) vis[i][j]=0;
    for(int i=n-1;i>=0;--i) for(int j=m-1;j>=0;--j) {
        int here = ck(i,j);
        if(here>=k)
            f(h,0,here+1)
                vis[i-h][j-h] = vis[i-h][j+h] = 1;
    }
    f(i,0,n) f(j,0,m) if(s[i][j]=='*' && !vis[i][j]) {
        cout<<"NO\n";
        return ;
    }
    cout<<"YES\n";
}


void solveD(){
    int n,x; cin>>n;
    set<pii> st; f(i,0,n){
        cin>>x; if(x!=0)
        st.insert({x,i});
    } 
    vpii ans;
    while(1){
        if(sz(st)==0) break;
        auto it = *st.begin();
        st.erase(it);
        if(sz(st)==0) break;
        auto ip = *st.rbegin();
        st.erase(ip);
        ans.pb({it.ss+1,ip.ss+1});
        pii here = {it.ff-1,it.ss};
        if(here.ff!=0) st.insert(here);
        here = {ip.ff-1,ip.ss};
        if(here.ff!=0) st.insert(here);
    }
    cout<<sz(ans)<<"\n";
    for(auto it : ans) cout<<it.ff <<" "<<it.ss<<"\n";
}

int here[mxn];
 
void solveE1(){
    int n; cin>>n;
    int a[n]; f(i,0,n) cin>>a[i];
    if(n==1) {
        cout<<a[0]<<"\n";
        return ;
    }
    int l = 250000, r=250001;
    here[l--] = a[0];
    if(a[1]<a[0])
        here[l--] = a[1];
    else here[r++] = a[1];
    f(i,2,n) if(a[i]<here[l+1]) here[l--] = a[i]; else here[r++] = a[i];
    f(i,l+1,r) cout<<here[i]<<" "; cout<<"\n";
}


int x;
vi vt;
 
void st(int curr,int l,int r,int id,int val){
    if(l==r){
        if(l==id) vt[curr]+=val;
        return ;
    }
    if(r<id || id<l) return ;
    int mid=l+r; mid/=2;
    st(2*curr+1,l,mid,id,val);
    st(2*curr+2,mid+1,r,id,val);
    vt[curr]=vt[2*curr+1]+vt[2*curr+2];
}
 
int gt(int curr,int l,int r,int L,int R){
    if(l==r){
        if(l>=L && l<=R) return vt[curr];
        return 0;
    }
    if(R<l || r<L) return 0;
    if(l>=L && r<=R) return vt[curr];
    int mid=l+r; mid/=2;
    return gt(2*curr+1,l,mid,L,R) + gt(2*curr+2,mid+1,r,L,R);
}
 
void solve()E2{
    // the number of inversions when a[i] was added from left or right is independent of how a[i-1] was added.
    // so better take the minimum at every stage.
    int n; cin>>n; 
    vi a(n); f(i,0,n) cin>>a[i];
    vi b(n); f(i,0,n) b[i] = a[i];
    sort(all(b)); b.erase(unique(all(b)),b.end());
    int tt = sz(b),ans = 0;
    f(i,0,n) a[i] = lb(all(b),a[i]) - b.begin();
    f(i,0,n) {
        int l = a[i]==0 ? 0 : gt(0,0,x-1,0,a[i]-1);
        int r = gt(0,0,x-1,a[i]+1,tt);
        ans += min(l,r);
        st(0,0,x-1,a[i],1);
    }
    cout<<ans<<"\n";
    f(i,0,n) st(0,0,x-1,a[i],-1);
}


// the key idea is that there will be a cycle in the array, one of them must be zero, or put another way, 
// there is a consectutive number of ones in it say loop, that must be set to zero, the maximum such number will be the ans for cycle.
// but we do not know what has to be the starting point of such loop, so we have a cycle of double length. the max ans if possible can 
// be len(cycle) -1. if it exceeds then no solution is possible.
    
void solveF(){
    int n,d; cin>>n>>d;
    vector<bool> use(n); vi a(n);
    f(i,0,n) cin>>a[i];
    int ans = 0; bool ok = 1;
    f(i,0,n) if(!use[i]) {
        vi here; int curr = i;
        while(!use[curr]){
            use[curr]=1;
            here.pb(a[curr]);
            curr+=d; curr%=n;
        }
        int tt=0,now=0;
        f(j,0,2*sz(here)){
            if(here[j%sz(here)]==1) ++now;
            else now=0;
            tt = max(tt,now);
        }
        if(tt>=sz(here)) {
            ok = 0;
            break;
        }
        ans = max(ans,tt);
    }
    if(ok) cout<<ans<<"\n";
    else cout<<"-1\n";
}

int n; 
vi a;
int dp[mxn],np[mxn];
 
bool poss(int x){
    f(i,0,x+1) dp[i]=1;  // x length has x+1 points, start from anywhere
    f(i,0,n){
        f(j,0,x+1) np[j]=0;
        f(j,0,x+1) if(dp[j]) {
            if(j>=a[i]) np[j-a[i]]=1;
            if((j+a[i])<=x) np[j+a[i]]=1;
        }
        f(j,0,x+1) dp[j]=np[j];
    }
    f(i,0,x+1) if(dp[i]) return 1; // if possible to end in interval without getting outside
    return 0; // else no.
}
 
void solveG(){
    cin>>n; a.resize(n); f(i,0,n) cin>>a[i];
    int l=0,h=2000,ans = -1;
    // see if you can complete it in x length
    while(l<=h){
        int mid = l+h; mid/=2;
        if(poss(mid)) {ans = mid; h = mid-1;}
        else l = mid+1;
    }
    cout<<ans<<"\n";
}