Submission #112427

#	Time	Username	Problem	Language	Result	Execution time	Memory
112427		Magisko	Toys (CEOI18_toy)	C++14	59 / 100	5070 ms	82200 KiB

toy

#include <bits/stdc++.h>

using namespace std ;

vector<int> primes ;
bool isprime[105000] ;

int maxi(int n)
{
  int counter = 0 ;
  int m = n ;
  for (int i(0) ; i<primes.size() ; i++)
  {
    while(n%primes[i]==0)
    {
      n /= primes[i] ;
      counter++ ;
    }
  }
  if (n==m) return 2 ;
  return counter ;
}

vector<vector<int>> f(int n, int k)
{
  if (k==0) return {} ;
  if (k==1) return {{n}} ;
  if (n==1) return {{1}} ;
  vector<vector<int>> sol ;
  vector<int> par ;
  par.clear() ;
  sol.clear() ; 
  for (int i(2) ; i<n ; i++)
  {
    if (n%i==0)
    {
      vector<vector<int>> pre = f(n/i , k-1) ;
      for (int j(0) ; j<pre.size() ; j++)
      {
        par.push_back(i) ; 
        for (int u(0) ; u<pre[j].size() ; u++)
        {
          par.push_back(pre[j][u]) ;
        }
        sol.push_back(par) ;
        par.clear() ;
      }
    }
  }
  if (sol.empty()) return {{n}};
  return sol ;
}

int main()
{
  for (int i(0) ; i<105000 ; i++)
  {
    isprime[i] = 1 ; 
  }
  for (int i(2) ; i<105000 ; i++)
  {
    if (isprime[i])
    {
      for (int j(2);  i*j<105000 ; j++)
      {
        isprime[i*j] = 0 ;
      }
    }
  }
  for (int i(2) ; i<105000 ; i++)
    if (isprime[i])
      primes.push_back(i) ; 
  int n ; 
  cin >> n ;
  int top = maxi(n) ;
  vector<int> sums ;
  vector<bool> used(n,false) ;
  for (int k(1) ; k<=top ; k++)
  {
    vector<vector<int>> p = f(n,k) ;
    for (int i(0) ; i<p.size() ; i++)
    {
      int sum = 0 ;
      for (int j(0) ; j<p[i].size() ; j++)
      {
        sum += p[i][j]-1 ;
      }
      if (!used[sum])
      {
        sums.push_back(sum) ;
        used[sum] = 1 ;
      }
    }
  }
  sort(sums.begin(),sums.end()) ;
  cout << sums.size() << '\n' ; 
  for (int i(0) ; i<sums.size() ; i++)
    cout << sums[i] << ' ' ;
  return 0;
}

Compilation message (stderr)

toy.cpp: In function 'int maxi(int)':
toy.cpp:12:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i(0) ; i<primes.size() ; i++)
                   ~^~~~~~~~~~~~~~
toy.cpp: In function 'std::vector<std::vector<int> > f(int, int)':
toy.cpp:38:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j(0) ; j<pre.size() ; j++)
                       ~^~~~~~~~~~~
toy.cpp:41:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int u(0) ; u<pre[j].size() ; u++)
                         ~^~~~~~~~~~~~~~
toy.cpp: In function 'int main()':
toy.cpp:81:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i(0) ; i<p.size() ; i++)
                     ~^~~~~~~~~
toy.cpp:84:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j(0) ; j<p[i].size() ; j++)
                       ~^~~~~~~~~~~~
toy.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i(0) ; i<sums.size() ; i++)
                   ~^~~~~~~~~~~~

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