Submission #481186

#	Time	Username	Problem	Language	Result	Execution time	Memory
481186		hidden1	Fibonacci representations (CEOI18_fib)	C++14	0 / 100	3 ms	972 KiB

fib

#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 = 1e6 + 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));
}

bitset<MAX_N> 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);

    dp[0][0] = true;

    forn(i, divis.size() - 1) {
        cerr << "Starting " << i << ": ";
        forn(j, MAX_N) {
            if(dp[i][j]) {
                cerr << j << " ";
            }
        }
        cerr << endl;
        forn(j, divis.size() - 1) {
            ll prod = divis[i] * divis[j];
            ll to = -1;
            if(n % prod == 0) {
                to = lower_bound(all(divis), prod) - divis.begin();
            } else {
                continue;
            }
            cerr << "from " << divis[i] << " " << divis[j] << " -> " << divis[to] << endl;
            dp[to] |= dp[i] << (divis[j] - 1);
        }
    }

    cout << dp[divis.size() - 1].count() + 1 << endl;
    forn(i, MAX_N) {
        if(dp[divis.size() - 1][i]) {
            cout << i << " ";
        }
    }
    cout << n - 1 << endl;

    return 0;
}

Compilation message (stderr)

fib.cpp: In function 'int main()':
fib.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(i, divis.size() - 1) {
      |          ~~~~~~~~~~~~~~~~~~~        
fib.cpp:54:5: note: in expansion of macro 'forn'
   54 |     forn(i, divis.size() - 1) {
      |     ^~~~
fib.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 ++)
......
   62 |         forn(j, divis.size() - 1) {
      |              ~~~~~~~~~~~~~~~~~~~    
fib.cpp:62:9: note: in expansion of macro 'forn'
   62 |         forn(j, divis.size() - 1) {
      |         ^~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 15
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35