oj.uz

답안 #364461

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364461 2021-02-09T08:49:08 Z arnold518 Matching (CEOI11_mat) C++14
100 / 100
 1071 ms 44184 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

int N, M;
int A[MAXN+10], B[MAXN+10], C[MAXN+10];
int fail[MAXN+10];

struct BIT
{
	int tree[MAXN+10];
	void update(int i, int k) { for(; i<=N; i+=(i&-i)) tree[i]+=k; }
	int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
}bit1, bit2;

vector<int> comp;

int main()
{
	scanf("%d%d", &M, &N);
	for(int i=1; i<=M; i++) scanf("%d", &C[i]);
	for(int i=1; i<=M; i++) B[C[i]]=i;
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);

	comp=vector<int>(A+1, A+N+1);
	sort(comp.begin(), comp.end());
	for(int i=1; i<=N; i++) A[i]=lower_bound(comp.begin(), comp.end(), A[i])-comp.begin()+1;
		
	for(int i=2, j=1; i<=M;)
	{
		if(j<=M && bit2.query(B[j])==bit1.query(B[i]))
		{
			fail[i]=j;
			bit1.update(B[i], 1);
			bit2.update(B[j], 1);
			i++; j++;
		}
		else
		{
			if(j!=1)
			{
				for(int k=j-1; k>fail[j-1]; k--)
				{
					bit2.update(B[k], -1);
					bit1.update(B[i-k], -1);
				}
				j=fail[j-1]+1;
			}
			else i++;
		}	
	}

	memset(bit1.tree, 0, sizeof(bit1.tree));
	memset(bit2.tree, 0, sizeof(bit2.tree));
	vector<int> ans;
	for(int i=1, j=1; i<=N;)
	{
		if(j<=M && bit2.query(B[j])==bit1.query(A[i]))
		{
			bit1.update(A[i], 1);
			bit2.update(B[j], 1);
			i++; j++;
			if(j==M+1)
			{
				ans.push_back(i-M);
			}
		}
		else
		{
			if(j!=1)
			{
				for(int k=j-1; k>fail[j-1]; k--)
				{
					bit2.update(B[k], -1);
					bit1.update(A[i-k], -1);
				}
				j=fail[j-1]+1;
			}
			else i++;
		}
	}
	printf("%d\n", ans.size());
	for(auto it : ans) printf("%d ", it);
	printf("\n");
}

Compilation message

mat.cpp: In function 'int main()':
mat.cpp:87:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   87 |  printf("%d\n", ans.size());
      |          ~^     ~~~~~~~~~~
      |           |             |
      |           int           std::vector<int>::size_type {aka long unsigned int}
      |          %ld
mat.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   25 |  scanf("%d%d", &M, &N);
      |  ~~~~~^~~~~~~~~~~~~~~~
mat.cpp:26:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |  for(int i=1; i<=M; i++) scanf("%d", &C[i]);
      |                          ~~~~~^~~~~~~~~~~~~
mat.cpp:28:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 8556 KB Output is correct
2 Correct 13 ms 8556 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct

Subtask #5
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 11484 KB Output is correct
2 Correct 76 ms 10988 KB Output is correct
3 Correct 123 ms 12652 KB Output is correct
4 Correct 127 ms 12780 KB Output is correct

Subtask #6
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 12396 KB Output is correct
2 Correct 111 ms 11756 KB Output is correct
3 Correct 89 ms 12396 KB Output is correct
4 Correct 93 ms 13316 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 12392 KB Output is correct
2 Correct 83 ms 11756 KB Output is correct
3 Correct 101 ms 11884 KB Output is correct

Subtask #8
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 520 ms 29416 KB Output is correct
2 Correct 997 ms 44184 KB Output is correct
3 Correct 425 ms 22268 KB Output is correct

Subtask #9
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 512 ms 29420 KB Output is correct
2 Correct 634 ms 22764 KB Output is correct
3 Correct 1071 ms 40332 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 463 ms 25700 KB Output is correct
2 Correct 488 ms 33876 KB Output is correct
3 Correct 543 ms 26608 KB Output is correct
4 Correct 607 ms 42376 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 444 ms 26724 KB Output is correct
2 Correct 542 ms 27244 KB Output is correct
3 Correct 208 ms 17388 KB Output is correct
4 Correct 680 ms 41708 KB Output is correct