Submission #444708

#	Time	Username	Problem	Language	Result	Execution time	Memory
444708		definitelynotmee	Toys (CEOI18_toy)	C++98	100 / 100	3338 ms	98396 KiB

toy

#include <bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MOD = 1e9 + 7;
const int MAXN = 1e6+1;

int power(int in, int exp){
    int cur = in;
    int resp = 1;
    for(int i = 0; i < 31; i++){
        if((1<<i)&exp){
            resp*=cur;
        }
        cur*=cur;
    }
    return resp;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    if(n==1){
        cout << 1 << '\n' << 0 << '\n';
        return 0;
    }
    vector<int>fat;
    vector<int>num;
    for(int i = 2; i <= sqrt(n); i++){
        if(n%i == 0){
            fat.push_back(i);
            num.push_back(0);
            while(n%i == 0){
                num[num.size()-1]++;
                n/=i;
            }
        }
    }
    if(n!=0)
        fat.push_back(n),num.push_back(1);
    map<vector<int>,vector<pii>> m;
    vector<int> base(fat.size(),0);
    m[base] = {{0,0}};
    function<void(vector<int>)> bt;

    function<void(int,int,vector<int>&, vector<pii>&)> choice = [&](int id, int cur, vector<int>&v, vector<pii>& resp){
        if(id == v.size()){
            if(cur==1)
                return;
            bt(v);
            for(pii i : m[v]){
                resp.push_back({i.ff+1,i.ss+cur});
            }
            return;
        }
        int aux = v[id];
        int add = 1;
        while(v[id]>=0){
            choice(id+1,cur*add,v,resp);
            v[id]--;
            add*=fat[id];
        }
        v[id] = aux;
    };
    bt = [&](vector<int>v){
        if(m.find(v)!=m.end())
            return;

        vector<pii> resp;
        
        choice(0,1,v,resp);
        sort(resp.begin(),resp.end());
        vector<pii> trueresp;
        if(resp.size()>0){
            trueresp.push_back(resp[0]);
            for(int i = 1; i < resp.size(); i++)
                if(resp[i]!=resp[i-1])
                    trueresp.push_back(resp[i]);
        }
        
        m[v] = trueresp;
    };

    bt(num);
    set<int> trueresp;
    for(pii i : m[num]){
        trueresp.insert(i.ss-i.ff);
    }

    cout << trueresp.size() << '\n';
    for(int i : trueresp)
        cout << i << ' ';
    return 0;

}

Compilation message (stderr)

toy.cpp: In lambda function:
toy.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         if(id == v.size()){
      |            ~~~^~~~~~~~~~~
toy.cpp: In lambda function:
toy.cpp:87:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             for(int i = 1; i < resp.size(); i++)
      |                            ~~^~~~~~~~~~~~~

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