Submission #722102

#	Time	Username	Problem	Language	Result	Execution time	Memory
722102		600Mihnea	Matching (CEOI11_mat)	C++17	18 / 100	2065 ms	25916 KiB

mat

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <cassert>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <stack>
#include <chrono>
#include <cstring>
#include <numeric>
using namespace std;
void print(vector<int> v) {
	cout << " ---> ";
	for (auto& x : v) {
		cout << x << " ";
	}
	cout << "\n";
}
signed main() {

#ifdef ONPC	
	FILE* stream;
	freopen_s(&stream, "input.txt", "r", stdin);
#else
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#endif
	int n, m;
	cin >> n >> m;
	vector<int> pattern(n), txt(m);
	for (int i = 0; i < n; i++) {
		int foo;
		cin >> foo;
		foo--;
		assert(0 <= foo && foo < n);
		pattern[foo] = i;
	}
	for (int i = 0; i < m; i++) {
		cin >> txt[i];
	}
	vector<int> sols;
	for (int i = 0; i + n - 1 < m; i++) {
		vector<int> vec(txt.begin() + i, txt.begin() + i + n);
		// normalize "vec"
		map<int, int> T;
		for (auto& x : vec) {
			T[x] = 0;
		}
		int y = 0;
		for (auto& it : T) {
			it.second = y++;
		}
		for (auto& x : vec) {
			x = T[x];
		}
		if (vec == pattern) {
			sols.push_back(i);
		}
	}
	cout << (int)sols.size() << "\n";
	for (auto& i : sols) {
		cout << i + 1 << " ";
	}
	cout << "\n";
	return 0;
}

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