辞書順に数を並べる

第１版

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

tyama_henae22.cpp

Copied!

//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

Copied!

//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);
	}
}