oj.uz

답안 #538000

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
538000 2022-03-16T02:34:08 Z jamielim Toys (CEOI18_toy) C++14
19 / 100
 3 ms 860 KB 
#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

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.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Incorrect 3 ms 860 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Incorrect 3 ms 860 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Incorrect 3 ms 860 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Incorrect 3 ms 860 KB Output isn't correct
27 Halted 0 ms 0 KB -