Submission #650128

#	Time	Username	Problem	Language	Result	Execution time	Memory
650128		idas	Toys (CEOI18_toy)	C++11	59 / 100	4455 ms	262144 KiB

toy

#pragma GCC optimize("O3")

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define sz(x) ((int)((x).size()))
#define le(vec) vec[vec.size()-1]
#define all(x) (x).begin(), (x).end()
#define TSTS int ttt; cin >> ttt; while(ttt--) solve()
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, begin, end) for(int i = (begin); i < (end); i++)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef pair<long double, long double> pdd;

const int INF=1e9, MOD=1e9+7, mod=998244353;
const ll LINF=1e18;

void setIO()
{
    FAST_IO;
}

void setIO(string s)
{
    FAST_IO;
    freopen((s+".txt").c_str(), "r", stdin);
    freopen((s+".out").c_str(), "w", stdout);
}

set<int> ans;
int n, dls[13], cn[13];

map<pair<pii, vi>, bool> vis;

int idx;

int counter;

void rec(int sum, int now, vi cnt)
{
    if(vis.count({{sum,now},cnt})) return;
    vis[{{sum,now},cnt}]=true;

    if(now!=1) rec(sum+now-1, 1, cnt);

    bool mt=true;
    FOR(i, 0, idx)
    {
        if(cnt[i]!=0){
            mt=false;
            vi nw(all(cnt)); nw[i]--;
            rec(sum, now*dls[i], nw);
        }
        counter++;
    }

    if(mt && now==1){
        ans.insert(sum);
    }
}

int main()
{
    setIO();
    cin >> n;
    multiset<int> tmp;
    while(n%2==0){
        n/=2;
        tmp.insert(2);
    }
    for(int i=3; i*i<=n; i+=2){
        while(n%i==0){
            n/=i;
            tmp.insert(i);
        }
    }
    if(n!=1) tmp.insert(n);
    set<int> st(all(tmp));
    for(auto it : st){
        cn[idx]=tmp.count(it);
        dls[idx++]=it;
    }

    vi init;
    FOR(i, 0, idx)
    {
        init.pb(cn[i]);
    }

    rec(0, 1, init);

    cout << sz(ans) << '\n';
    for(auto x : ans) cout << x << " ";

//    cout << '\n';
//    cout << idx << '\n';

//    cout << "\ncounter: " << counter << endl;
}

//729000000

Compilation message (stderr)

toy.cpp: In function 'void setIO(std::string)':
toy.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     freopen((s+".txt").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toy.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen((s+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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