Submission #1370365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1370365		solution6312	Splits (CEOI25_splits)	C++17	7 / 100	2095 ms	456 KiB

splits

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll=long long;

namespace 
{
    const ll mod=(119<<23)+1;
    bool check(vector<int> x, vector<int> y)
    {
        //for (int i:x) cerr<<i<<' '; cerr<<endl;
        //for (int i:y) cerr<<i<<' '; cerr<<endl;
        int n=x.size();
        vector<int> pos(n);
        for (int i=0; i<n; i++) pos[x[i]]=i+1;
        int cnt=1;
        for (int i=1; i<n; i++)
        {
            //cerr<<i<<": "<<pos[y[i]]<<endl;
            if (pos[y[i]]<pos[y[i-1]]) cnt++;
        }
        //cerr<<cnt<<endl;
        return cnt<=2;
    }
}

int solve(int n, int m, vector<vector<int>> &splits)
{
    vector<int> p(n);
    for (int i=0; i<n; i++) p[i]=i+1;
    int ans=1;
    for (vector<int> i:splits)
    {
        if (!check(p, i))
        {
            ans=0;
            break;
        }
    }
    while (next_permutation(p.begin(), p.end()))
    {
        int add=1;
        for (vector<int> i:splits)
        {
            if (!check(p, i))
            {
                add=0;
                break;
            }
        }
        ans+=add;
    }
    return ans;
}

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 17
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 21