oj.uz

Submission #70518

# Submission time Handle Problem Language Result Execution time Memory
70518 2018-08-23T05:02:38 Z 윤교준(#2187) Toys (CEOI18_toy) C++11
0 / 100
 3 ms 544 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void f(vector<pii>&, int, int);
void g0(vector<pii>&, int, int, vector<int>&, int, int, int, int);
void g1(vector<pii>&, int, int, vector<int>&, int, int, vector<vector<pii>>&);

const bool debug = 0;
const int MAXX = 33005;

bitset<MAXX> isnp;

vector<vector<int>> PP;
vector<pii> PV;

vector<int> Ans;
int N;

void fact(vector<pii> &V, int N) {
	V.clear(); if(N < 2) return;
	if(!(N&1)) {
		for(V.eb(2, 0); !(N&1); V.back().second++, N >>= 1);
	}
	for(int i = 3; i*i <= N; i += 2) if(!isnp[i] && !(N%i)) {
		for(V.eb(i, 1), N /= i; !(N%i); V.back().second++, N /= i);
	}
	if(1 < N) V.eb(N, 1);
}

void g2(vector<pii> &G, int i, int n, vector<int> &VC, int j, int gn, vector<vector<pii>> &GC, int lft, int cnt, int ub) {
	if(debug) {
		printf("G2 : i=%d, n=%d, j=%d, gn=%d, left=%d, cnt=%d, ub=%d\n", i, n, j, gn, lft, cnt, ub);
	}

	if(!cnt || !lft) {
		g1(G, i, n, VC, j+1, gn, GC);
		return;
	}

	for(int x = (cnt + lft - 1 + lft) / (lft+1); x < ub; x++) {
		for(int c = max(1, cnt - x * lft + lft), cub = min(cnt/x, lft); c <= cub; c++) {
			if(debug) printf("TRY (%d,%d)\n", x, c);
			GC[j].eb(x, c);
			g2(G, i, n, VC, j, gn, GC, lft-c, cnt-x*c, x);
			GC[j].pop_back();
		}
	}
}

void g1(vector<pii> &G, int i, int n, vector<int> &VC, int j, int gn, vector<vector<pii>> &GC) {
	if(debug) {
		printf("G1 : i=%d, n=%d, j=%d, gn=%d : VC=", i, n, j, gn);
		for(int v : VC) printf("%d ", v);
		if(j < gn) {
			printf(": GC=");
			for(auto &v : GC[j]) printf("(%d,%d) ", v.first, v.second);
		}
		puts("");
	}

	if(j == gn) {
		vector<pii> NG;
		for(int k = 0; k < gn; k++) {
			int a, b; tie(a, b) = G[k];
			for(auto &v : GC[k]) {
				NG.eb(a * PP[i][v.first], v.second);
				b -= v.second;
			}
			if(b) NG.eb(a, b);
		}

		f(NG, i+1, n);
		return;
	}

	g2(G, i, n, VC, j, gn, GC, G[j].second, VC[j], 31);
}

void g0(vector<pii> &G, int i, int n, vector<int> &VC, int j, int gn, int p, int cnt) {
	if(debug) {
		printf("G0 : i=%d, n=%d, j=%d, gn=%d, p=%d, cnt=%d :: ", i, n, j, gn, p, cnt);
		for(auto &v : VC) printf("%d ", v);
		puts("");
	}

	if(!cnt) {
		vector<vector<pii>> GC(gn);
		g1(G, i, n, VC, 0, gn, GC);
		return;
	}

	if(j+1 == gn) {
		VC[j] = cnt;
		g0(G, i, n, VC, j+1, gn, p, 0);
		VC[j] = 0;
		return;
	}

	for(int k = 0; k <= cnt; k++) {
		VC[j] = k;
		g0(G, i, n, VC, j+1, gn, p, cnt-k);
	}
	VC[j] = 0;
}

void f(vector<pii> &G, int i, int n) {
	if(debug) {
		printf("F : i=%d, n=%d :: ", i, n);
		for(auto &v : G) printf("(%d,%d) ", v.first, v.second);
		puts("");
	}

	if(i == n) {
		int ret = -31;
		for(auto &v : G)
			ret += v.first * v.second;
		Ans.eb(ret);
		return;
	}

	int p, cnt; tie(p, cnt) = PV[i];
	int gn = sz(G);
	vector<int> VC(gn, 0);

	g0(G, i, n, VC, 0, gn, p, cnt);
}

int main() {
	isnp[0] = isnp[1] = true;
	for(int i = 4; i < MAXX; i += 2) isnp[i] = true;
	for(int i = 3; i*i < MAXX; i += 2) if(!isnp[i])
		for(int j = i*i; j < MAXX; j += i<<1) isnp[j] = true;
	
	cin >> N;
	if(1 == N) {
		puts("1\n0");
		return 0;
	}
	fact(PV, N);
	sort(allv(PV), [&](pii a, pii b) { return a.second > b.second; });

	for(auto &v : PV) {
		int p, cnt; tie(p, cnt) = v;
		PP.eb(vector<int>(1, 1));
		for(int i = 0; i < cnt; i++)
			PP.back().eb(PP.back().back() * p);
	}

	{
		vector<pii> G(1, pii(1, 31));
		f(G, 0, sz(PV));
	}

	sorv(Ans); univ(Ans);
	printf("%d\n", sz(Ans));
	for(int v : Ans) printf("%d ", v);
	puts("");
	return 0;
}

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 3 ms 436 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 544 KB Output is correct
8 Incorrect 2 ms 544 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 3 ms 436 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 544 KB Output is correct
8 Incorrect 2 ms 544 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 3 ms 436 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 544 KB Output is correct
8 Incorrect 2 ms 544 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 3 ms 436 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 544 KB Output is correct
8 Incorrect 2 ms 544 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 436 KB Output is correct
4 Correct 3 ms 436 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 3 ms 544 KB Output is correct
8 Incorrect 2 ms 544 KB Output isn't correct
9 Halted 0 ms 0 KB -