Submission #826135

#	Time	Username	Problem	Language	Result	Execution time	Memory
826135		dxz05	Toys (CEOI18_toy)	C++17	100 / 100	631 ms	20388 KiB

toy

//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2")

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

#define all(x) (x).begin(), (x).end()

vector<pair<int, int>> dp[1500];

int main(){
	ios_base::sync_with_stdio(false);
	
	int n;
	cin >> n;
	
	vector<int> divisors;
	for (int d = 1; d * d <= n; d++){
		if (n % d == 0){
			divisors.push_back(d);
			if (n != d * d) divisors.push_back(n / d);
		}
	}
	
	sort(all(divisors));
	
	int m = (int) divisors.size();
	
	dp[0].emplace_back(0, 0);
	
	for (int i = 1; i < m; i++){
		int d = divisors[i];
		
		vector<pair<int, int>> v;
		
		int k = m - 1;
		for (int j = 1; j <= i; j++){
			int x = divisors[j];
			if (d % x) continue;
			
			int _d = d / x;
			while (divisors[k] > _d) k--;
			
			for (auto [l, r] : dp[k]){
				v.emplace_back(l + x - 1, r + x - 1);
			}
		}
		
		sort(all(v));
		
		int m = (int) v.size();
		for (int j = 0; j < m;){
			int l = v[j].first, r = v[j].second;
			int k = j;
			while (k < m && v[k].first <= r + 1){
				l = min(l, v[k].first);
				r = max(r, v[k].second);
				k++;
			}
			dp[i].emplace_back(l, r);
			j = k;
		}
		
	}
	
	int ans = 0;
	for (auto [l, r] : dp[m - 1]){
		ans += r - l + 1;
	}
	
	cout << ans << endl;
	for (auto [l, r] : dp[m - 1]){
		while (l <= r){
			cout << l << ' ';
			l++;
		}
	}
	cout << endl;
	
    return 0;
}

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