Submission #490990

#	Time	Username	Problem	Language	Result	Execution time	Memory
490990		Mike4235	Toys (CEOI18_toy)	C++17	100 / 100	3086 ms	84572 KiB

toy

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
// #define int long long
 
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;
 
using namespace std;
 
const int MX = 1e5;
 
int n;
unordered_map<int, vector<pii>> mp;
unordered_map<int, bool> flag;
set<int> se;
 
void solve(int x, int sum) {
    if (flag[x * MOD + sum]) return;
    flag[x * MOD + sum] = 1;
    se.insert(sum + x - 1);
 
    if (mp.find(x) != mp.end()) {
        for (auto p : mp[x]) solve(p.first, sum + p.second - 1);
    }
    else {
        for (int i = 2; i * i <= x; i++) if (x % i == 0) {
            if (i * i == x) {
                mp[x].push_back({i, i});
                solve(i, sum + i - 1);
            }
            else {
                int j = x / i;
                mp[x].push_back({i, j});
                mp[x].push_back({j, i});
                solve(i, sum + j - 1);
                solve(j, sum + i - 1);
            }
        }
    }
}
 
signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);s
 
    cin >> n;
    solve(n, 0);
 
    cout << sz(se) << "\n";
    for (auto x : se) cout << x << " ";
    
}

Compilation message (stderr)

toy.cpp:21:17: warning: overflow in conversion from 'long int' to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
   21 | const int INF = 1000000000000000000;
      |                 ^~~~~~~~~~~~~~~~~~~

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