QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#627927	#9356. LRU Algorithm	guodong^#	WA	956ms	271296kb	C++17	1.7kb	2024-10-10 17:41:18	2024-10-10 17:41:18

Judging History

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

[2024-10-10 17:41:18]
评测

测评结果：WA
用时：956ms
内存：271296kb

查看

[2024-10-10 17:41:18]
提交

answer

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long 
using namespace std;
#define For(i,a,b) for(int i = a; i <= b; ++i)
#define push_back emplace_back
#define mp make_pair
inline int read(){
	int x=0;
	bool f=false;
	char ch=getchar();
	while(!isdigit(ch))f=ch=='-',ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return f?-x:x;
}
int T = 0;
const int mod = 1e17 + 3;
const int base = 13;
int mul(int x,int y){
	int t = x * y - (1.L) * (x * y / mod) * mod;
	if(t < 0) return t + mod;
	return t;
}
void Mod(int &x){
	if(x >= mod) 
		x -= mod;
}
signed main(){
#ifdef NICEGUODONG
	freopen("data.in","r",stdin);
#endif
	int T;
	T =read();
	while(T--){
		int n,q;
		n = read() ,q = read();
		vector<int> a;
#define M asdfa
		vector<vector<int>> h(n + 2);
		For(i,1,n){
			int x;
			x = read();
			++x;
			a.push_back(x);
			int hashsum = 0,cur = 1,cnt = 0;
			vector<int> vis(n + 1);
			for(int j = a.size() - 1; j >= 0; --j){
				if(vis[a[j]]) continue;
				++cnt;
				vis[a[j]] = 1;	
				hashsum += mul(cur,a[j]);
				Mod(hashsum);
				h[cnt].push_back(hashsum);
				cur = mul(cur,base);
			}
			while(cnt < n){
				hashsum += cur;
				Mod(hashsum);
				cur = mul(cur,base);
				++cnt;
				h[cnt].push_back(hashsum);
			}
		}
		for(int i = 1; i <= q; ++i){
			int r;
			r = read();
			int hashsum = 0,cur = 1;
			for(int i = 1; i <= r; ++i){
				int x;
				x = read();
				++x;
				hashsum += mul(cur , x);
				Mod(hashsum);
				cur = mul(cur , base);
			}
			int flag = 0;
			for(auto &x : h[r]){
				if(x == hashsum){
					flag = 1;
					break;
				}
			}
			if(flag){
				puts("Yes");
			}
			else 
				puts("No");
		}
	}

}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3560kb

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

Wrong Answer

time: 956ms

memory: 271296kb

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:

No
No
Yes
No
Yes
No
No
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
No
No
No
Yes
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
No
No
Yes
Yes
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
Yes
Yes
Yes
No
No
Yes
No
No
No
Yes
Yes
Yes
Yes
No
No
Yes
No
No
No
Yes
No
Yes
No
Yes
No
Yes
No
No
No
Yes
Yes
Yes
No
No
No
No
No
No
Yes...

result:

wrong answer 44th lines differ - expected: 'Yes', found: 'No'