QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#628465#7723. Hash ServerAfterlife#0 173ms3852kbC++204.0kb2024-10-10 20:25:182024-10-10 20:25:19

Judging History

你现在查看的是最新测评结果

  • [2024-10-10 20:25:19]
  • 评测
  • 测评结果:0
  • 用时:173ms
  • 内存:3852kb
  • [2024-10-10 20:25:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=111,P=141167095653376ll;

int ty;

mt19937 rng(58);

int n=10;

vector<int> g10()
{
    int k=rng()%24+1;
    vector<int> v;
    v.push_back(k);
    v.push_back(k+1);
    v.push_back(k+2);
    set<int> s({k,k+1,k+2});
    for(int i=1;i<=7;i++)
    {
        int x;
        do {
            x=rng()%26+1;
        }while(s.count(x));
        v.push_back(x);
        s.insert(x);
    }
    return v;
}

int A[]={71, 67, 61, 59, 53, 47, 43, 41, 37, 31}, K[] = {29, 23, 19, 17, 13, 11, 7, 5, 3, 2}, X = 73;

string ask(string s)
{
    cout<<s<<endl;
    string r;
    cin>>r;
    return r;
    // int H=0;
    // for(int i=0;i<n;i++)
    // {
    //     int c=s[i]-'a'+1;
    //     int sk=1;
    //     for(int j=0;j<K[i];j++)
    //         sk=sk*X%P;
    //     sk=sk*c%P;
    //     sk=sk*(c+A[i])%P;
    //     H=(H+sk)%P;
    // }
    // string ans;
    // while(H)
    // {
    //     ans+=(H%26+'a');
    //     H/=26;
    // }
    // reverse(ans.begin(),ans.end());
    // r=ans;
    // cout<<ans<<endl;
    // return r;
}

signed main()
{
    cin>>ty;
    if(ty==1)
    {
        for(int i=0;i<10;i++)
        {
            //generate string
            string s;
            for(int j=0;j<10;j++)
            {
                s+=(char)(rng()%26+'a');
            }
            vector<int> v=g10();
            for(auto x:v)
            {
                s[i]=x+'a'-1;
                ask(s);
            }
        }
        cout<<"done"<<endl;
        return 0;
    }
    else
    {
        int m;
        cin>>m;
        vector<int> sv(m);
        for(int i=0;i<m;i++)
        {
            string u;
            cin>>u;
            for(auto x:u)
                sv[i]=sv[i]*26+x-'a';
        }
        vector<int> k2(10),a1(10);
        for(int i=0;i<10;i++)
        {
            m=sv.size();
            unordered_set<int> mp(sv.begin(),sv.end());
            string s;
            for(int j=0;j<10;j++)
                s+=(char)(rng()%26+'a');
            vector<int> v=g10();
            int p=v[0];
            int B=0;
            for(int a=0;a<m;a++)
                for(int b=0;b<m;b++)
                    for(int c=0;c<m;c++)
                    {
                        if(a==b||b==c||c==a)
                            continue;
                        int k2t=((sv[c]-2*sv[b]+sv[a])%P+P)%P;
                        int a1t=((sv[b]-sv[a]+P)%P-p*k2t%P+P)%P;
                        int bs=(sv[a]-a1t*p%P-(p*p-p)/2*k2t)%P;
                        bs=(bs%P+P)%P;
                        int ok=1;
                        for(auto c:v)
                        {
                            int q=(bs+(c*c-c)/2*k2t+a1t*c)%P;
                            if(!mp.count(q))
                            {
                                ok=0;
                                break;
                            }
                        }
                        if(ok)
                            k2[i]=k2t,a1[i]=a1t,B=bs;
                    }
            int bs=B,k2t=k2[i],a1t=a1[i];
            unordered_set<int> era;
            for(auto c:v)
            {
                int q=(bs+(c*c-c)/2*k2t+a1t*c)%P;
                era.insert(q);
            }
            vector<int> nsv;
            for(auto x:sv)
                if(!era.count(x))
                    nsv.push_back(x);
            sv.swap(nsv);
        }
        int Q=100;
        while(Q--)
        {
            string s;
            cin>>s;
            int H=0;
            for(int i=0;i<10;i++)
            {
                int c=s[i]-'a'+1;
                H=(H+c*a1[i]+(c*c-c)/2*k2[i])%P;
            }
            string ans;
            while(H)
            {
                ans+=(H%26+'a');
                H/=26;
            }
            reverse(ans.begin(),ans.end());
            cout<<ans<<endl;
        }
    }
}

详细

Test #1:

score: 100
Accepted
time: 165ms
memory: 3612kb

input:

1
vqtoooowzq
mlsrtdhzkq
drxczvcfxg
ntgkfbphiq
egsvdrrdfm
ackierpmcu
xqxbodslgo
kdwoldxkoq
bcptzmxwai
rtvobciieg
xisyfvwdng
vfkfzfwgoq
ywueedtuck
vnnagciyfc
srftkcwtoa
cxqjqtklmk
qefblczbca
fgugxztkyg
gtlzvmkphq
lvgbrqvsbo
htzdfoamqa
xpuhbhdtfq
ogxztjibzq
hzaggldsok
uapbnggyfk
vxumtbrtym
lcupdekgtm
o...

output:

cytdenncjh
dytdenncjh
eytdenncjh
pytdenncjh
sytdenncjh
uytdenncjh
wytdenncjh
qytdenncjh
mytdenncjh
oytdenncjh
sfclaiyfdm
sgclaiyfdm
shclaiyfdm
swclaiyfdm
skclaiyfdm
spclaiyfdm
szclaiyfdm
seclaiyfdm
sqclaiyfdm
sbclaiyfdm
tqtggbpmpz
tquggbpmpz
tqvggbpmpz
tqnggbpmpz
tqcggbpmpz
tqdggbpmpz
tqzggbpmpz
tql...

input:

2
100
htzdfoamqa
hrqozmhbtm
ogxztjibzq
akcvjotdek
qhwzeasfmk
iqaccvmxdg
bcptzmxwai
hrqpqoqsnw
lvgbrqvsbo
qxkpcawfsm
hrqqpudlpy
eqagmbyhxk
srftkcwtoa
vabuuhncni
ijtmhyoaak
qjjdfpukaa
hrqpbcvtfc
drxczvcfxg
fpoztcvguw
xnxgguvrwq
qxkpcaihcg
dzkrokzywa
hcohiqnfsw
xnanwjjkgq
qxkpckvdxq
lqtzlimtey
xqxbodsl...

output:

wilyevxwyy
gcfffvmuie
dhfvcyssbs
nxntwfpqfo
lzdblqdots
xlzrxeinse
wkdrewenay
itozirrmua
iohqiqvmxk
vuhqetqnlc
wloyxacojc
kodqlkfprk
mbzqvxzrka
bbdacpktmy
dlnsfkmwae
thftejfyxs
wofczlqcfo
nglvqrrfxs
rjzxebjkae
iyvhnosomy
nyyatfstka
gkicvajyrk
mgznsysejc
foyhnarklc
miekdghqxk
gmrvppoxua
wilyevxwyy
gcf...

result:

ok 100 lines

Test #2:

score: 0
Wrong Answer
time: 173ms
memory: 3852kb

input:

1
cquszbdfgu
enigiwknjc
hfduwuptjy
mvrxflocau
awghzqaryi
fqmuyyysgs
nrzmotokjg
zjfzqsujkc
gexwwhitqc
bdlvyhfsqa
kpryebzhdg
wlohzkzgoq
orkijxmfyo
odlchgypya
dqwfcdzdto
ahrkoplyzi
ekgreoylfg
fdvexwmhqk
xzkefhlxwc
bccusazivc
ysxbfvwcll
ugxjhxsovb
pqxrrfxxdf
wgvkpnuzbb
zatkmyfdoj
xetnvwhgwv
vqzbwydpvf
c...

output:

cytdenncjh
dytdenncjh
eytdenncjh
pytdenncjh
sytdenncjh
uytdenncjh
wytdenncjh
qytdenncjh
mytdenncjh
oytdenncjh
sfclaiyfdm
sgclaiyfdm
shclaiyfdm
swclaiyfdm
skclaiyfdm
spclaiyfdm
szclaiyfdm
seclaiyfdm
sqclaiyfdm
sbclaiyfdm
tqtggbpmpz
tquggbpmpz
tqvggbpmpz
tqnggbpmpz
tqcggbpmpz
tqdggbpmpz
tqzggbpmpz
tql...

input:

2
100
qyiqwmcuwk
dtwmacuaql
mvrxflocau
mwodqiijro
cebjhfdbkq
nrzmotokjg
gexwwhitqc
ysxbfvwcll
xvqlffhlne
hhekewuhuu
hiryortfmm
cpaawhykrs
fqmuyyysgs
rktconlpnf
werblkdgco
ugxjhxsovb
wgvkpnuzbb
vqzbwydpvf
mixfjkptcl
kgkgzcumya
ftpslrbxta
hbywldzvhq
cquszbdfgu
wlohzkzgoq
theksesxln
kzqdcczitv
jinimdnz...

output:

jmbofxzrbe
nujgisbzwd
xtmlblrkrj
ltomppcyts
cfxbkoufrf
oilrvwyei
yqedatllin
hjrimolkog
cjgczxjeat
tkysttetjy
zbusszevpq
cnnhdwnbat
tylgxmebld
rgtatequfy
uavxkvdwyt
yighoklain
sqggwlaed
olasnaaqlk
onzxebwutp
ordapmpoxl
ppxnjaclus
zcyepvbshv
dbvukzichf
zxbcahmtlq
itfekgedcw
xyzjkaiuiw
xyrqvmaiyo
ogkmt...

result:

wrong answer 6th lines differ - expected: 'aoilrvwyei', found: 'oilrvwyei'