Submission #1214842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214842		biank	Binaria (CCO23_day1problem1)	C++20	25 / 25	57 ms	12104 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;

struct DSU{
    vi p;
    DSU(int n):p(n,-1){}
    int find(int x){
        if(p[x]<0) return x;
        return p[x]=find(p[x]);
    }
    bool unite(int x, int y){
        x=find(x),y=find(y);
        if(x==y) return false;
        if(p[x]>p[y]) swap(x,y);
        p[x]+=p[y],p[y]=x;
        return true;
    }
};

const int MOD=1e6+3;

int mul(int a, int b){
    return int(1LL*a*b%MOD);
}

int binpow(int a, int k){
    int r=1;
    while(k){
        if(k&1) r=mul(r,a);
        a=mul(a,a),k/=2;
    }
    return r;
}

int choose(int n, int k){
    if(k<0||n<0||n-k<0) return 0;
    int ans=1,ans2=1;
    forn(i,k){
        ans=mul(ans,n-i);
        ans2=mul(ans2,i+1);
    }
    return mul(ans,binpow(ans2,MOD-2));
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n,k;
    cin>>n>>k;
    vi s(n-k+1);
    forn(i,n-k+1) cin>>s[i];
    vi x(n,-1);
    DSU dsu(n);
    forn(i,n-k){
        int diff=s[i]-s[i+1];
        if(diff==1) x[i]=1,x[i+k]=0;
        else if(diff==-1) x[i]=0,x[i+k]=1;
        else if(diff==0) dsu.unite(i,i+k);
        else assert(false);
    }
    forn(i,n){
        int p=dsu.find(i);
        if(x[p]==-1) x[p]=x[i];
    }
    forn(i,n){
        int p=dsu.find(i);
        if(x[i]==-1) x[i]=x[p];
    }
    int a=0,b=s[0];
    forn(i,k){
        if(x[i]==-1) a++;
        else if(x[i]==1) b--;
    }
    cout<<choose(a,b)<<'\n';
    
    return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 7 / 7