More than 5 years have passed since last update.
第１版
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);
}
}
Register as a new user and use Qiita more conveniently
- You get articles that match your needs
- You can efficiently read back useful information
- You can use dark theme