Submission #701354

#	Time	Username	Problem	Language	Result	Execution time	Memory
701354		thomasqm	Matching (CEOI11_mat)	C++17	92 / 100	1447 ms	63676 KiB

mat

#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <numeric>
#include <list>
#include <array>
#include <set>
#include <map>
#include <chrono>
#include <stack>
#include <random>
#include <climits>
#include <algorithm>
#include <tgmath.h>

using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

int main() {
	unsigned n,m; cin>>n>>m;
	vector<unsigned> arr(n+m);
	for (unsigned i=0; i<n+m; i++) {
		unsigned x; cin>>x;
		if (i<n) arr[x-1]=i+1e9+1;
		else arr[i]=x;
	}

	vector<unsigned> z(m+n);
	z[0]=m+n;
	unsigned l=1, r=1;

	vector<unsigned> sorted_arr(n+m);
	for (unsigned i=0; i<n+m; i++) sorted_arr[i]=i;
	std::sort(sorted_arr.begin(), sorted_arr.end(), [&](unsigned a, unsigned b) {return arr[a]<arr[b];});

	vector<unsigned> sorted_arr_inv(n+m);
	for (unsigned i=0; i<n+m; i++) sorted_arr_inv[sorted_arr[i]]=i;

	auto get = [](vector<unsigned>& tr, unsigned i) {
		uint64_t out=0;
		while (i!=-1u) {
			out += tr[i];
			i=((i&(i+1)) - 1);
		}

		return out;
	};

	auto up = [&](vector<unsigned>& tr, unsigned i, int add) {
		for (unsigned j=i; (j&(j+1))<=i && j<n+m; j=j|(j+1)) tr[j]+=add;
	};

	vector<unsigned> sorted(n+m, 0), sorted_pre(n+m, 0);

	auto shift = [&]() {
		up(sorted, sorted_arr_inv[l], -1);
		up(sorted_pre, sorted_arr_inv[r-l-1], -1);
		l++;
	};

	auto extend = [&]() {
		if (r==m+n) return false;

		unsigned x = get(sorted, sorted_arr_inv[r]), y=get(sorted_pre, sorted_arr_inv[r-l]);
		if (x!=y) return false;

		up(sorted, sorted_arr_inv[r], 1);
		up(sorted_pre, sorted_arr_inv[r-l], 1);

		r++;
		return true;
	};

	for (unsigned i=1; i<m+n; i++) {
		if (i>=r || z[i-l]+1>=r-i) {
			while (l<i) shift();
			while (extend());
			z[i]=r-l;
		} else {
			z[i]=z[i-l];
		}
	}

	vector<unsigned> out;
	for (unsigned i=n; i<m+n; i++) {
		if (z[i]>=n) out.push_back(i-n+1);
	}

	cout<<out.size()<<"\n";
	for (unsigned i=0; i<out.size(); i++) cout<<out[i]<<(i<out.size()-1 ? " " : "");
	cout<<"\n";
}

Compilation message (stderr)

mat.cpp:20: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   20 | #pragma GCC optimization ("O3")
      | 
mat.cpp:21: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   21 | #pragma GCC optimization ("unroll-loops")
      |

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