QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#660856 | #9356. LRU Algorithm | XG0000# | TL | 0ms | 6648kb | C++14 | 1.1kb | 2024-10-20 13:39:58 | 2024-10-20 13:40:00 |
Judging History
answer
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define ull unsigned long long
const int N=5010,P=10086001;
__gnu_pbds::gp_hash_table<ull,bool> H[N],H1[N];
vector<int> s;
int T,n,q,a[N];
int main(void)
{
cin.tie(0)->sync_with_stdio(0);
cin>>T;
while(T--)
{
s.clear();
for(int i=1;i<=n;i++) H[i].clear(),H1[i].clear();
cin>>n>>q;
for(int i=1,x;i<=n;i++)
{
cin>>x;
auto t=find(s.begin(),s.end(),x);
if(t!=s.end()) s.erase(t);
s.push_back(x);
ull hh=0;
for(int j=s.size()-1;j>=0;j--) hh=hh*P+s[j],H[s.size()-j].insert({hh,1});
H1[s.size()].insert({hh,1});
}
//for(int i=1;i<=n;i++) sort(H[i].begin(),H[i].end()),sort(H1[i].begin(),H1[i].end());
while(q--)
{
int m,len;
bool flag=0;
ull hh=0;
cin>>m;len=m;
for(int x;m--;)
{
cin>>x;
if(!x) {len--;flag=1;continue;}
hh=hh*P+x;
}
if(flag)
{
if(H1[len].find(hh)!=H1[len].end()) cout<<"Yes\n";
else cout<<"No\n";
}
else
{
if(H[len].find(hh)!=H[len].end()) cout<<"Yes\n";
else cout<<"No\n";
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6648kb
input:
1 7 5 4 3 4 2 3 1 4 1 4 2 2 3 3 3 2 1 4 4 1 3 2 4 3 4 0 0
output:
Yes No No Yes Yes
result:
ok 5 lines
Test #2:
score: -100
Time Limit Exceeded
input:
105 50 10 23 30 34 20 27 11 21 29 12 7 21 42 45 48 8 15 6 16 19 35 16 14 29 11 31 18 22 4 45 22 14 4 13 40 43 48 27 15 15 15 15 10 15 11 31 37 34 34 50 14 1 25 2 23 6 3 29 21 11 4 12 29 18 39 5 29 21 11 27 20 6 21 10 9 3 34 14 7 49 36 36 43 50 50 35 8 12 29 21 11 27 20 34 30 9 11 27 20 34 30 23 0 0 ...