Submission #94423

#	Time	Username	Problem	Language	Result	Execution time	Memory
94423		Noam527	Toys (CEOI18_toy)	C++17	100 / 100	3448 ms	12232 KiB

toy

#include <bits/stdc++.h>
#include <unordered_set>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;

void debug(string names) {
	cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
	int pos = 0;
	for (; pos < names.size() && names[pos] != ' '  && names[pos] != ','; pos++)
		cout << names[pos];
	cout << ": " << par << "  ";
	while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
		pos++;
	}
	names.erase(names.begin(), names.begin() + pos);
	debug(names, left...);
}

int n;
vector<int> a;
unordered_set<int> s;

void calc(int ind, int left, int sum) {
	if (left == 1) {
		s.insert(sum);
		return;
	}
	if (ind == a.size() || left < a[ind]) return;
	calc(ind + 1, left, sum);
	while (left % a[ind] == 0) {
		left /= a[ind];
		sum += a[ind] - 1;
		calc(ind + 1, left, sum);
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	cin >> n;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			a.push_back(i);
			if (i != n / i) a.push_back(n / i);
		}
	}
	sort(a.begin(), a.end());
	a.push_back(n);

	s.reserve(1 << 20);
	calc(0, n, 0);
	vector<int> t;
	for (const auto &i : s) t.push_back(i);
	sort(t.begin(), t.end());
	cout << t.size() << '\n';
	for (const auto &i : t) cout << i << " "; cout << '\n';
}

Compilation message (stderr)

toy.cpp: In function 'void calc(int, int, int)':
toy.cpp:35:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (ind == a.size() || left < a[ind]) return;
      ~~~~^~~~~~~~~~~
toy.cpp: In function 'int main()':
toy.cpp:63:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (const auto &i : t) cout << i << " "; cout << '\n';
  ^~~
toy.cpp:63:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (const auto &i : t) cout << i << " "; cout << '\n';
                                            ^~~~

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