Submission #168824

#	Time	Username	Problem	Language	Result	Execution time	Memory
168824		kostia244	Toys (CEOI18_toy)	C++17	0 / 100	230 ms	262148 KiB

toy

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,sse2,sse,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC comment("/STACK:26666666")
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
using vi = vector<int>;
const int mod = 1e9 + 7;
int n;
int cnt = 0, dcnt = 0, anscnt = 0;
bitset<1200200> *vis;//exact upper bound +1
bitset<6969569> *vis2;//exact upper bound +1
bitset<1000001> goods, goodb;
int ans[80808], go[10203];
int *a, *b, sz = 0;
int x, z, zz;
ll u;

__attribute__((always_inline)) void sset(int i) {
	if(i < 1000001)
		goods.set(i);
	else
		goodb.set(n/i);
}

__attribute__((always_inline)) bool gget(int i) {
	if(i < 1000001)
		return goods.test(i);
	else
		return goodb.test(n/i);
}
__attribute__((always_inline)) inline bool mark(int i, int cur) {
	x = 0;
	for(int z = 1<<10; z; z>>=1)
		if(x+z<dcnt&&go[x+z]<=i) x+=z;
	z = (3ll*cur + 1)%1002523;
	zz = (65ll*cur + 2)%6969569;
	if(vis[x][z]&&vis2[x][zz]) return false;
	vis[x][z] = 1;
	vis2[x][zz] = 1;
	return true;
}
__attribute__((always_inline)) inline void dfs(int i, int cur) {
	if(i>n) return;
	cnt++;
	if(i == n) {
		ans[anscnt++] = cur;
		return;
	}
	for(int k = 0; k < dcnt; k++) {
		u = i*1ll*go[k];
		if(u>n) break;
		if(gget(u)&&mark(u, cur+go[k]-1)){
		a[sz] = u;
		b[sz] = cur+go[k]-1;
		sz++;
		}
	}
}
__attribute__((always_inline)) void solve() {
	a[0] = 1;
	b[0] = 0;
	mark(1, 0);
	sz = 1;
	int i = 0;
	while(i < sz) {
		dfs(a[i], b[i]);
		i++;
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	a = new int[50000001];
	b = new int[50000001];
	vis = new bitset<1200200>[1345];
	vis2 = new bitset<6969569>[1345];
	cin >> n;
	ll tn = n;
	for(ll i = 1; i*i <= tn; i++) {
		if(tn%i) continue;
		if(i>1) {
		go[dcnt++] = i;
		sset(i);
		}
		if(i*i!=n)
			go[dcnt++] = n/i, sset(n/i);
	}
	sort(go, go+dcnt);
	solve();
//	cerr<< cnt << "\n";
	sort(ans, ans+anscnt);
	cout << anscnt << "\n";
	string s;
	for(int i = 0; i < anscnt; i++)
		s += to_string(ans[i]), s.pb(' ');
	cout << s;
}

Compilation message (stderr)

toy.cpp:4:0: warning: ignoring #pragma GCC comment [-Wunknown-pragmas]
 #pragma GCC comment("/STACK:26666666")
 
toy.cpp:66:37: warning: always_inline function might not be inlinable [-Wattributes]
 __attribute__((always_inline)) void solve() {
                                     ^~~~~
toy.cpp:32:37: warning: always_inline function might not be inlinable [-Wattributes]
 __attribute__((always_inline)) bool gget(int i) {
                                     ^~~~
toy.cpp:25:37: warning: always_inline function might not be inlinable [-Wattributes]
 __attribute__((always_inline)) void sset(int i) {
                                     ^~~~

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