Submission #1053481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053481		VMaksimoski008	Toys (CEOI18_toy)	C++17	100 / 100	1232 ms	86868 KiB

toy

#include <bits/stdc++.h>
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

signed main() {
    //a b c
    //(a + 1)(b + 1)(c + 1) = n
    //maks log(n) razlicni
    //baska (a + 1), (b + 1), (c + 1) | n

    int n;
    cin >> n;

    vector<int> div;
    for(int i=1; i*i<=n; i++) {
        if(n % i > 0) continue;
        div.push_back(i);
        if(n / i != i) div.push_back(n/i);
    }

    map<int, int> mp;
    sort(div.begin(), div.end());
    for(int i=0; i<div.size(); i++) mp[div[i]] = i;

    int m = div.size();
    set<int> dp[m]; dp[0].insert(0);

    for(int i=1; i<m; i++) {
        for(int j=1; j*j<=div[i]; j++) {
            if(div[i] % j == 0 && j > 1)
                for(auto &x : dp[mp[div[i]/j]]) dp[i].insert(x+j-1);
            if(div[i] % j == 0 && div[i] / j > 1)
                for(auto &x : dp[mp[j]]) dp[i].insert(x+(div[i]/j)-1);
        }
    }

    cout << dp[m-1].size() << '\n';
    for(auto &x : dp[m-1]) cout << x << " ";
    return 0;
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0; i<div.size(); i++) mp[div[i]] = i;
      |                  ~^~~~~~~~~~~

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