Submission #481190

#	Time	Username	Problem	Language	Result	Execution time	Memory
481190		hidden1	Toys (CEOI18_toy)	C++14	59 / 100	5079 ms	24816 KiB

toy

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(ll i = 0; i < n; i ++)
#define revn(i, n) for(ll i = n - 1; i >= 0; i --)
typedef long long ll;
template<class T, template<class T2, class A=allocator<T2> > class cont> inline ostream &operator <<(ostream &out, const cont<T> &x) { for(const auto &it : x) { out << it << " ";} return out;}
template<class T, template<class T2, class A=allocator<T2> > class cont> inline istream &operator >>(istream &in, cont<T> &x) { for(auto &it : x) { in >> it;} return in;}
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;

const ll MAX_N = 4e6 + 10, MAX_CORD = 2e3 + 10;
ll n;
vector<ll> divis;

void comp(ll x) {
    for(ll i = 1; i * i <= x; i ++) {
        if(x % i == 0) {
            divis.push_back(i);
            if(i * i != x) {
                divis.push_back(x / i);
            }
        }
    }

    sort(all(divis));
}

set<int> dp[MAX_CORD];
ll who[MAX_CORD][MAX_CORD];

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    if(n == 1) {
        cout << 1 << endl << 0 << endl;
        return 0;
    }

    comp(n);

    forn(i, divis.size()) {
        dp[i].insert(divis[i] - 1);
        forn(j, divis.size()) {
            ll prod = divis[i] * divis[j];
            ll to = -1;
            if(n % prod == 0) {
                to = lower_bound(all(divis), prod) - divis.begin();
            } else {
                continue;
            }
            for(auto it1 : dp[i]) {
                for(auto it2 : dp[j]) {
                    dp[to].insert(it1 + it2);
                }
            }
        }
    }

    cout << dp[divis.size() - 1].size() << endl;
    for(auto it : dp[divis.size() - 1]) {
        cout << it << " ";
    }
    cout << endl;

    return 0;
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:10:36: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define forn(i, n) for(ll i = 0; i < n; i ++)
......
   52 |     forn(i, divis.size()) {
      |          ~~~~~~~~~~~~~~~            
toy.cpp:52:5: note: in expansion of macro 'forn'
   52 |     forn(i, divis.size()) {
      |     ^~~~
toy.cpp:10:36: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define forn(i, n) for(ll i = 0; i < n; i ++)
......
   54 |         forn(j, divis.size()) {
      |              ~~~~~~~~~~~~~~~        
toy.cpp:54:9: note: in expansion of macro 'forn'
   54 |         forn(j, divis.size()) {
      |         ^~~~

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