Submission #1039144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039144		0npata	Toys (CEOI18_toy)	C++17	100 / 100	2266 ms	33364 KiB

toy

#include<bits/stdc++.h>
using namespace std;
 
#define vec vector
#define int long long
 
 
vec<int> ans;
vec<pair<int, int>> primes(0);
 
int n;
 
 
void find_primes() {
    int cn = n;
    for(int i = 2; i*i <= cn; i++) {
       if(cn % i == 0) {
           primes.push_back({i, 0});
           while(cn % i == 0) {
               cn /= i;
               primes.back().second++;
           }
       }
    }
    if(cn != 1) primes.push_back({cn, 1});
}
 
 
void go(int cur, int lst, int id, int pi=0, int mul= 1) {
    bool done = true;
    if(mul == n) {
        ans.push_back(id); 
        return;
    }

    if(pi == primes.size()) return;

    int j = pi;
    go(cur, lst, id, pi+1, mul);
    auto &[p, cnt] = primes[j];
    int val = 1;
    for(int i = 0; i<cnt; i++) {
        val *= p;
        cnt -= (i+1); 
        if(cur * val >= lst) {
            go(1, cur*val, id + cur*val-1, 0, mul*cur*val);
        }
        go(cur*val, lst, id, pi+1, mul);
        cnt += (i+1);
   }
}
 
int32_t main() {
    cin >> n;
    
    find_primes();
     
     go(1, 0, 0);
 
     vec<int> ans_filt(0);
     sort(ans.begin(), ans.end());
     ans_filt.push_back(ans[0]);
     for(int i = 1; i<ans.size(); i++) {
         if(ans[i] != ans[i-1]) {
             ans_filt.push_back(ans[i]);
         }
     }
 
    cout << ans_filt.size() << '\n';
    for(int res : ans_filt) {
        cout << res << ' ';
    }
    cout << '\n';
}

Compilation message (stderr)

toy.cpp: In function 'void go(long long int, long long int, long long int, long long int, long long int)':
toy.cpp:36:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if(pi == primes.size()) return;
      |        ~~~^~~~~~~~~~~~~~~~
toy.cpp:30:10: warning: unused variable 'done' [-Wunused-variable]
   30 |     bool done = true;
      |          ^~~~
toy.cpp: In function 'int32_t main()':
toy.cpp:63:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |      for(int i = 1; i<ans.size(); i++) {
      |                     ~^~~~~~~~~~~

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