結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
![]() |
提出日時 | 2021-01-08 15:18:21 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,094 bytes |
コンパイル時間 | 1,314 ms |
コンパイル使用メモリ | 110,608 KB |
実行使用メモリ | 47,556 KB |
最終ジャッジ日時 | 2024-11-15 20:22:21 |
合計ジャッジ時間 | 8,904 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 19 |
ソースコード
#include <fstream>#include <iostream>#include <algorithm>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <string>#include <sstream>#include <map>#include <set>#include <vector>#include <stack>#include <cmath>#include <queue>#include <random>#include <numeric>#include <complex>using namespace std;#define I_MAX 2147483647#define LL_MAX 9223372036854775807#define ll long long#define ld long doublestruct XX{int l;int r;int m;};class xxGreater {public:bool operator()(const XX& riLeft, const XX& riRight) const {//第2条件if((riLeft.r) == (riRight.r)){return riLeft.l < riRight.l;//<:昇順(小さいものから順番)、>:降順(大きいものから順番)//プライオリティキューの場合は > で、top()すると値の小さいものがとれる}//第1条件return (riLeft.r) < (riRight.r);}};//map<long long,long long> prime_f(long long n){// map<long long,long long>res;// for(int i=2;i*i<=n;i++){// while(n%i==0){// ++res[i];// n/=i;// }// }// if(n!=1)res[n]=1;// return res;//}//int n;////int dat[2*10000000];////int dat2[2*10000000];//int dat[10];//int dat2[10];////void init(int n_){// n=1;// while(n<n_)n*=2;// for(int i=0;i<2*n-1;i++){// dat[i]=0;// dat2[i]=0;// }//}////void initset(int k,int a){// k+=n-1;// dat[k]=a;// while(k>0){// k=(k-1)/2;// dat[k]=dat[k*2+1]+dat[k*2+2];// }//}//////[a,b)の間を[l,r]区間で比較しアップデート////引数のindexに注意////nは固定。initで計算すみ////update2(L[i],R[i]+1,0,0,n,D[i]);//void update2(int a,int b,int k,int l,int r,int v){//v更新値、区間は0-index// if(r<=a || b<=l)return;// if(a<=l && r<=b){// dat[k]+=dat2[k];// if(r-l>1){// dat2[k*2+1]+=dat2[k]/2;// dat2[k*2+1]+=dat2[k]/2;// }// dat2[k]=v*(r-l);// return;// }else{// update2(a,b,k*2+1,l,(l+r)/2,v);// update2(a,b,k*2+2,(l+r)/2,r,v);// return;// }//}////int query(int a,int b,int k,int l,int r){// if(r<=a || b<=l)return 0;// if(a<=l && r<=b){// dat[k]+=dat2[k];// if(r-l>1){// dat2[k*2+1]+=dat2[k]/2;// dat2[k*2+1]+=dat2[k]/2;// }// dat2[k]=0;// return dat[k];// }// else{// int vl=query(a,b,k*2+1,l,(l+r)/2);// int vr=query(a,b,k*2+2,(l+r)/2,r);// return vl+vr;// }//}//void printb(unsigned int v) {// unsigned int mask = (int)1 << (sizeof(v) * CHAR_BIT - 1);// do putchar(mask & v ? '1' : '0');// while (mask >>= 1);//}#ifdef DEBUG#else#endifvoid dft(vector<complex<double>>& p, int inverse) {int sz = (int)p.size();if (sz == 1)return;vector<complex<double>> x0, x1;for(int i=0;i<sz/2;i++){x0.push_back(p[2*i]);x1.push_back(p[2*i+1]);}dft(x0, inverse);dft(x1, inverse);complex<double> now = 1;complex<double> zeta = polar(1.0, inverse * (2.0*acos(-1))/sz);//複素数の極形式 角度(2*pi)/nfor(int i=0;i<sz;i++){p[i] = x0[i%(sz/2)] + now * x1[i%(sz/2)];now *= zeta;}}vector<double> multiply(vector<complex<double>> f, vector<complex<double>> g) {vector<complex<double>> p, q;int jisu = 1;while (jisu < f.size()+g.size()){jisu *= 2;}p.resize(jisu); q.resize(jisu);for(int i=0;i<f.size();i++){p[i] = f[i];}for(int i=0;i<g.size();i++){q[i] = g[i];}dft(p, 1);dft(q, 1);for(int i=0;i<jisu;i++){p[i] *= q[i];}dft(p, -1);vector<double> res;for(int i=0;i<jisu;i++){res.push_back(p[i].real()/jisu);}return res;}double keisu[400000];int main(int argc, const char * argv[]){//scanf("%s",S);//scanf("%d",&N);//scanf("%lld %lld",&target1,&target2);//sscanf(tmp.c_str(),"%dd%d%d",&time[i], &dice[i], &z[i]);//getline(cin, target);//ifstream ifs("01");//テスト用//ifs >> a;//ここから//入力高速化ios::sync_with_stdio(false);cin.tie(0);int n,q;cin>>n>>q;vector<complex<double>>f,g;for(int i=0;i<n;i++){double t1;cin>>t1;f.push_back(complex<double>(t1,0.0));}for(int i=0;i<n;i++){f.push_back(f[i]);}for(int i=0;i<q;i++){int t1;cin>>t1;keisu[n-t1]+=1.0;}for(int i=0;i<=n;i++){g.push_back(complex<double>(keisu[i],0.0));}vector<double> ret=multiply(f,g);for(int i=n;i<2*n;i++){printf("%.0f ",ret[i]);//誤差が出るのでこの方法で出力}cout << endl;//ここまで//cout << "ans" << endl;//cout << " " << "ans" << endl;//printf("%.0f\n",ans);//小数点以下表示なし//printf("%.7f\n",p);return 0;}