제출 #1246644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246644		Jovica	Toys (CEOI18_toy)	C++20	79 / 100	5099 ms	138828 KiB

toy

#include <bits/stdc++.h>

using namespace std;
bool ima[1000000];
int odg = 0;
set<int> ans;
map<vector<array<int,2> > , bool> visited;
bool sito[100000];

void f(vector<array<int,2> > v)
{
    int p = v.size()-1;
    for (int i = 0;i<p;i++) {
        if (v[i][1] == 0) swap(v[i],v[p]),p--;
    }
    while(v.back()[1] == 0) v.pop_back();
    sort(v.begin(),v.end());
    if (visited[v]) return;
    visited[v] = true;

    //for (auto a: v) cout<<a[0]<< " "<<a[1]<<",";cout<<endl;

    int z = 0;

    for (int i=0;i<v.size();i++)
    {
        z += (v[i][0]-1) * v[i][1];
        if (v[i][1] > 1){
            v.push_back({v[i][0]*v[i][0],1});
            v[i][1]-=2;
            f(v);
            v.pop_back();
            v[i][1]+=2;
        }
        for (int j=i+1;j<v.size();j++)
        {
            v.push_back({v[i][0]*v[j][0],1});
            v[i][1]--;v[j][1]--;
            f(v);
            v.pop_back();
            v[i][1]++;v[j][1]++;
        }
    }
    if (z>=1000000) ans.insert(z);
    else {
        if (ima[z] == false) odg++;
        ima[z] = true;
    }
}

int main()
{
    //f({{2,0},{3,4},{6,0},{5,1}});

    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    const int B = sqrt(n);

    if (n == 1){
        cout<<"1\n0"<<endl;
        return 0;
    }

    for (int i=2;i<=B;i++){
        if (sito[i]) continue;
        for (int j=i*2;j<=B;j+=i) sito[j] = true;
    }

    //cout<<"mine\n";
    vector<array<int,2> > v;

    for (int i=2;i<=B;i++)
    {
        if (sito[i] == false && n%i == 0)
        {
            v.push_back({i,0});
            while (n%i == 0){
                n/=i;
                v.back()[1]++;
            }
        }
    }
    if (n > 1) v.push_back({n,1});



    //for (auto a: v) cout<<a[0]<<" "<<a[1]<<endl;cout<<"-\n";

    f(v);

    cout<<ans.size()+odg<<"\n";
    string res = "";
    for (int i=0;i<1000000;i++) if (ima[i]) res += to_string(i) + " ";
    for (auto a: ans) res += to_string(a) + " ";
    cout<<res;
    return 0;
}

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