www.main.edu.pl/en/user.phtml?op=showtask&task=bon&con=OI19 19th Polish Olympiad in Informatics Stage II - day 1

Vouchers.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

const int maxn = 1000011;

int n, m, x, maxm, a[maxn], pos[maxn];
int head[maxn];
bool vis[maxn];
long long now;
vector<long long> ans;

int main() {
    memset(pos, 0, sizeof(pos));
	memset(vis, false, sizeof(vis));
	ans.clear(); now = 0; maxm = 0;
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d", &x);
		maxm = max(maxm, x);
		pos[x] ++;
	}
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		head[a[i]] = a[i];
	}
	for (int i = 1; i <= n; i++) {
		// int cnt = 0;
		x = a[i];
		
		for (int j = 1; j <= x && head[x] < maxm + 10; j++) {
			if (vis[head[x]]) {
				head[x] += x;
				j--;
				continue;
			}
			if (!vis[head[x]]) {
				vis[head[x]] = true;
				if (pos[head[x]])
					ans.push_back(j + now);
			}
			head[x] += x;
		}
		//这种写法会T，上面那种能AC，不知道为什么 T_T
		// for (int j = x; cnt < x && j < maxm + 10; j += x) {
		// 	if (!vis[j]) {
		// 		cnt++; vis[j] = true;
		// 		if (pos[j]) {
		// 			ans.push_back(cnt + now);
		// 			pos[j] = 0;
		// 		}
		// 	}
		// }
		now +=x;
	}
	//for (int i = 0; i < num.size(); i++)
	//	printf("%d\n", num[i]);
	// for (int i = 0; i < num.size(); i++) {
	// 	if (pos[num[i]])
	// 		ans.push_back(i+1);
	// }
	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); i++)
		printf("%lld\n", ans[i]);
	return 0;
}