oj.uz

답안 #701354

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
701354 2023-02-21T03:51:53 Z thomasqm Matching (CEOI11_mat) C++17
92 / 100
 1447 ms 63676 KB 
#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

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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 304 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 952 KB Output is correct
2 Correct 14 ms 948 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 952 KB Output is correct
2 Correct 11 ms 908 KB Output is correct
3 Correct 2 ms 340 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 6940 KB Output is correct
2 Correct 104 ms 6216 KB Output is correct
3 Correct 157 ms 8312 KB Output is correct
4 Correct 144 ms 8304 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 8136 KB Output is correct
2 Correct 127 ms 6984 KB Output is correct
3 Correct 118 ms 7612 KB Output is correct
4 Correct 143 ms 8380 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 129 ms 8104 KB Output is correct
2 Correct 113 ms 7492 KB Output is correct
3 Correct 120 ms 7448 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 733 ms 39928 KB Output is correct
2 Correct 1447 ms 63676 KB Output is correct
3 Correct 483 ms 26960 KB Output is correct

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 760 ms 40036 KB Output is correct
2 Incorrect 567 ms 30524 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 588 ms 33960 KB Output is correct
2 Correct 742 ms 41376 KB Output is correct
3 Correct 663 ms 34876 KB Output is correct
4 Correct 1055 ms 61644 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 577 ms 35432 KB Output is correct
2 Correct 728 ms 35564 KB Output is correct
3 Correct 288 ms 18572 KB Output is correct
4 Correct 1149 ms 59952 KB Output is correct