Submission #1173066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173066		ladnooo	September (APIO24_september)	C++20	0 / 100	1096 ms	328 KiB

september

#include <bits/stdc++.h>
using namespace std;


int N, M;
vector<int> F, was;
vector<vector<int>> S;
bool check(int k) {
    for(int i = 0; i < M; i++) {
        vector<int> sigma;
        for(int x : S[i]) {
            sigma.push_back(was[x]);
        }
        vector<int> cmp;
        for(int x : sigma) {
            if (cmp.empty()) cmp.push_back(x);
            else if(cmp.back() != x) cmp.push_back(x);
        }
        int sx = cmp.size();
        if(sx != k) return false;
        for(int j = 0; j < k; j++) {
            if (cmp[j] != j + 1) return false;
        }
    }
    return true;
}
bool idk(int i, int k) {
    if(i == N) {
        vector<int> wass(k + 1);
        for(int j = 1; j < N; j++) {
            wass[was[j]] = 1;
        }
        for(int j = 1; j <= k; j++) {
            if (!wass[j]) return false;
        }
        return check(k);
    }
    int l = 1, r = 0;
    if(F[i] == 0) {
        r = k;
    } else {
        r = was[F[i]] - 1;
    }
    
    for(int j = l; j <= r; j++) {
        was[i] = j;
        if(idk(i + 1, k)) return true;
    } 
    return false;
}
int solvee(int N_, int M_, vector<int>& F_, vector<vector<int>>& S_) {
    N = N_;
    M = M_;
    F = F_;
    S = S_;
    was.resize(N);
    for(int i = 0; i < N; i++) {
        was[i] = 0;
    }
    for(int i = N - 1; i > 0; i--) {
        was[0] = i + 1;
        if(idk(1, i)) return i;
    }
    return 1;
}
int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
    return solvee(N, M, F, S);
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 5
• Subtask 4: 0 / 9
• Subtask 5: 0 / 5
• Subtask 6: 0 / 11
• Subtask 7: 0 / 9
• Subtask 8: 0 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16