Submission #385755

#TimeUsernameProblemLanguageResultExecution timeMemory
385755mohamedsobhi777Toys (CEOI18_toy)C++14
79 / 100
5053 ms4268 KiB
#include <bits/stdc++.h> #pragma GCC optimize("-Ofast") //#pragma GCC optimize("trapv") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-funroll-loops") using namespace std; #define vi vector<int> #define vll vector<ll> #define vii vector<pair<int, int>> #define pii pair<int, int> #define pll pair<ll, ll> #define loop(_) for (int __ = 0; __ < (_); ++__) #define pb push_back #define f first #define s second #define sz(_) ((int)_.size()) #define all(_) _.begin(), _.end() #define lb lower_bound #define ub upper_bound using ll = long long; using ld = long double; const int N = 1e5 + 7; const ll mod = 1e9 + 7; int n; set<int> ans; vi prm; vi facto(int x) { vi ret; for (int i = 2; i * i <= x; ++i) { while (x % i == 0) { ret.pb(i); x /= i; } } if (x > 1) ret.pb(x); return ret; } int sum; int tkn = 0; int lst = 0; void backtrack() { if (tkn == (1 << sz(prm)) - 1) { ans.insert(sum); return; } int ntkn = (tkn ^ ((1 << sz(prm)) - 1)); for (int i = ntkn; i; i = (i - 1) & ntkn) { // if ((tkn & i)) // continue; int asum = 1; bool flag = 0; for (int j = 0; j < sz(prm); ++j) { if (i & (1 << j)) { asum *= prm[j]; auto got = [&](int u, int z) -> bool { return (u >> z) & 1; }; if (j && prm[j] == prm[j - 1] && !got(tkn, j - 1) && !got(i, j - 1)) { flag = 1; break; } } } if (flag || asum < lst) continue; sum += asum - 1; int omask = tkn; int olst = lst; tkn |= i; lst = asum; backtrack(); tkn = omask; lst = olst; sum -= asum - 1; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); #ifndef ONLINE_JUDGE #endif cin >> n; // n = (1 << 26); prm = facto(n); sort(all(prm)); vi lhs, rhs; for (int i = 0; i < sz(prm); ++i) { if (i < sz(prm) / 2) lhs.pb(prm[i]); else rhs.pb(prm[i]); } backtrack(); cout << sz(ans) << "\n"; for (auto u : ans) { cout << u << " "; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...