Submission #347404

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
347404	2021-01-12T22:50:25 Z	kingfran1907	Matching (CEOI11_mat)	C++14	100 / 100	1331 ms	46092 KB

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 1e6+10;
const int base = 101;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, m;
int a[maxn], b[maxn];
int tour[treesiz], cnt[treesiz], p[treesiz];
int pot[maxn];
vector< int > v;
int as[maxn];

int mul(int a, int b) {
	llint out = (llint)a * b;
	return out % mod;
}

void update(int x, int val, int cn) {
	x += off;
	p[x] = val;
	cnt[x] = cn;
	
	x /= 2;
	while (x > 0) {
		tour[x] = (tour[x * 2] + tour[x * 2 + 1]) % mod;
		p[x] = (p[x * 2] + p[x * 2 + 1]) % mod;
		cnt[x] = cnt[x * 2] + cnt[x * 2 + 1];
		
		tour[x] += mul(p[x * 2 + 1], cnt[x * 2]);
		tour[x] %= mod;
		x /= 2;
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d", a+i);
	for (int i = 0; i < m; i++)
		scanf("%d", b+i);
		
	for (int i = 0; i < m; i++)
		v.push_back(b[i]);
	sort(v.begin(), v.end());
	for (int i = 0; i < m; i++)
		b[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin();
	
	int has = 0;
	pot[0] = 1;
	for (int i = 1; i <= m; i++) pot[i] = mul(pot[i - 1], base);
	
	for (int i = 0; i < n; i++) as[a[i]] = i;
	for (int i = 1; i <= n; i++) {
		has += mul(pot[n - i], as[i]);
		has %= mod;
	}
	
	vector< int > sol;
	for (int i = 0; i <= m - n; i++) {
		if (i == 0) {
			for (int j = 0; j < n; j++) {
				update(b[j], pot[m - j - 1], 1);
			}
		}
		
		//printf("debug: %d %d\n", mul(has, pot[m - n - i]), tour[1]);
		if (mul(has, pot[m - n - i]) == tour[1]) 
			sol.push_back(i + 1);
		update(b[i], 0, 0);
		update(b[i + n], pot[m - n - i - 1], 1);
	}
	
	printf("%d\n", sol.size());
	for (int i = 0; i < sol.size(); i++) {
		printf("%d ", sol[i]);
	}
	return 0;
}

Compilation message

mat.cpp: In function 'int main()':
mat.cpp:83:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   83 |  printf("%d\n", sol.size());
      |          ~^     ~~~~~~~~~~
      |           |             |
      |           int           std::vector<int>::size_type {aka long unsigned int}
      |          %ld
mat.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for (int i = 0; i < sol.size(); i++) {
      |                  ~~^~~~~~~~~~~~
mat.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
mat.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   scanf("%d", a+i);
      |   ~~~~~^~~~~~~~~~~
mat.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |   scanf("%d", b+i);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	492 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	492 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	620 KB	Output is correct
2	Correct	1 ms	620 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	1260 KB	Output is correct
2	Correct	15 ms	1388 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	1308 KB	Output is correct
2	Correct	16 ms	1388 KB	Output is correct
3	Correct	3 ms	620 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	6772 KB	Output is correct
2	Correct	153 ms	8032 KB	Output is correct
3	Correct	216 ms	9568 KB	Output is correct
4	Correct	214 ms	9568 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	168 ms	7520 KB	Output is correct
2	Correct	222 ms	8928 KB	Output is correct
3	Correct	172 ms	9184 KB	Output is correct
4	Correct	174 ms	10208 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	159 ms	7648 KB	Output is correct
2	Correct	155 ms	8800 KB	Output is correct
3	Correct	181 ms	8800 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	936 ms	34388 KB	Output is correct
2	Correct	1178 ms	42580 KB	Output is correct
3	Correct	902 ms	27004 KB	Output is correct

Subtask #9
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	843 ms	33108 KB	Output is correct
2	Correct	1331 ms	33492 KB	Output is correct
3	Correct	1169 ms	42068 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	928 ms	33492 KB	Output is correct
2	Correct	890 ms	46092 KB	Output is correct
3	Correct	1126 ms	34968 KB	Output is correct
4	Correct	693 ms	42452 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	886 ms	34132 KB	Output is correct
2	Correct	1104 ms	36180 KB	Output is correct
3	Correct	397 ms	18780 KB	Output is correct
4	Correct	781 ms	41812 KB	Output is correct