QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#661615 | #9349. Exchanging Gifts | ganking# | RE | 0ms | 0kb | C++23 | 2.8kb | 2024-10-20 17:07:51 | 2024-10-20 17:07:53 |
answer
#include<bits/stdc++.h>
#define ll long long
#define db long double
#define mk make_pair
#define eb emplace_back
#define pi pair<ll,ll>
#define fo(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define fd(i,a,b) for(ll (i)=(a);(i)>=(b);(i)--)
using namespace std;
const int N=1e4+10;
const ll mo1=1e9+7;
const ll mo2=1e9+9;
const ll P=131;
const ll Q=13331;
ll f,g,pp[N],qq[N];
// queue<int>q[2];
int b[2][N];
unordered_map<ll,int> h[N],o[N];
int n,k,val;
int a[N];
int tmp,len;
int las;
void R(int &x){
int t=0;
char ch;
for (ch=getchar();!('0'<=ch && ch<='9');ch=getchar());
for (;('0'<=ch && ch<='9');ch=getchar()) t=t*10+ch-'0';
x=t;
}
void solve(){
R(n); R(k);
fo(i,1,n) h[i].clear(),o[i].clear();
fo(i,1,n) R(a[i]);
fo(i,1,n)b[0][i]=b[1][i]=0;
// fo(i,1,n)q[0].push(0);
las=0;
fo(i,1,n)
{
len=0;
// while(!q[(i)%2].empty())q[(i)%2].pop();
// q[i%2].push(a[i]);
b[i%2][1]=a[i];
tmp=a[i];
len=1;
f=tmp+1;
g=tmp+1;
val=rand()+1;
h[len][f]=val;
o[len][g]=val;
if(len==n) {
continue;
}
fo(j,1,n)
{
if(b[(i+1)%2][j]==a[i])continue;
len++;
tmp=b[(i+1)%2][j];
b[i%2][len]=tmp;
f=(f*P%mo1+(tmp+1))%mo1;
g=(g*Q%mo2+(tmp+1))%mo2;
val=rand()+1;
h[len][f]=val;
o[len][g]=val;
if(len==n)break;
}
// while(!q[(i+1)%2].empty())
// {
// tmp=q[(i+1)%2].front();
// q[(i+1)%2].pop();
// if(tmp==a[i])continue;
// q[i%2].push(tmp);
// len++;
// f=(f*P%mo1+(tmp+1))%mo1;
// g=(g*Q%mo2+(tmp+1))%mo2;
// val=rand()+1;
// h[len][f]=val;
// o[len][g]=val;
// if(len==n)break;
//tmp len
// }
}
int l,x;
while (k--) {
R(l);
f=g=0;
fo(i,1,l) {
R(x);
f=(f*P%mo1+(x+1))%mo1;
g=(g*Q%mo2+(x+1))%mo2;
}
if (h[l][f]==o[l][g] && h[l][f]!=0) puts("Yes");
else puts("No");
}
}
int main(){
freopen("data.in","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
srand(time(NULL));
cout<<4<<"\n";
fo(T,1,4) {
n=5000; k=5000;
cout<<n<<" "<<k<<"\n";
fo(i,1,n) cout<<rand()%n+1<<" ";
cout<<"\n";
fo(i,1,k) {
int l=rand()%5+1;
cout<<l<<" ";
fo(j,1,l) cout<<rand()%n+1<<" ";
cout<<"\n";
}
cout<<"\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
2 1 1 5 3 3 2 1 3 3 1 3 3 3 2 1 4 2 2 3 3 2 1 2