22863 c++

원래 티스토리를 잘 사용하지 않고 있었으나

이 알고리즘에서 틀린 부분이 어디있는지 몰라 고생 중이기에 기록으로 남기고자 포스팅한다.

 

<순열사이클분할 - 수정 전>

#include<iostream>
#include<vector>
using namespace std;
int N, K;
vector<int> S(1000001);
vector<int> D(1000001);
vector<vector<int> >cycles;
vector<bool> check(1000001);
int cnt = -1;
void dfs(int i){
    check[i] = true;
    cycles[cnt].push_back(i);
    if(!check[D[i]]) dfs(D[i]);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>N>>K;
    for(int i =1; i<=N; ++i){
        cin>>S[i];
    }
    for(int i =1; i<=N; ++i){
        cin>>D[i];
    }
    for(int i = 1; i<=N; ++i){
        if(!check[i]){
            cycles.push_back(vector<int>());
            cnt++;
            dfs(i);
        }
    }
    vector<long long> result(1000001);
    for(auto cycle : cycles){
        for(int i = 0; i<cycle.size(); ++i){
            result[cycle[(i+K)%cycle.size()]] = S[cycle[i]];
        }
    }
    for(int i =1; i<=N; ++i){
        cout<<result[i]<<' ';
    }
}

<sparse table - 수정 전>

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
int N;
long long K;
vector<int> S(1000001);
int spt[50][1000001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    for (int i = 1; i <= N; ++i) cin >> S[i];
    for (int i = 1; i <= N; ++i) cin >> spt[0][i];
    for (int i = 1; i <= 49; ++i){
        for (int j = 1; j <= N; ++j){
            spt[i][j] = spt[i - 1][spt[i - 1][j]];
        }
    }
    vector<int> result(N + 1);
    for (int i = 1; i <= N; ++i){
        int start = i;
        long long cycle = K;
        for (int j = 50; j >= 0; --j){
            if ((1<<j) <= cycle){
                start = spt[j][start];
                cycle -= (1<<j);
            }
        }
        result[start] = S[i];
    }
    for (int i = 1; i <= N; ++i){
        cout << result[i] << ' ';
    }
}

 

<순열사이클분할>

틀린 점 : K의 타입 지정 실수 int -> long long

 

 

<sparse table>

틀린 점 : 시간 초과

고친 부분 : sparse table을 다 채우기 보다는 K에 맞는 범위까지만 채웠다.

log2(K)까지만 채움

 

틀린 점 : 시프트연산의 범위

고친 부분 : 시프트 연산을 할 때 보통 (1<<n)이런 형식으로 사용하는데 여기서 1은 암묵적으로 int 타입(32비트)이므로 시프트 연산 역시 32번 하게 되면 0으로 없어져버린다. 그러므로 32번 이상 시프트 연산을 할 경우에는 1을 long long 타입으로 미리 지정해줘야 한다.

long long one = 1;

(one<<n); 이런 방법으로 고쳤더니 해결되었다.

 

 

<순열사이클분할 - 수정 후>

#include<iostream>
#include<vector>
using namespace std;
int N;
long long K;
vector<int> S(1000001);
vector<int> D(1000001);
vector<vector<int> >cycles;
vector<bool> check(1000001);
int cnt = -1;
void dfs(int i){
    check[i] = true;
    cycles[cnt].push_back(i);
    if(!check[D[i]]) dfs(D[i]);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>N>>K;
    for(int i =1; i<=N; ++i){
        cin>>S[i];
    }
    for(int i =1; i<=N; ++i){
        cin>>D[i];
    }
    for(int i = 1; i<=N; ++i){
        if(!check[i]){
            cycles.push_back(vector<int>());
            cnt++;
            dfs(i);
        }
    }
    vector<int> result(1000001);
    for(auto cycle : cycles){
        for(int i = 0; i<cycle.size(); ++i){
            result[cycle[(i+K)%cycle.size()]] = S[cycle[i]];
        }
    }
    for(int i =1; i<=N; ++i){
        cout<<result[i]<<' ';
    }
}

 

<sparse table - 수정 후>

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
int N;
long long K;
vector<int> S(1000001);
int spt[50][1000001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    for (int i = 1; i <= N; ++i) cin >> S[i];
    for (int i = 1; i <= N; ++i) cin >> spt[0][i];
    for (int i = 1; i <= log2(K); ++i){
        for (int j = 1; j <= N; ++j){
            spt[i][j] = spt[i - 1][spt[i - 1][j]];
        }
    }
    vector<int> result(N + 1);
    for (int i = 1; i <= N; ++i){
        int start = i;
        long long cycle = K;
        for (int j = 50; j >= 0; --j){
            long long one = 1;
            one = (one<<j);
            if (one <= cycle){
                start = spt[j][start];
                cycle -= one;
            }
        }
        result[start] = S[i];
    }
    for (int i = 1; i <= N; ++i){
        cout << result[i] << ' ';
    }
}