Submission #730965

#	Time	Username	Problem	Language	Result	Execution time	Memory
730965		grogu	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++14	10 / 100	628 ms	448 KiB

festival2

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
using namespace std;

#define maxn 20
ll mod;
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
ll po(ll x,ll y){
    if(y==0) return 1LL;
    ll ans = po(x,y/2);
    ans = mul(ans,ans);
    if(y&1) ans = mul(ans,x);
    return ans;
}
ll inv(ll x){return po(x,mod-2);}
ll n;
vector<pll> v;
vector<pll> e;
bool vis[maxn];
ll st[maxn];
ll dp[maxn];
ll reshi(ll m){
    if(m==n+1){
        sort(all(v));
        for(pll p : v){
            if(e.empty()||p.fi>e.back().sc) e.pb(p);
        }
        ll ans1 = e.size();
        e.clear();
        for(ll i = 1;i<=2*n;i++) st[i] = 0;
        for(pll p : v) st[p.sc] = p.fi;
        dp[0] = 0;
        for(ll i = 1;i<=2*n;i++){
            dp[i] = dp[i-1];
            if(!st[i]) continue;
            dp[i] = max(dp[i],dp[st[i]-1] + 1);
        }
        return dp[2*n]>ans1;
    }
    vector<ll> w;
    for(ll i = 1;i<=2*n;i++) if(!vis[i]) w.pb(i);
    ll ans = 0;
    ll x = w[0];
    for(ll j = 1;j<w.size();j++){
        ll y = w[j];
        v.pb({x,y});
        vis[x] = vis[y] = 1;
        ans = add(ans,reshi(m+1));
        vis[x] = vis[y] = 0;
        v.popb();
    }
    return ans;
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> mod;
    cout<<reshi(1)<<endl;
}
/**
3 1000000007

4 100000007
**/

Compilation message (stderr)

festival2.cpp: In function 'long long int reshi(long long int)':
festival2.cpp:73:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(ll j = 1;j<w.size();j++){
      |                  ~^~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 27
• Subtask 4: 0 / 14
• Subtask 5: 0 / 36
• Subtask 6: 0 / 13