글 읽기 - 다른풀이에 대한 질문

(追記) (追記ここまで)

다른풀이에 대한 질문

12792번 - 주작 주 주작

starttoday 9년 전 0

안녕하세요

대회 풀이에 나온 솔루션처럼 큰 소수를 출력 하지 않고,

사이클의 크기들의 최소공배수 + 1를 찍었는데 답이 틀렸다고 나옵니다.

위처럼 풀었을때 반례가 있을까요? 아니면 코딩실수인가요? 궁금합니다

#include<stdio.h>
int a[1000010];
bool v[1000010];
 
int gcd(int a, int b) {
 int t;
 if (a < b) {
 t=a;a=b;b=t;
 }
 while (b>0) {
 t=b;
 b=a%b;
 a=t;
 }
 return a;
}
 
int lcm(int a, int b) {
 return a / gcd(a, b) * b;
}
 
int main() {
 int n, i;
 scanf("%d", &n);
 for (i=0;i<n;i++) {
 scanf("%d", &a[i]);
 a[i]--;
 }
 
 int ans = 1;
 
 for (i=0;i<n;i++) {
 if (v[i]) continue;
 int s = i, cnt = 0;
 while (!v[s]) {
 v[s] = true;
 s = a[i];
 cnt++;
 }
 
 if (cnt == 1) {
 printf("-1\n");
 return 0;
 }
 ans = lcm(ans, cnt);
 }
 printf("%d\n", ans+1);
 return 0;
}

koosaga 9년 전 1

반례 데이터가 있습니다 (제가 넣었습니다).

저대로 하면 답의 크기가 기하급수적으로 커질 것입니다.

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC