QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#627847 | #9356. LRU Algorithm | guodong# | TL | 0ms | 3600kb | C++17 | 2.3kb | 2024-10-10 17:21:33 | 2024-10-10 17:21:34 |
Judging History
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 ...