Submission #1154878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154878		mutse	Toys (CEOI18_toy)	C++20	0 / 100	0 ms	528 KiB

toy

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int n;
map<int, bool> ittakotoaru;
vector<int> ans;

int f(priority_queue<int> q){
    int ans = 0;
    while(!q.empty()){
        ans += q.top() - 1;
        q.pop();
    }
    return ans;
}

void printq(priority_queue<int> q){
    while(!q.empty()){
        cout << q.top() << ' ';
        q.pop();
    }
    cout << '\n';
}

void bfs(){
    queue<priority_queue<int>> q;
    priority_queue<int> tmp;
    tmp.push(n);
    q.push(tmp);
    while(!q.empty()){
        priority_queue<int> smallq = q.front();
        q.pop();
        // cout << "pop: ";
        // printq(smallq);
        ans.push_back(f(smallq));
        int qfront = smallq.top();
        // cout << "now working on: " << qfront << '\n';
        smallq.pop();
        for(int j = 2; j <= sqrt(qfront); ++j){
            priority_queue<int> newq = smallq;
            if(qfront % j == 0){
                newq.push(j);
                newq.push(qfront / j);
                if(!ittakotoaru[f(newq)]){
                    // cout << "factorized " << qfront << " into " << j << ' ' << qfront / j << '\n';
                    // cout << "push: ";
                    // printq(newq);
                    ittakotoaru[f(newq)] = 1;
                    q.push(newq);
                }
            }
        }
    }
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    bfs();
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for(auto i: ans){
        cout << i << ' ';
    }
}

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