QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#660764#9356. LRU AlgorithmXG0000#TL 0ms4488kbC++141.2kb2024-10-20 13:14:092024-10-20 13:14:09

Judging History

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

  • [2024-10-20 13:14:09]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:4488kb
  • [2024-10-20 13:14:09]
  • 提交

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;
}

詳細信息

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

output:


result: