Submission #538000

#	Time	Username	Problem	Language	Result	Execution time	Memory
538000		jamielim	Toys (CEOI18_toy)	C++14	19 / 100	3 ms	860 KiB

toy

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

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

bool prime[100005];
int n;

int main(){
	prime[0]=0;prime[1]=0;
	for(int i=2;i<=100005;i++)prime[i]=1;
	for(int i=2;i<=100005;i++){
		if(prime[i]==0)continue;
		for(int j=2*i;j<=100005;j+=i)prime[j]=0;
	}
	scanf("%d",&n);
	vector<int> pfac;
	for(int i=2;i<=100005;i++){
		if(prime[i]==0)continue;
		while(n%i==0){
			pfac.pb(i);
			n/=i;
		}
	}
	if(pfac.empty())pfac.pb(n);
	vector<vector<vector<int> > > v[2];
	vector<int> t;
	vector<vector<int> > r; r.pb(t);
	v[1].pb(r);
	for(int i=0;i<SZ(pfac);i++){
		v[i&1].clear();
		for(int j=0;j<SZ(v[(i&1)^1]);j++){
			int m=SZ(v[(i&1)^1][j]);
			for(int k=0;k<m;k++){
				vector<vector<int> > newv=v[(i&1)^1][j];
				if(k==0||SZ(newv[k])+1<=SZ(newv[k-1])){
					newv[k].pb(pfac[i]);
					v[i&1].pb(newv);
				}
			}
			vector<vector<int> > newv=v[(i&1)^1][j];
			t.clear();t.pb(pfac[i]);newv.pb(t);v[i&1].pb(newv);
		}
	}
	set<ll> ans;
	int x=(SZ(pfac)&1)^1;
	for(int i=0;i<SZ(v[x]);i++){
		ll sum=0;
		for(int j=0;j<SZ(v[x][i]);j++){
			ll prod=1;
			for(int k=0;k<SZ(v[x][i][j]);k++){
				//printf("%d ",v[x][i][j][k]);
				prod*=(ll)v[x][i][j][k];
			}
			sum+=prod-1;
			//printf("\n");
		}
		ans.insert(sum);
		//printf("\n");
	}
	printf("%d\n",SZ(ans));
	for(ll i:ans)printf("%lld ",i);
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
toy.cpp:24:36: warning: iteration 100003 invokes undefined behavior [-Waggressive-loop-optimizations]
   24 |  for(int i=2;i<=100005;i++)prime[i]=1;
      |                            ~~~~~~~~^~
toy.cpp:24:15: note: within this loop
   24 |  for(int i=2;i<=100005;i++)prime[i]=1;
      |              ~^~~~~~~~
toy.cpp:26:13: warning: iteration 100003 invokes undefined behavior [-Waggressive-loop-optimizations]
   26 |   if(prime[i]==0)continue;
      |      ~~~~~~~^
toy.cpp:25:15: note: within this loop
   25 |  for(int i=2;i<=100005;i++){
      |              ~^~~~~~~~
toy.cpp:24:36: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset 100005 is out of the bounds [0, 100005] of object 'prime' with type 'bool [100005]' [-Warray-bounds]
   24 |  for(int i=2;i<=100005;i++)prime[i]=1;
      |                            ~~~~~~~~^~
toy.cpp:19:6: note: 'prime' declared here
   19 | bool prime[100005];
      |      ^~~~~

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