辞書順に数を並べる

第１版

6m20.857s, -fopenmpで5m26.862sでした.

tyama_henae22.cpp

//https://qiita.com/Nabetani/items/99e38a39165e1905b415
//http://nabetani.sakura.ne.jp/hena/orde22numord/
#pragma GCC optimize("O3")
#pragma GCC target("avx")

#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

#if _OPENMP
#include <parallel/algorithm>
#endif

void convert(vector<pair<vector<char>,int>>&v,int i,int m,int b){
    vector<char>v0;
    int n=i+m;
    for(;n;){
        v0.push_back(n%b);
        n/=b;
    }
    reverse(v0.begin(),v0.end());
    v[i].first=v0;
    v[i].second=i+m;
}

int main(){
    int m,n,b,x;
    for(;~scanf("%d,%d,%d,%d",&m,&n,&b,&x);){
        int siz=n-m+1,i;
        vector<pair<vector<char>,int>>v(siz);
#pragma omp parallel for
        for(i=0;i<siz;i++){
            convert(v,i,m,b);
        }
#if _OPENMP
        __gnu_parallel::sort(
#else
        sort(
#endif
            v.begin(),v.end()
        );
        printf("%d\n",v[x-1].second);
        fflush(stdout);
    }
}

第２版

angelさんの答案を見て、ビット並列すべきと思い直した。OpenMPで73秒。

・変数kは、左埋めにするために掛けるべき数。
・例の10:3と100:9について、100:3と読み替えてもpairでのソートであれば問題ない。

tyama_henae22_mod.cpp

//https://qiita.com/Nabetani/items/99e38a39165e1905b415
//http://nabetani.sakura.ne.jp/hena/orde22numord/
#pragma GCC optimize("O3")
#pragma GCC target("avx")

#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

#if _OPENMP
#include <parallel/algorithm>
#endif

void convert(vector<pair<long long,int>>&v,int i,int m,int b,long long k){
    int n=i+m;
    for(;n;n/=b)k/=b;
    v[i].first=(i+m)*k;
    v[i].second=i+m;
}

int main(){
    int m,n,b,x;
    for(;~scanf("%d,%d,%d,%d",&m,&n,&b,&x);){
        int siz=n-m+1,i;
        long long k=1;
        for(;k<=n;k*=b);
        vector<pair<long long,int>>v(siz);
#pragma omp parallel for
        for(i=0;i<siz;i++){
            convert(v,i,m,b,k);
        }
#if _OPENMP
        __gnu_parallel::sort(
#else
        sort(
#endif
            v.begin(),v.end()
        );
        printf("%d\n",v[x-1].second);
        fflush(stdout);
    }
}