Submission #1039133

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039133		0npata	Toys (CEOI18_toy)	C++17	79 / 100	5077 ms	131788 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) {
    bool done = true;
    for(int j = pi; j<primes.size(); j++) {
        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);
            }
            go(cur*val, lst, id, pi+1);
            cnt += (i+1);
            done = false;
       }
    }
    if(done && cur == 1) {
        ans.push_back(id); 
    }
}

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)':
toy.cpp:31:22: 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]
   31 |     for(int j = pi; j<primes.size(); j++) {
      |                     ~^~~~~~~~~~~~~~
toy.cpp: In function 'int32_t main()':
toy.cpp:60: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]
   60 |      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: 0 / 21