QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#630690 | #3840. Pass the Ball! | karito# | Compile Error | / | / | C++20 | 3.4kb | 2024-10-11 20:00:53 | 2024-10-11 20:00:53 |
Judging History
This is the latest submission verdict.
- [2024-10-11 20:00:53]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-10-11 20:00:53]
- Submitted
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
namespace FFT{
const int MAXB=19;
const int MAXN=(1<<MAXB);
int pbd[MAXN];
int bit_rev(int x,int b)
{
int ans=0;
for(int i=0;i<b;i++)
{
ans=(ans<<1)|(x&1);
x>>1;
}
return ans;
}
int cmp_b;
bool bit_cmp(int x,int y)
{
return bit_rev(x,cmp_b)<bit_rev(y,cmp_b);
}
const double pi=acos(-1);
complex<double> w(int n,int m)
{
double phi=2*pi/n*m;
return complex<double>{cos(phi),sin(phi)};
}
void pre(int b)
{
int n=(1<<b);
for(int i=0;i<n;i++)
pbd[i]=(pbd[i>>1]>>1)|((i&1)<<(b-1));
}
void fft(vector<complex<double>>::iterator a,int b)
{
int n=(1<<b);
for(int i=0;i<n;i++)
if(i<pbd[i])
swap(a[i],a[pbd[i]]);
for(int i=1;i<=b;i++)
{
for(int j=0;j<n;j+=(1<<i))
{
int t=(1<<i),s=t>>1;
for(int k=0;k<s;k++)
{
auto a0=a[k+j],a1=a[k+j+s];
auto wi=w(t,k);
a[k+j]=a0+a1*wi;
a[k+j+s]=a0-a1*wi;
}
}
}
return;
}
void ifft(vector<complex<double>>::iterator a,int b)
{
fft(a,b);
int n=(1<<b);
reverse(a+1,a+n);
for(int i=0;i<n;i++)
a[i]/=n;
return;
}
}
using namespace FFT;
int a[MAXN];
int vis[MAXN];
vector<complex<double>>t[MAXN];
vector<long long>ans[MAXN];
int sza[MAXN];
int szcnt=0;
map<int,int> mp;
int cnt=0;
void dfs(int x){
if(vis[x]) return;
t[cnt].push_back(x);
vis[x]=1;
dfs(a[x]);
}
signed main(){
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
if(!vis[i]){
cnt++;
dfs(i);
int sz = t[cnt].size();
t[cnt+1] = t[cnt];
reverse(t[cnt+1].begin(),t[cnt+1].end());
int b = 1;
while((1<<b)<sz*2) b++;
pre(b);
t[cnt].resize(1<<(b));
t[cnt+1].resize(1<<(b));
// cout<<b<<" "<<sz<<endl;
// for(int i=0;i<sz;i++){
// cout<<t[cnt][i].real()<<" "<<t[cnt+1][i].real()<<endl;
// }
fft(t[cnt].begin(),b);
fft(t[cnt+1].begin(),b);
for(int i=0;i<(1<<(b));i++){
t[cnt][i]=t[cnt][i]*t[cnt+1][i];
}
ifft(t[cnt].begin(),b);
// cout<<endl;
// for(int i=0;i<1<<(b);i++){
// cout<<i<<" "<<t[cnt][i].real()<<endl;
// }
if(!mp.count(sz)){
szcnt++;
sza[szcnt]=sz;
mp[sz]=szcnt;
ans[szcnt].resize(sz);
}
int id=mp[sz];
ans[id][0]+=(long long)(t[cnt][sz-1].real()+0.5);
for(int j=1;j<sz;j++){
ans[id][j]+=(long long)(t[cnt][j-1].real()+0.5)+(long long)(t[cnt][sz-1+j].real()+0.5);
}
for(int i=0;i<(1<<(b));i++) pbd[i] = 0;
cnt++;
}
}
for(int i=1;i<=q;i++){
int k;
cin>>k;
ll res = 0;
for(int j=1;j<=szcnt;j++){
res += ans[j][k%(sza[j])];
}
// cout<<ans[2][k%3]<<endl;
cout<<res<<endl;
}
}
Details
answer.code: In function ‘int main()’: answer.code:150:9: error: ‘ll’ was not declared in this scope 150 | ll res = 0; | ^~ answer.code:152:13: error: ‘res’ was not declared in this scope 152 | res += ans[j][k%(sza[j])]; | ^~~ answer.code:156:15: error: ‘res’ was not declared in this scope 156 | cout<<res<<endl; | ^~~