제출 #1246641

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

toy

#include <bits/stdc++.h>

using namespace std;

set<int> ans;
unordered_set<string> visited;
bool sito[100000];

string encode(const vector<array<int,2>>& v) {
    // encode as "p1:e1;p2:e2;...;"
    string s;
    s.reserve(v.size() * 12);
    for (auto& a : v) {
        s += to_string(a[0]);
        s += ':';
        s += to_string(a[1]);
        s += ';';
    }
    return s;
}

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.empty() && v.back()[1] == 0) {
        v.pop_back();
    }

    sort(v.begin(), v.end());
    string key = encode(v);
    if (visited.count(key)) return;
    visited.insert(key);

    int z = 0;
    for (int i = 0; i < (int)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 < (int)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]++;
        }
    }
    ans.insert(z);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    const int B = sqrt(n);

    if (n == 1){
        cout << "1\n0\n";
        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;
        }
    }

    vector<array<int,2>> v;
    for (int i = 2; i <= B; i++) {
        if (!sito[i] && 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});
    }

    f(v);

    cout << ans.size() << "\n";
    for (int a : ans) {
        cout << a << " ";
    }
    cout << "\n";
    return 0;
}

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