Submission #1154880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154880		mutse	Toys (CEOI18_toy)	C++20	59 / 100	1037 ms	327680 KiB

toy

#include <bits/stdc++.h>

#define ll long long

using namespace std;

int n;
// map<priority_queue<int>, bool> visited;
map<int, bool> ansdict;
map<int, bool> ittakotoaru;
vector<int> ans;

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

bool visited(priority_queue<int> q){
    return ittakotoaru[f(q)];
}

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

void go(priority_queue<int> q){
    int cnt = 0;
    while(!q.empty()){
        cnt += q.top() - 1;
        q.pop();
    }
    if(!ansdict[cnt]){
        ans.push_back(cnt);
        ansdict[cnt] = 1;
    }
}

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);
        // for(int i = 0; i < smallq.size(); ++i){
        if(!visited(smallq)){
            go(smallq);
            ittakotoaru[f(smallq)];
            // cout << "rotation: ";
            // printq(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(!visited[newq]){
                        // cout << "factorized " << qfront << " into " << j << ' ' << qfront / j << '\n';
                        // cout << "push: ";
                        // printq(newq);
                        // visited[newq] = 1;
                    q.push(newq);
                    // }
                }
            }
            smallq.push(qfront);
        }
    }
}


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: 19 / 19
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 21