QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#661298 | #9356. LRU Algorithm | ganking# | TL | 2ms | 8932kb | C++20 | 1.8kb | 2024-10-20 15:42:02 | 2024-10-20 15:42:08 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define db long double
#define mk make_pair
#define eb emplace_back
#define pi pair<ll,ll>
#define fo(i,a,b) for(ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,a,b) for(ll (i)=(a);(i)>=(b);(i)--)
using namespace std;
const int N=1e5+10;
const ll mo1=1e9+7;
const ll mo2=1e9+9;
const ll P=131;
const ll Q=13331;
ll f,g,pp[N],qq[N];
queue<int>q[2];
map<pi,bool> h[N];
int n,k;
int a[N];
int tmp,len;
void solve(){
cin>>n>>k;
fo(i,1,n) h[i].clear();
fo(i,1,n)cin>>a[i];
while(!q[0].empty())q[0].pop();
while(!q[1].empty())q[1].pop();
fo(i,1,n)q[0].push(0);
fo(i,1,n)
{
while(!q[(i)%2].empty())q[(i)%2].pop();
q[i%2].push(a[i]);
tmp=a[i];
len=1;
f=tmp+1;
g=tmp+1;
h[len][mk(f,g)]=1;
if(len==n) {
continue;
}
while(!q[(i+1)%2].empty())
{
tmp=q[(i+1)%2].front();
q[(i+1)%2].pop();
if(tmp==a[i])continue;
q[i%2].push(tmp);
len++;
f=(f*P%mo1+(tmp+1))%mo1;
g=(g*Q%mo2+(tmp+1))%mo2;
h[len][mk(f,g)]=1;
if(len==n)break;
//tmp len
}
}
ll l,x;
while (k--) {
cin>>l;
f=g=0;
fo(i,1,l) {
cin>>x;
f=(f*P%mo1+(x+1))%mo1;
g=(g*Q%mo2+(x+1))%mo2;
}
if (h[l].find(mk(f,g))!=h[l].end()) cout<<"Yes"<<"\n";
else cout<<"No"<<"\n";
}
}
int main(){
pp[0]=qq[0]=1;
fo(i,1,5005) {
pp[i]=pp[i-1]*P%mo1;
qq[i]=qq[i-1]*Q%mo2;
}
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
cin>>T;
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8932kb
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 ...