Submission #826088

#	Time	Username	Problem	Language	Result	Execution time	Memory
826088		dxz05	Toys (CEOI18_toy)	C++17	100 / 100	1990 ms	31212 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()

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

void add_segment(int l, int r, set<pair<int, int>> &s){
	s.emplace(l, r);
	auto it = s.find(make_pair(l, r));
	
	if (next(it) != s.end()){
		auto nit = next(it);
		if (nit->first <= r + 1){
			l = min(l, nit->first);
			r = max(r, nit->second);
			s.erase(nit);
			s.erase(it);
			s.emplace(l, r);
			it = s.find(make_pair(l, r));
		}
	}
	
	if (it != s.begin()){
		auto pit = prev(it);
		if (pit->second >= l - 1){
			l = min(l, pit->first);
			r = max(r, pit->second);
			s.erase(it);
			s.erase(pit);
			s.emplace(l, r);
		}
	}
	
}

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();
	
	add_segment(0, 0, dp[0]);
	
	for (int i = 1; i < m; i++){
		int d = divisors[i];
		
		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]){
				add_segment(l + x - 1, r + x - 1, dp[i]);
			}
		}
	}
	
	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;
}

/*

735134400

*/

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