Submission #347404

#	Time	Username	Problem	Language	Result	Execution time	Memory
347404		kingfran1907	Matching (CEOI11_mat)	C++14	100 / 100	1331 ms	46092 KiB

mat

#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 (stderr)

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 / 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: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10