Submission #973895

#	Time	Username	Problem	Language	Result	Execution time	Memory
973895		efedmrlr	Toys (CEOI18_toy)	C++17	100 / 100	1183 ms	19504 KiB

toy

#include <bits/stdc++.h>

#define lli long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)

using namespace std;

const int INF = 1e9 + 5;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
vector<int> f(vector<array<int, 2> > x, int cap);
void find_divis(vector<array<int, 2> > &x, int ind, vector<int> &ret, int cur, int cap, vector<array<int, 2> > &lft) {
    if(cur > cap) return;
    if(x.size() == ind) {
        if(cur == 1) return;
        vector<int> tmp = f(lft, cur);
        for(auto c : tmp) {
            ret.pb(c + cur - 1);
        }
        return;
    }
    lft.pb(x[ind]);
    find_divis(x, ind + 1, ret, cur, cap, lft);
    for(int i = 1; i <= x[ind][1]; i++) {
        cur *= x[ind][0];
        lft[lft.size() - 1][1]--;
        if(lft[lft.size() - 1][1] == 0) lft.pop_back();
        find_divis(x, ind + 1, ret, cur, cap, lft);
    }
    
}
vector<int> f(vector<array<int, 2> > x, int cap) {
    // cout << "cap:" << cap << endl;
    // for(auto c : x) { 
    //     cout << c[0] << " " << c[1] << endl;
    // }
    // cout << "end\n";
    if(x.empty()) return {0};
    if(cap < x.back()[0]) return {};
    vector<int> ret;
    vector<array<int, 2> > lft;
    find_divis(x, 0, ret, 1, cap, lft);
    return ret;
}

void solve() {
    int n;
    cin >> n;
    int SQRN = sqrt(n) + 30; 
    vector<array<int, 2> > pri;
    array<int, 2> last = {0, 0};
    int cur = n;
    for(int i = 2; i <= SQRN; i++) {
        last[0] = i;
        while(!(cur % i)) {
            last[1]++;
            cur /= i;
        }
        if(last[1]) {
            pri.pb(last);
            last = {0, 0};
        }
    }   
    if(cur > 1) {
        pri.pb({cur, 1});
    }
    
    vector<int> ret = f(pri, INF);
    sort(all(ret));
    ret.resize(unique(all(ret)) - ret.begin());
    cout << ret.size() << "\n";
    for(auto c : ret) {
        cout << c << " ";
    }
    cout << "\n";
}

signed main() {
    fastio();
    solve();
}

Compilation message (stderr)

toy.cpp: In function 'void find_divis(std::vector<std::array<int, 2> >&, int, std::vector<int>&, int, int, std::vector<std::array<int, 2> >&)':
toy.cpp:22:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |     if(x.size() == ind) {
      |        ~~~~~~~~~^~~~~~

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