結果

問題 No.3015 アンチローリングハッシュ
ユーザー Lay_ecLay_ec
提出日時 2015-11-05 15:26:32
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 4,768 bytes
コンパイル時間 1,343 ms
コンパイル使用メモリ 105,380 KB
実行使用メモリ 13,760 KB
最終ジャッジ日時 2024-09-13 12:43:07
合計ジャッジ時間 4,985 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
13,760 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 TLE -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>
#include <sstream>
#include <map>
#include <queue>
#include <stack>

using namespace std;

typedef long double ld;

ld IP(vector<vector<ld> > &B1, int x, vector<vector<ld> > &B2, int y){
    ld res=0;
    for(int i=0;i<B1.size();i++) res+=(ld)B1[i][x]*(ld)B2[i][y];
    return res;
}

//https://en.wikipedia.org/wiki/Gram-Schmidt_process
vector<vector<ld> > GS(vector<vector<ld> > &Basis){
    //vector<vector<ld> > Basis_=Basis;
    
    const int n=Basis.size();
    vector<vector<ld> > Basis_(n,vector<ld>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) Basis_[i][j]=Basis[i][j];
    }
    
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            ld ip=IP(Basis,i,Basis_,j);
            ld ip2=IP(Basis_,j,Basis_,j);
            for(int k=0;k<n;k++) Basis_[k][i]-=ip/ip2*Basis_[k][j];
        }
    }
    
    return Basis_;
}

ld MU(vector<vector<ld> > &Basis,int x,vector<vector<ld> > &Basis_,int y){
    return IP(Basis,x,Basis_,y)/IP(Basis_,y,Basis_,y);
}

ld PI2(vector<vector<ld> > &Basis,vector<vector<ld> > &Basis_,int i,int x){

    const int n=Basis.size();
    vector<ld> pi(n,0);
        
    for(int j=i;j<n;j++){
        ld ip1=IP(Basis,x,Basis_,j);
        ld ip2=IP(Basis_,j,Basis_,j);
        
        for(int k=0;k<n;k++){
            pi[k]+=ip1/ip2*Basis_[k][j];
        }
    }
    
    ld res=0;
    for(int j=0;j<n;j++) res+=pi[j]*pi[j];
    return res;
    
}

vector<ld> LLL(vector<vector<ld> > Basis){
    const int n=Basis.size();
    const ld delta=1.0/4.0;
    vector<ld> svp(n);
        
    vector<vector<ld> > Basis_=GS(Basis);
    while(true){
        
/*
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++) cout<<Basis[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;
*/
        
        for(int i=0;i<n;i++){
            for(int j=i-1;j>=0;j--){
                ld c_ij=(ld)roundl(IP(Basis,i,Basis_,j)/IP(Basis_,j,Basis_,j));
                for(int k=0;k<n;k++) Basis[k][i]-=c_ij*Basis[k][j];
                Basis_=GS(Basis);
            }
        }
        
        bool cont=false;
        for(int i=0;i<n-1;i++){
            ld p1=PI2(Basis,Basis_,i,i);
            ld p2=PI2(Basis,Basis_,i,i+1);
            if(delta*p1>p2){
                for(int j=0;j<n;j++) swap(Basis[j][i],Basis[j][i+1]);
                Basis_=GS(Basis);
                cont=true;
                break;
            }	
        }
        
        if(cont) continue;
        else{
/*			
            cout<<"result"<<endl;
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    cout<<Basis[i][j]<<" ";
                }
                cout<<endl;
            }
*/
            for(int i=0;i<n;i++) svp[i]=Basis[i][0];
            return svp;
        }
        
                
    }
    
}

unsigned long long get_hash(string s, unsigned long long a, unsigned long long b){
    unsigned long long hash = 0;

    for(int i = 0; i < s.size(); i++){
        hash = (hash * a + s[i]) % b;
    }

    return hash;
}

int main(){
/*
    vector<vector<ll> > mat(4,vector<ll>(4));
    mat[0][0]=105;  mat[1][0]=821;  mat[2][0]=404; mat[3][0]=328;
    mat[0][1]=881;  mat[1][1]=667; mat[2][1]=644; mat[3][1]=927;
    mat[0][2]=181;  mat[1][2]=483; mat[2][2]=87; mat[3][2]=500;
    mat[0][3]=893;  mat[1][3]=834; mat[2][3]=732; mat[3][3]=441;
    LLL(mat);
*/
    

    ld p,b;
    cin>>p>>b;
	swap(p,b);
    vector<ld> tmp;
	vector<long long> coe;
    int n;
    for(n=4;;n+=4){
        //cout<<n<<endl;
		coe.resize(n);
        vector<vector<ld> > Basis(n,vector<ld>(n,0));
        for(int i=0;i<n-1;i++){
            Basis[i][i]=-b;
            Basis[i+1][i]=1;
        }
        Basis[0][n-1]=p;
        		
        tmp=LLL(Basis);
        reverse(tmp.begin(),tmp.end());
        for(int i=0;i<n;i++) coe[i]=(long long)tmp[i];
		
        bool ok=true;
        for(int i=0;i<n;i++) ok&=(abs(tmp[i])<=25.0);
        if(ok){
/*
            for(int i=0;i<n;i++) cout<<coe[i]<<" ";
            cout<<endl;
*/
            break;
        }
    }

    map<int,pair<char,char> > st;
    for(int i=-25;i<=25;i++){
        bool ok=false;
        for(char s='a';s<='z' && !ok;s++){
            for(char t='a';t<='z' && !ok;t++){
                if(s-t==i){
                    st[i]=make_pair(s,t);
                    ok=true;
                }
            }
        }
    }

    string s,t;
    for(int i=0;i<n;i++){
        s+=st[coe[i]].first;
        t+=st[coe[i]].second;
    }
    cout<<s+"\n"<<t<<endl;
    //cout<<get_hash(s,b,p)<<endl;
    //cout<<get_hash(t,b,p)<<endl;

    return 0;

}
0