oj.uz

Submission #734690

# Submission time Handle Problem Language Result Execution time Memory
734690 2023-05-02T20:57:09 Z grossly_overconfident Festivals in JOI Kingdom 2 (JOI23_festival2) C++17
10 / 100
 9000 ms 320 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1740 ms 300 KB Output is correct
9 Correct 1749 ms 292 KB Output is correct
10 Correct 1693 ms 212 KB Output is correct
11 Correct 8 ms 320 KB Output is correct
12 Correct 115 ms 304 KB Output is correct
13 Correct 116 ms 212 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1740 ms 300 KB Output is correct
9 Correct 1749 ms 292 KB Output is correct
10 Correct 1693 ms 212 KB Output is correct
11 Correct 8 ms 320 KB Output is correct
12 Correct 115 ms 304 KB Output is correct
13 Correct 116 ms 212 KB Output is correct
14 Execution timed out 9003 ms 212 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1740 ms 300 KB Output is correct
9 Correct 1749 ms 292 KB Output is correct
10 Correct 1693 ms 212 KB Output is correct
11 Correct 8 ms 320 KB Output is correct
12 Correct 115 ms 304 KB Output is correct
13 Correct 116 ms 212 KB Output is correct
14 Execution timed out 9003 ms 212 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1740 ms 300 KB Output is correct
9 Correct 1749 ms 292 KB Output is correct
10 Correct 1693 ms 212 KB Output is correct
11 Correct 8 ms 320 KB Output is correct
12 Correct 115 ms 304 KB Output is correct
13 Correct 116 ms 212 KB Output is correct
14 Execution timed out 9003 ms 212 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1740 ms 300 KB Output is correct
9 Correct 1749 ms 292 KB Output is correct
10 Correct 1693 ms 212 KB Output is correct
11 Correct 8 ms 320 KB Output is correct
12 Correct 115 ms 304 KB Output is correct
13 Correct 116 ms 212 KB Output is correct
14 Execution timed out 9003 ms 212 KB Time limit exceeded
15 Halted 0 ms 0 KB -