Submission #1200183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200183		prince	September (APIO24_september)	C++17	0 / 100	1 ms	392 KiB

september

#include "bits/stdc++.h"
#include "september.h"
using namespace std;

int solve(int n, int m, vector<int> a, vector<vector<int>> vol) {
    int L = n - 1;
    // Build position table: pos[j][x] = index of x in volunteer j's sequence
    vector<vector<int>> pos(m, vector<int>(n));
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < L; i++) {
            pos[j][ vol[j][i] ] = i;
        }
    }

    // Reference sequence from volunteer 0
    const vector<int>& s0 = vol[0];

    // For each position i in s0, compute the max and min positions across all volunteers
    vector<int> mx(L), mn(L);
    for (int i = 0; i < L; i++) {
        int x = s0[i];
        int p_max = pos[0][x], p_min = pos[0][x];
        for (int j = 1; j < m; j++) {
            p_max = max(p_max, pos[j][x]);
            p_min = min(p_min, pos[j][x]);
        }
        mx[i] = p_max;
        mn[i] = p_min;
    }

    // Build prefix max of mx and suffix min of mn
    vector<int> pref_max(L), suf_min(L);
    pref_max[0] = mx[0];
    for (int i = 1; i < L; i++) {
        pref_max[i] = max(pref_max[i-1], mx[i]);
    }
    suf_min[L-1] = mn[L-1];
    for (int i = L-2; i >= 0; i--) {
        suf_min[i] = min(suf_min[i+1], mn[i]);
    }

    // Count valid day boundaries
    int boundaries = 0;
    for (int i = 0; i + 1 < L; i++) {
        if (pref_max[i] < suf_min[i+1]) {
            boundaries++;
        }
    }

    // Number of days is boundaries + 1
    return boundaries + 1;
}

• 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