글 읽기 - 3113번 양 질문입니다.

portableangel 9년 전 0

그냥 평범한 그리디 구현입니다.

MAX 인풋을 20회정도 만들어 넣어봤는데 오류를 찾지 못해서 질문드립니다.

어디를 고쳐야 하는 건가요?ㅠㅠ

#include <stdio.h>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

class p {
public:
	multiset<int> fac;
	int dn, m, idx;
	void setp() {
		scanf("%d",&m);
		int k=2;
		while(k*k<=m) {
			while(m%k==0) {
				fac.insert(k);
				m/=k;
			}
			k++;
		}
		if(m>1) fac.insert(m);
	}
	int getd() {
		if(fac.empty()) return -1;
		multiset<int>::iterator it=fac.begin();
		return *it;
	}
	void setd(int k) {
		dn=fac.count(k);
	}
	bool remd(int k) {
		if(fac.count(k)) {
			fac.erase(fac.find(k));
			return true;
		}
		return false;
	}
	bool has(int k) {
		return fac.count(k);
	}
};

p list[50];

bool cmp(const p &i, const p &j) {
	return i.dn!=j.dn?i.dn>j.dn:i.idx<j.idx;
}

bool cmpinit(const p &i, const p &j) {
	return i.idx<j.idx;
}

int main() {
	int n, m;
	scanf("%d",&n);
	for(int i=0;i<n;i++) {
		list[i].setp();
		list[i].idx=i+1;
	}
	scanf("%d",&m);

	while(1) {
		sort(list,list+n,cmpinit);
		int f=-1;
		for(int i=0;i<n;i++) {
			if(list[i].getd()>0) {
				f=list[i].getd();
				printf("ENTER %d\n",f);
				break;
			}
		}
		if(f<0) return 0;

		while(1) {
			bool facf=false;
			for(int i=0;i<n;i++) {
				if(list[i].has(f)) {
					facf=true;
					break;
				}
			}
			if(!facf) break;

			for(int i=0;i<n;i++)
				list[i].setd(f);
			sort(list,list+n,cmp);
			printf("CLONE ");
			for(int i=0,c=0;i<n&&c<m;i++) {
				if(list[i].remd(f)) {
					c++;
					printf("%d ",list[i].idx);
				}
			}
			puts("");
		}
	}
}

portableangel 9년 전 0

@baekjoon

테스트 케이스 또는 스페셜 저지 확인 부탁드립니다. ㅠㅠ

baekjoon 9년 전 1

재채점했습니다.

스페셜 저지 구현에 실수가 있었네요 ㅠㅠ

portableangel 9년 전 0

감사합니다! 결국 12간지 문제집 클리어했네요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

3113번 양 질문입니다.

portableangel 9년 전 0

portableangel 9년 전 0

baekjoon 9년 전 1

portableangel 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말