Submission #503603

#	Time	Username	Problem	Language	Result	Execution time	Memory
503603		andrei_boaca	Toys (CEOI18_toy)	C++17	100 / 100	4185 ms	58756 KiB

toy

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef pair<int,int> pii;
int n;
set<int> sol;
vector<int> v;
queue<vector<int>> coada;
unordered_map<int,int> use;
map<vector<int>,int> vuse;
int niv;
int main()
{
    cin>>n;
    int d=2;
    while(n>1)
    {
        while(n%d==0)
        {
            v.push_back(d);
            n/=d;
        }
        d++;
        if(d%2==0)
            d++;
        if(d*d>n&&n>1)
        {
            v.push_back(n);
            break;
        }
    }
    sort(v.begin(),v.end());
    coada.push(v);
    vuse[v]=1;
    niv=v.size();
    while(!coada.empty())
    {
        vector<int> a=coada.front();
        coada.pop();
        int suma=0;
        for(auto i:a)
            suma+=i;
        suma-=a.size();
        sol.insert(suma);
        pii x={0,0};
        for(int i=0;i<a.size();i++)
            for(int j=i+1;j<a.size();j++)
                if(i!=x.first||j!=x.second)
                {
                    x={i,j};
                    int s=suma-a[i]-a[j]+1+a[i]*a[j];
                    if(use[s]<20)
                    {
                        vector<int> aux;
                        for(int p=0;p<a.size();p++)
                            if(p!=i&&p!=j)
                                aux.push_back(a[p]);
                        aux.push_back(a[i]*a[j]);
                        sort(aux.begin(),aux.end());
                        if(!vuse[aux])
                        {
                            use[s]++;
                            vuse[aux]=1;
                            sol.insert(s);
                            coada.push(aux);
                        }
                    }
                }
    }
    cout<<sol.size()<<'\n';
    for(auto i:sol)
        cout<<i<<' ';
    return 0;
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i=0;i<a.size();i++)
      |                     ~^~~~~~~~~
toy.cpp:47:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for(int j=i+1;j<a.size();j++)
      |                           ~^~~~~~~~~
toy.cpp:55:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                         for(int p=0;p<a.size();p++)
      |                                     ~^~~~~~~~~

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