Submission #1312246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312246		azamurai	September (APIO24_september)	C++20	45 / 100	165 ms	7488 KiB

september

#include "september.h"

#include <bits/stdc++.h>
#include <vector>

using namespace std;

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	vector <int> p(N + 1, 0);
	vector <int> pos(N, 0);
	for (int i = 0; i < N - 1; i++) {
		pos[S[0][i]] = i;
	}
	vector <pair<int,int>> seg;
	for (int i = 1; i < N; i++) {
		if (F[i] == 0) continue;
		if (pos[F[i]] < pos[i]) {
			seg.push_back(make_pair(pos[F[i]], pos[i]));
		}
	}
	sort(seg.begin(), seg.end());
	for (int i = 0; i < N; i++) {
		p[i] = i;
	}
	int idx = -1;
	for (auto to : seg) {
		int l = to.first, r = to.second;
		if (idx >= l) {
			for (int i = idx + 1; i <= r; i++) p[i] = p[i - 1];
			idx = r;
		}
		else {
			for (int i = l + 1; i <= r; i++) p[i] = p[i - 1];
			idx = r;
		}
	}
	set <int> st;
	for (int i = 0; i < N - 1; i++) {
		st.insert(p[i]);
	}
	return (int)st.size();
}

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