Submission #782947

#	Time	Username	Problem	Language	Result	Execution time	Memory
782947		kebine	The Xana coup (BOI21_xanadu)	C++17	0 / 100	1 ms	468 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll a[2005],b[2005];
ll pref[2005],suff[2005];
ll mod=1e9+7;
ll jawab;
vector <ll> ans;
void solve (ll indeks, ll previous){
    // cout<<indeks<<" "<<previous<<endl;
    if (indeks>=m){
        ans.push_back(n);
        // for (auto z:ans) cout<<z<<" ";
        // cout<<endl;
        for (int i=1;i<ans.size();i++){
            ll maks=0;
            for (int j=ans[i-1]+1;j<=ans[i];j++){
                maks=max(maks,a[j]);
                // cout<<i<<" "<<maks<<"::";
            }
            // cout<<endl<<endl;
            if (maks!=b[i]){
                ans.pop_back();
                return;
            }
        }
        // for (auto z:ans) cout<<z<<" ";
        // cout<<endl;
        jawab++;
        ans.pop_back();
        return;
    }
    for (int i=previous+1;i<=n-(m-indeks);i++){
        ans.push_back(i);
        solve(indeks+1,i);
        ans.pop_back();
    }
}
ll fact (ll n){
    if (n==0) return 1;
    return n%mod*fact(n-1)%mod;
}
ll kali (ll a, ll b){
    return (a*b)%mod;
}
ll simpan=1;
void fexpo(ll a, ll b){
    // cout<<a<<" "<<b<<endl;
    if (b==1) {
        simpan=kali(simpan,a);
        return;
    }
    if (b%2==0){
        fexpo(kali(a,a),b/2);
    }
    else{
        simpan=kali(simpan,a);
        fexpo(kali(a,a),(b-1)/2);
    }
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        cin>>a[i];
        pref[i]=max(pref[i-1],a[i]);
        // cout<<pref[i]<<endl;
    }
    for (int i=1;i<=n;i++){
        suff[i]=max(suff[i-1],a[n-i+1]);
    }
    // for (int i=1;i<=n;i++) cout<<pref[i]<<" "<<suff[i]<<":::"<<i<<endl;
    for (int i=1;i<=m;i++){
        cin>>b[i];
    }
    if (m==2){
        ll ans=0;
        for(int i=1;i<n;i++){
            // cout<<pref[i]<<" "<<b[1]<<suff[n-i+1]<<" "<<b[2]<<endl;
            if (pref[i]==b[1]&&suff[n-i]==b[2]) ans++;
        }
        cout<<ans%mod;
    }
    else if (n<=20&&m<=20){
        // cout<<fact(n-1)<<" "<<fexpo(fact(m-1),2*fact(m)+1)<<" "<<fexpo(fact(n-m-2),2*fact(n-m-2)+1)<<endl;
        ans.push_back(0);
        solve(1,0);
        cout<<jawab;
    }
    else{
        if (n<m) {
            cout<<0;
            return 0;
        }
        ll tes=1;
        ll u=m-1;
        // fexpo(fact(u)%mod,mod-2);
        // tes*=simpan%mod;
        // simpan=1;
        // fexpo(fact(n-m-2)%mod,mod-2);
        // tes*=simpan%mod*fact(n-1)%mod;
        // tes%=mod;
        // cout<<tes;
    }
    // else{
    //     if (m>n) cout<<0;

    // }
}

Compilation message (stderr)

xanadu.cpp: In function 'void solve(ll, ll)':
xanadu.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for (int i=1;i<ans.size();i++){
      |                      ~^~~~~~~~~~~
xanadu.cpp: In function 'int main()':
xanadu.cpp:96:12: warning: unused variable 'tes' [-Wunused-variable]
   96 |         ll tes=1;
      |            ^~~
xanadu.cpp:97:12: warning: unused variable 'u' [-Wunused-variable]
   97 |         ll u=m-1;
      |            ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40
• Subtask 5: 0 / 30