Submission #169845

#	Time	Username	Problem	Language	Result	Execution time	Memory
169845		arnold518	Toys (CEOI18_toy)	C++14	100 / 100	1943 ms	217424 KiB

toy

#include <bits/stdc++.h>
using namespace std;

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

const ll MAXN = 1e9;

ll N;
vector<ll> V;
vector<vector<ll>> dp;

int main()
{
	ll i, j;

	scanf("%lld", &N);
	for(i=1; i*i<=N; i++)
	{
		if(N%i) continue;
		V.push_back(i);
		V.push_back(N/i);
	}

	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());

	dp.resize(V.size());
	dp[0].push_back(0);
	for(i=1; i<V.size(); i++)
	{
		for(j=0; j<i; j++)
		{
			if(V[i]%V[j]) continue;
			for(auto it : dp[j]) dp[i].push_back(it+V[i]/V[j]-1);
		}
		sort(dp[i].begin(), dp[i].end());
		dp[i].erase(unique(dp[i].begin(), dp[i].end()), dp[i].end());
	}

	printf("%d\n", dp.back().size());
	for(auto it : dp.back()) printf("%d ", it);
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:31:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=1; i<V.size(); i++)
           ~^~~~~~~~~
toy.cpp:42:33: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<long long int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", dp.back().size());
                 ~~~~~~~~~~~~~~~~^
toy.cpp:43:43: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
  for(auto it : dp.back()) printf("%d ", it);
                                           ^
toy.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &N);
  ~~~~~^~~~~~~~~~~~

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