Submission #920841

#	Time	Username	Problem	Language	Result	Execution time	Memory
920841		Ghulam_Junaid	Toys (CEOI18_toy)	C++17	59 / 100	5041 ms	83148 KiB

toy

#include <bits/stdc++.h>
using namespace std;

int n;
map<vector<int>, bool> vis;
set<int> output;

int good, sizes;

inline int compute(vector<int> v){
    int sm = 0;
    for (int x : v)
        sm += x;
    return sm - v.size();
}

void bfs(vector<int> vec){
    sort(vec.begin(), vec.end());

    queue<vector<int>> q;
    q.push(vec);
    vis[vec] = 1;

    while (!q.empty()){
        vector<int> vec = q.front();
        q.pop();

        good ++;
        sizes += vec.size();

        output.insert(compute(vec));
        for (int i=0; i<vec.size() - 1; i++){
            for (int j=i+1; j<vec.size(); j++){
                vector<int> nvec;
                for (int k=0; k<i; k++)
                    nvec.push_back(vec[k]);
                for (int k=i+1; k<j; k++)
                    nvec.push_back(vec[k]);
                for (int k=j+1; k<vec.size(); k++)
                    nvec.push_back(vec[k]);
                nvec.push_back(vec[i] * vec[j]);

                sort(nvec.begin(), nvec.end());
                if (!vis[nvec]){
                    q.push(nvec);
                    vis[nvec] = 1;
                }
            }
        }
    }
}

int main(){
    cin >> n;

    vector<int> vec;
    vec.push_back(1);
    for (int x = 2; x * x <= n; x ++){
        if (n % x) continue;
        while (n % x == 0){
            n /= x;
            vec.push_back(x);
        }
    }
    if (n - 1)
        vec.push_back(n);

    bfs(vec);

    cout << output.size() << endl;
    for (int x : output)
        cout << x << " ";
    cout << endl;
}

Compilation message (stderr)

toy.cpp: In function 'void bfs(std::vector<int>)':
toy.cpp:32:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for (int i=0; i<vec.size() - 1; i++){
      |                       ~^~~~~~~~~~~~~~~
toy.cpp:33:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |             for (int j=i+1; j<vec.size(); j++){
      |                             ~^~~~~~~~~~~
toy.cpp:39:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |                 for (int k=j+1; k<vec.size(); k++)
      |                                 ~^~~~~~~~~~~

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