Submission #841823

#	Time	Username	Problem	Language	Result	Execution time	Memory
841823		WLZ	Toys (CEOI18_toy)	C++17	100 / 100	1092 ms	135244 KiB

toy

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n; cin >> n;
  vector<int> div;
  for (int i = 1; i * i <= n; i++) {
    if (n % i != 0) continue;
    div.push_back(i);
    if (i * i != n) div.push_back(n / i);
  }
  vector< vector< pair<int, int> > > multiples((int) div.size());
  sort(div.begin(), div.end());
  for (int i = 0; i < (int) div.size(); i++) {
    for (int j = i + 1; j < (int) div.size(); j++) {
      if (div[j] % div[i] == 0) multiples[i].emplace_back(j, div[j] / div[i]);
    }
  }
  vector< vector<int> > ans((int) div.size()); ans[0] = {0};
  for (int i = 0; i < (int) div.size() - 1; i++) {
    sort(ans[i].begin(), ans[i].end());
    ans[i].erase(unique(ans[i].begin(), ans[i].end()), ans[i].end());
    for (auto &[j, y] : multiples[i]) {
      for (auto &x : ans[i]) ans[j].push_back(x + y - 1);
    }
    ans[i].clear();
  }
  sort(ans.back().begin(), ans.back().end());
  ans.back().erase(unique(ans.back().begin(), ans.back().end()), ans.back().end());
  cout << (int) ans.back().size() << '\n';
  for (auto &x : ans.back()) cout << x << ' ';
  cout << '\n';
  return 0;
}

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