| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1200181 | prince | September (APIO24_september) | C++17 | 0 ms | 0 KiB |
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;
}