QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#627847#9356. LRU Algorithmguodong#TL 0ms3600kbC++172.3kb2024-10-10 17:21:332024-10-10 17:21:34

Judging History

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

  • [2024-10-10 17:21:34]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3600kb
  • [2024-10-10 17:21:33]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long 
using namespace std;
#define For(i,a,b) for(int i = a; i <= b; ++i)
#define pb push_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;
}
const int N = 5050;
const int mod = 1e18 + 3;
const int base = 13;
const int M = 262143;
int T = 0;
struct E{int v; E * nxt;} *g[M+1],pool[N * N + 2],*cur = pool, *p;
struct hashMap{
		int vis[M + 1];
		void ins(int v){
			int u = v & M;
			if(vis[u] < T) vis[u] = T ,g[u] = NULL;
			for(p = g[u]; p ; p = p -> nxt)
				if(p -> v == v) 
					return;
			p = cur ++;
			p -> v = v;
			p -> nxt = g[u];
			g[u] = p;

		}
		int ask(int v){
			int u = v & M;
			if(vis[u] < T) return 0;
			for(p = g[u] ; p ; p = p -> nxt) if(p -> v == v) return 1;
			return 0;
		}
		void init(){
			T++;
			cur = pool;
		}
		
};
int mul(int x,int y){
	int t = x * y - (1.L) * (x * y / mod);
	return (t % mod + mod) % mod;
}

signed main(){
#ifdef NICEGUODONG
	freopen("data.in","r",stdin);
#endif
	int T;
	T =read();
	while(T--){
		int n,q;
		hashMap m;
		m.init();
		n = read() ,q = read();
		vector<int> a;
#define M asdfa
		unordered_map<int,bool> M;
		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]);
				hashsum %= mod;
				h[cnt].push_back(hashsum);
				//m.ins(hashsum);
				M[hashsum] = true;
				cur = mul(cur,base);
			}
			while(cnt < n){
				hashsum += cur;
				hashsum %= mod;
			//	m.ins(hashsum);
				M[hashsum] = true;
				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);
				hashsum %= mod;
				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");
		}
	}

}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3600kb

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: