QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#660856#9356. LRU AlgorithmXG0000#TL 0ms6648kbC++141.1kb2024-10-20 13:39:582024-10-20 13:40:00

Judging History

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

  • [2024-10-20 13:40:00]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:6648kb
  • [2024-10-20 13:39:58]
  • 提交

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 ...

output:


result: