글 읽기 - [C++] 15% 시간초과입니다...

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

[C++] 15% 시간초과입니다...

25614번 - 자리 바꾸기

jemin0619 1년 전 0

순열 사이클 분할로 사이클을 나눈 뒤, 사이클에 속한 숫자들의 위치를 M%cycle_size 만큼 이동시켜주는 것으로 코드를 짜봤습니다. 어느 부분에서 시간초과가 나는 걸까요?

#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(NULL)->sync_with_stdio(false)
#define ll long long
vector<int> memo;
int mod(string X, int M){
 if(memo[M]!=-1) return memo[M];
 int ret = 0;
 for(char c : X){
 ret = (10*ret + (int)(c-'0'))%M;
 }
 return memo[M] = ret;
}
int main(){
 fastio;
 int N; string M; cin>>N>>M;
 memo.resize(N+3, -1);
 vector<int> V(N);
 vector<bool> vis(N, false);
 vector<int> ans(N);
 for(int i=0; i<N; i++){
 cin>>V[i]; --V[i];
 ans[i] = i;
 }
 for(int i=0; i<N; i++){
 if(vis[i]) continue;
 vector<int> group;
 vector<int> tmp(ans);
 for(int nxt=i; !vis[nxt]; nxt=V[nxt]){
 vis[nxt] = true;
 group.push_back(nxt);
 }
 int sz = group.size();
 int mv = mod(M, sz);
 for(int j=0; j<sz; j++){
 tmp[group[j]] = ans[group[(j+mv)%sz]];
 }
 ans = tmp;
 }
 for(int val : ans) cout<<val+1<<' ';
 return 0;
}

jemin0619 1년 전 0

아래 코드는 통과하는데 왜 이건 안될까요...

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio cin.tie(NULL)->sync_with_stdio(false)
int mod(string X, int M){
 int ret = 0;
 for(char c : X){
 ret = (10*ret + (int)(c-'0'))%M;
 }
 return ret;
}
int main(){
 fastio;
 string M;
 int N; cin>>N>>M;
 vector<int> V(N+1);
 vector<bool> vis(N+1);
 vector<int> Ans(N+1, -1);
 vector<int> memo(N, -1); //mod값 저장해둠
 for(int i=1;i<=N;i++) cin>>V[i];
 for(int i=1;i<=N;i++){
 if(Ans[i]!=-1) continue;
 int l = 0;
 for(int nxt=i; !vis[nxt]; nxt=V[nxt]){
 vis[nxt]=true;
 l++;
 }
 int move;
 if(memo[l]!=-1) move = memo[l];
 else move = memo[l] = mod(M, l);
 int next = i;
 for(int j=0; j<move; j++){
 next = V[next];
 }
 Ans[i] = next;
 int cur = V[i];
 int nxt = V[next];
 for(;Ans[cur]==-1;cur=V[cur],nxt=V[nxt]){
 Ans[cur] = nxt;
 }
 }
 for(int i=1;i<=N;i++) cout<<Ans[i]<<' ';
 return 0;
}

jemin0619 1년 전 0

tmp를 매 사이클마다 선언하는게 문제였네요. main 밑으로 빼니 통과되었습니다.

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

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

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

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

한국어 | English (Beta)

문제

문제

출처

ICPC

[C++] 15% 시간초과입니다...

jemin0619 1년 전 0

jemin0619 1년 전 0

jemin0619 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말