Submission #1201951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201951		pera	Toys (CEOI18_toy)	C++20	100 / 100	873 ms	109788 KiB

toy

#include<bits/stdc++.h>
using namespace std;
int main(){
   int n;
   cin >> n;
   vector<int> d;
   for(int i = 1;i * i <= n;i ++){
      if(n % i == 0){
         d.emplace_back(i);
         if(i * i != n){
            d.emplace_back(n / i);
         }
      }
   }
   auto f = [&](int x){
      int l = 0;
      for(int bit = 20;bit >= 0;bit --){
         l += 1 << bit;
         if(l >= (int)d.size() || d[l] > x){
            l -= 1 << bit;
         }
      }
      return l;
   };
   sort(d.begin() , d.end());
   vector<vector<int>> dp((int)d.size());
   for(int i = 0;i < (int)d.size();i ++){
      dp[i].emplace_back(d[i] - 1);
      for(int v = 1;v * v <= d[i];v ++){
         if(d[i] % (v + 1) == 0){
            for(int a : dp[f(d[i] / (v + 1))]){
               dp[i].emplace_back(a + v);
            }
            if(v + 1 == d[i]){
               continue;
            }
            for(int a : dp[f(v + 1)]){
               dp[i].emplace_back(a + d[i] / (v + 1) - 1);
            }
         }
      }
      sort(dp[i].begin() , dp[i].end());
      dp[i].erase(unique(dp[i].begin() , dp[i].end()) , dp[i].end());
   }
   cout << (int)dp.back().size() << '\n';
   for(int x : dp.back()){
      cout << x << " ";
   }
}

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