oj.uz

Submission #730965

# Submission time Handle Problem Language Result Execution time Memory
730965 2023-04-26T17:03:01 Z grogu Festivals in JOI Kingdom 2 (JOI23_festival2) C++14
10 / 100
 628 ms 448 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 606 ms 296 KB Output is correct
9 Correct 628 ms 300 KB Output is correct
10 Correct 572 ms 296 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 37 ms 212 KB Output is correct
13 Correct 40 ms 212 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 606 ms 296 KB Output is correct
9 Correct 628 ms 300 KB Output is correct
10 Correct 572 ms 296 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 37 ms 212 KB Output is correct
13 Correct 40 ms 212 KB Output is correct
14 Runtime error 1 ms 448 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 606 ms 296 KB Output is correct
9 Correct 628 ms 300 KB Output is correct
10 Correct 572 ms 296 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 37 ms 212 KB Output is correct
13 Correct 40 ms 212 KB Output is correct
14 Runtime error 1 ms 448 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 606 ms 296 KB Output is correct
9 Correct 628 ms 300 KB Output is correct
10 Correct 572 ms 296 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 37 ms 212 KB Output is correct
13 Correct 40 ms 212 KB Output is correct
14 Runtime error 1 ms 448 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 606 ms 296 KB Output is correct
9 Correct 628 ms 300 KB Output is correct
10 Correct 572 ms 296 KB Output is correct
11 Correct 3 ms 212 KB Output is correct
12 Correct 37 ms 212 KB Output is correct
13 Correct 40 ms 212 KB Output is correct
14 Runtime error 1 ms 448 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -