Submission #734690

#	Time	Username	Problem	Language	Result	Execution time	Memory
734690		grossly_overconfident	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++17	10 / 100	9003 ms	320 KiB

festival2

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
int answer = 0;
int n, p;

int findfront(vector<bool> v, int s){
    for (int i = s + 1; i < v.size(); ++i){
        if (!v[i]){
            return i;
        }
    }
    return -1;
}

int bsearch(vector<int>& a, int i){
    int lo = 0, hi = a.size() - 1;
    while(lo != hi){
        int mid = (lo + hi) / 2;
        if (a[mid] >= i){
            hi = mid;
        }
        else{
            lo = mid + 1;
        }
    }
    if (a[lo] == i){
        return lo;
    }
    return -1;
}

int greedysol(vector<int>& a, vector<int>& b, int i){
    if (i == b.size() * 2){
        return 0;
    }
    int j = bsearch(a, i);
    if (j == -1){
        return greedysol(a, b, i + 1);
    }
    return greedysol(a, b, b[j]) + 1;
}

int dpsol(vector<int>& a, vector<int>& b, int i, vector<int>& dp){
    if (i == b.size() * 2){
        return 0;
    }
    if (dp[i] != -1){
        return dp[i];
    }
    int j = bsearch(a, i);
    if (j == -1){
        return dp[i] = dpsol(a, b, i + 1, dp);
    }
    return dp[i] = max(dpsol(a, b, b[j], dp) + 1, dpsol(a, b, i + 1, dp));
}

void create(vector<int> a, vector<int> b, vector<bool> visited, int t, int f){
    
    if (t == n){
        vector<int> dp(n * 2, -1);
        if (dpsol(a, b, 0, dp) != greedysol(a, b, 0)){
            answer++;
            answer %= p;
        }
        return;
    }
    a[t] = f;
    visited[f] = true;
    for (int i = f + 1; i < n * 2; ++i){
        if (!visited[i]){
            b[t] = i;
            visited[i] = true;
            create(a, b, visited, t + 1, findfront(visited, f));
            visited[i] = false;
        }
    }




}

signed main(){
    
    cin.tie(0);
    iostream::sync_with_stdio(0);

    cin >> n >> p;
    vector<int> a(n), b(n);
    vector<bool> v(2 * n, false);
    create(a, b, v, 0, 0);
    cout << answer;


    return 0;
}

Compilation message (stderr)

festival2.cpp: In function 'int findfront(std::vector<bool>, int)':
festival2.cpp:9:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for (int i = s + 1; i < v.size(); ++i){
      |                         ~~^~~~~~~~~~
festival2.cpp: In function 'int greedysol(std::vector<int>&, std::vector<int>&, int)':
festival2.cpp:35:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     if (i == b.size() * 2){
      |         ~~^~~~~~~~~~~~~~~
festival2.cpp: In function 'int dpsol(std::vector<int>&, std::vector<int>&, int, std::vector<int>&)':
festival2.cpp:46:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     if (i == b.size() * 2){
      |         ~~^~~~~~~~~~~~~~~

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