QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#660764 | #9356. LRU Algorithm | XG0000# | TL | 0ms | 4488kb | C++14 | 1.2kb | 2024-10-20 13:14:09 | 2024-10-20 13:14:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=5010,P=13331;
unordered_map<ull,bool> H[N],H1[N];
vector<int> s;
int T,n,q,a[N];
bool find_site(vector<ull> &s,ull h)
{
auto t=lower_bound(s.begin(),s.end(),h);
if(t!=s.end() && (*t)==h) return 1;
return 0;
}
int main(void)
{
scanf("%d",&T);
while(T--)
{
for(int i=1;i<=n;i++) H[i].clear(),H1[i].clear();
scanf("%d%d",&n,&q);
for(int i=1,x;i<=n;i++)
{
scanf("%d",&x);
auto t=s.begin();
while(t!=s.end())
{
if((*t)==x) {s.erase(t);break;}
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][hh]=1;
H1[s.size()][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;
scanf("%d",&m);len=m;
while(m--)
{
int x;
scanf("%d",&x);
if(!x) {len--;flag=1;continue;}
hh=hh*P+x;
}
if(flag)
{
if(H1[len].count(hh)) puts("Yes");
else puts("No");
}
else
{
if(H[len].count(hh)) puts("Yes");
else puts("No");
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4488kb
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 ...