제출 #1222179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222179		Aviansh	Festivals in JOI Kingdom 2 (JOI23_festival2)	C++20	10 / 100	1911 ms	1114112 KiB

festival2

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>>pos;

void rec(int prev, int n, vector<int>&curr){
    if(curr.size()==n){
        vector<int>cp;
        for(int i : curr)
            cp.push_back(i);
        pos.push_back(cp);
        return;
    }
    for(int i = prev+1;i<=2*n;i++){
        curr.push_back(i);
        rec(i,n,curr);
        curr.pop_back();
    }
}

bool check(vector<int>a, vector<int>b){
    int ans1 = 0;
    int temp = 0;
    vector<array<int,2>>v;
    for(int i = 0;i<a.size();i++) {
        if(a[i]>temp){
            temp=b[i];
            ans1++;
        }
        v.push_back({b[i],a[i]});
    }
    sort(v.begin(),v.end());
    int ans2 = 0;
    temp = 0;
    for(int i = 0;i<a.size();i++){
        if(v[i][1]>temp){
            ans2++;
            temp=v[i][0];
        }
    }
    return (ans1!=ans2);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,p;
    cin >> n >> p;
    vector<int>v={1};
    rec(1,n,v);
    bool used[2*n+1];
    int ans = 0;
    int fac = 1;
    for(int i = 1;i<=n;i++){
        fac*=i;
    }
    for(vector<int>a:pos){
        //a is fixed now.
        fill(used,used+2*n+1,0);
        for(int i : a){
            used[i]=1;
        }
        vector<int>b;
        for(int i = 1;i<=2*n;i++){
            if(used[i])
                continue;
            b.push_back(i);
        }
        for(int i = 0;i<=fac;i++){
            bool wor = 1;
            for(int i = 0;i<n;i++){
                if(a[i]>b[i]){
                    wor=0;
                    break;
                }
            }
            if(wor){
                ans+=check(a,b);
                ans%=p;
            }
            next_permutation(b.begin(),b.end());
        }
    }
    cout << ans << "\n";
    return 0;
}

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