Submission #481192

#	Time	Username	Problem	Language	Result	Execution time	Memory
481192		hidden1	Triangles (CEOI18_tri)	C++14	0 / 100	1 ms	332 KiB

tri

#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));
}

unordered_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);

    dp[0].insert(0);

    forn(i, divis.size()) {
        forn(j, i + 1) {
            if(divis[i] % divis[j] != 0) {
                continue;
            }
            for(auto it : dp[j]) {
                dp[i].insert(it + divis[i] / divis[j] - 1);
            }
        }
    }

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

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25