Submission #405398

#	Time	Username	Problem	Language	Result	Execution time	Memory
405398		ollel	Toys (CEOI18_toy)	C++14	79 / 100	5061 ms	26552 KiB

toy

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

int n;
map<int, vi> d;
map<int, set<int>> dp;


void getd(){
  set<int> divs;
  rep(i, 1, sqrt(n) + 4) {
    if (n % i == 0) {divs.insert(i); divs.insert(n / i);}
  }

  for (auto &i : divs) {
    dp.insert({i, {}});
    d.insert({i, vi(0)});
  }

  for (auto &i : divs){
    int x = 2*i;
    while (x < n+1) {if (divs.find(x) != divs.end()) d[x].pb(i); x += i;}
  }
}

set<int> get(int x) {
  if (!(dp[x].empty())) return dp[x];

  dp[x].insert(x - 1);
  for (auto &y : d[x]) {
    for (auto &k : get(x/y)) {
      dp[x].insert(k + y - 1);
    }
  }
  return dp[x];
}

int main(){
  cin >> n;
  getd();
  set<int> ans = get(n);
  cout << ans.size() << endl;
  for (auto &i : ans) cout << i << " "; cout<<endl;
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:51:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   51 |   for (auto &i : ans) cout << i << " "; cout<<endl;
      |   ^~~
toy.cpp:51:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   51 |   for (auto &i : ans) cout << i << " "; cout<<endl;
      |                                         ^~~~

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