QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #135756 | #6635. Strange Keyboard | PhantomThreshold | Compile Error | / | / | C++20 | 1.9kb | 2023-08-05 23:40:38 | 2023-08-05 23:40:42 |
Judging History
你现在查看的是最新测评结果
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-08-05 23:40:42]
- 评测
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [2023-08-05 23:40:38]
- 提交
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1010000;
const int maxt = 5050;
const int inf = 1e18;
int n,K;
int len[maxn],id[maxn];
signed rt,tr[maxn][26],fa[maxn],f[maxn],tot;
int newnode()
{
++tot;
for(int i=0;i<26;i++) tr[tot][i]=0;
fa[tot]=0;
f[tot]=inf;
return tot;
}
int dis[maxt],a[maxt];
vector<int>ai;
priority_queue< pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > >q;
string T; int tn;
int g[maxt];
signed main()
{
ios_base::sync_with_stdio(false);
int Tcase; cin>>Tcase;
while(Tcase--)
{
cin>>n>>K;
for(int i=0;i<K;i++) a[i]=inf;
tot=0;
rt=newnode();
for(int i=1;i<=n;i++)
{
string str; cin>>str;
len[i]=str.size();
a[len[i]%K]= min( a[len[i]%K], len[i]/K+1 );
int now=rt;
for(auto c:str)
{
int j=c-'a';
if(!tr[now][j])
{
tr[now][j]=newnode();
fa[tr[now][j]]=now;
}
now=tr[now][j];
}
id[i]=now;
}
cin>>T; tn=T.size();
ai.clear();
for(int k=0;k<K;k++) if(a[k]!=inf) ai.push_back(k);
sort(ai.begin(),ai.end());
for(int i=0;i<K;i++) dis[i]= inf;
dis[0]=0; q.push( make_pair( dis[0],0 ) );
while(!q.empty())
{
auto [D,i]= q.top(); q.pop();
if( D!=dis[i] ) continue;
for(auto k:ai)
{
int j= (i+k)%K, jc=D+a[k]+(i+k>=K);
if( dis[j]>jc )
{
dis[j]=jc;
q.push(make_pair(dis[j],j));
}
}
}
for(int i=1;i<=n;i++)
{
int l=0,x=id[i];
while(x!=rt)
{
f[x]=min(f[x], l/K+ ( l%K==0?0:dis[K-l%K]+1 ) );
x=fa[x]; l++;
}
}
for(int i=0;i<=tn;i++) g[i]=inf;
g[0]=0;
for(int i=0;i<tn;i++)
{
int now=rt;
for(int j=1;j<=tn-i;j++)
{
int c=T[i+j-1]-'a';
if(tr[now][c]==0) break;
now=tr[now][c];
g[i+j]=min(g[i+j],g[i]+1+f[now]);
}
}
cout<< (g[tn]==inf?-1:g[tn]) <<'\n';
}
return 0;
}
Details
answer.code: In function ‘long long int newnode()’:
answer.code:17:16: warning: overflow in conversion from ‘long long int’ to ‘int’ changes value from ‘1000000000000000000’ to ‘-1486618624’ [-Woverflow]
17 | f[tot]=inf;
| ^~~
answer.code: In function ‘int main()’:
answer.code:86:41: error: no matching function for call to ‘min(int&, long long int)’
86 | f[x]=min(f[x], l/K+ ( l%K==0?0:dis[K-l%K]+1 ) );
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
from /usr/include/c++/11/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)’
230 | min(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: template argument deduction/substitution failed:
answer.code:86:41: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
86 | f[x]=min(f[x], l/K+ ( l%K==0?0:dis[K-l%K]+1 ) );
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
from /usr/include/c++/11/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
from answer.code:1:
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)’
278 | min(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: template argument deduction/substitution failed:
answer.code:86:41: note: deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘long long int’)
86 | f[x]=min(f[x], l/K+ ( l%K==0?0:dis[K-l%K]+1 ) );
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)’
3449 | min(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: template argument deduction/substitution failed:
answer.code:86:41: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
86 | f[x]=min(f[x], l/K+ ( l%K==0?0:dis[K-l%K]+1 ) );
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from answer.code:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)’
3455 | min(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: template argument deduction/substitution failed:
answer.code:86:41: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
86 | f[x]=min(f[x], l/K+ ( l%K==0?0:dis[K-l%K]+1 ) );
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~