Submission #1196906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196906		LucaLucaM	Toys (CEOI18_toy)	C++17	100 / 100	1978 ms	86476 KiB

toy

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  
  int n;
  std::cin >> n;

  std::vector<int> divs;
  for (int d = 1; d * d <= n; d++) {
    if (n % d == 0) {
      divs.push_back(d);
      if (d * d != n) {
        divs.push_back(n / d);
      }
    }
  }

  std::sort(divs.begin(), divs.end());

  int sz = (int) divs.size();
  std::vector<std::set<int>> sums(sz);
  
  sums[0].insert(0);
  for (int i = 1; i < sz; i++) {
    for (int j = 0; j < i; j++) {
      if (divs[i] % divs[j] == 0) {
        // sums[i] U= sums[j] + divs[i] / divs[j] - 1
        for (int k : sums[j]) {
          sums[i].insert(k + divs[i] / divs[j] - 1);
        }
      }
    }
  }
  
  std::cout << sums.back().size() << '\n';
  for (int x : sums.back()) {
    std::cout << x << ' ';
  }
  
  return 0;
}

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