oj.uz

Submission #1039136

# Submission time Handle Problem Language Result Execution time Memory
1039136 2024-07-30T13:32:59 Z 0npata Toys (CEOI18_toy) C++17
0 / 100
 1 ms 348 KB 
#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;
    if(pi == primes.size()) return;
    int j = pi;
    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;
   }
   go(cur, lst, id, pi+1);
    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

toy.cpp: In function 'void go(long long int, long long int, long long int, long long int)':
toy.cpp:31: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]
   31 |     if(pi == primes.size()) return;
      |        ~~~^~~~~~~~~~~~~~~~
toy.cpp: In function 'int32_t main()':
toy.cpp:61: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]
   61 |      for(int i = 1; i<ans.size(); i++) {
      |                     ~^~~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -