Submission #730207

#	Time	Username	Problem	Language	Result	Execution time	Memory
730207		dozer	Toys (CEOI18_toy)	C++14	100 / 100	362 ms	134144 KiB

toy

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("bmi2,avx2")
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 60005
#define M 3005
#define A 1000000008

const int modulo = 1e9 + 7;

vector<int> dv[M];
int cnt[N];
bitset<N> dp[M];

int32_t main()
{
	fastio();

	int n;
	cin>>n;
	if (n == 1)
	{
		cout<<1<<"\n"<<0<<endl;
		return 0;
	}

	vector<int> v;
	int s = 0;
	for (int i = 1; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			if (i != 1) v.pb(i);
			if (n / i != i) v.pb(n / i);
		}
		s = i;
	}

	sort(v.begin(), v.end());
	int m = v.size();

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j <= i; j++)
			if (v[i] % v[j] == 0) dv[i].pb(j);
	}

	for (int i = 0; i < m; i++)
	{
		if (v[i] <= s) dp[i][v[i] - 1] = 1;
		for (auto j : dv[i])
			if (j != i) dp[i] |= (dp[j]<<(v[i] / v[j] - 1));
	}

	bitset<A> all;

	for (int i = 0; i < N; i++)
		if (dp[m - 1][i]) all[i] = 1;

	
	for (int it = 0; v[it] < s; it++)
	{
		for (int i = 0; i < N; i++)
			if (dp[it][i]) all[i + n / v[it] - 1] = 1;
	}
	all[n - 1] = 1;

	vector<int> ans;
	int pos = all._Find_first();
	while(pos < A)
	{
		ans.pb(pos);
		pos = all._Find_next(pos);
	}
	cout<<ans.size()<<endl;
	for (auto i : ans)
		cout<<i<<sp;
	cout<<endl;
	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

• Subtask 1: 19 / 19
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 21 / 21