Submission #134451

#	Time	Username	Problem	Language	Result	Execution time	Memory
134451		dragonslayerit	Toys (CEOI18_toy)	C++14	100 / 100	3163 ms	86728 KiB

toy

#include <cstdio>
#include <vector>
#include <map>
#include <set>

std::vector<int> factors;

std::map<int,std::set<int> > memo;

const std::set<int>& dfs(int n){
  if(memo.count(n)) return memo[n];
  auto& ans=memo[n];
  if(n==1){
    ans.insert(0);
  }else{
    for(int f:factors){
      if(n%f==0){
	auto& set=dfs(n/f);
	for(int x:set){
	  ans.insert(x+(f-1));
	}
      }
    }
  }
  return ans;
}

int main(){
  int N;
  scanf("%d",&N);
  for(int x=1;x*x<=N;x++){
    if(N%x==0){
      factors.push_back(x);
      if(x*x<N){
	factors.push_back(N/x);
      }
    }
  }
  auto& ans=dfs(N);
  printf("%d\n",(int)ans.size());
  for(int x:ans){
    printf("%d ",x);
  }
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&N);
   ~~~~~^~~~~~~~~

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