제출 #739221

#제출 시각아이디문제언어결과실행 시간메모리
739221huynhyen1609Matching (CEOI11_mat)C++14
90 / 100
1037 ms65536 KiB
/* .. .:^!7?JJJYJJJJ?77!!~^. .:~7JYYJYYJJ?77?J??JY?JYY5YY?7~:. :!J5YJ??777J?J?????7J?J?7J?J?JYYYYY?~. :?5JJ???77!?77?J??J7?7???JJJJ?J777??JYJY?!. ^J5YYJJJ77?!7!7!77JJJJ?J77??Y???77!!777!7?JY5?^ ~JYY??J7??7J?7?!7!7???J?77!777J?JY?J7777?7?????5PY^ ^Y5J??J??!!???J??77777????J?J77?YY?!~^::::::^!77??YPG7. !PY?777?77!7!7J?7!7?????JJ??7J??J^:. .:!7?75GY: .JPJ!7!7?7?7!7!????????J?7??7J?YJ~. .:!7?JGP^ .JP?!7!!??7J7!!!?7J????7J7!!?!?7?7. . ^??YG5: !P??7777?77??777?7?!7!777!?7J??J?^ :~~: . ^?7YGY. :PY7??77!7~~:::.....:^^~!7??????J?^ . .7PGGPY: . !?JPB~ .Y5!!Y77!~:.. .:~7JJJ??J!. . . .5GGGGP^ ..:J?JBJ ~G?!!?7!^. .^7JJYYJ7:. . ..:~???~^^:..77?G5. !G!7?77: ..?J7~^~!77: . .. ..^~~~~~~~:.!75B! !P77J7^ ..~?:::^~!7?^ ........^~^^^^^:.^JYG?. !G???!: .~77!:. ..7?7?77~:....................^JPJ~ :P5??7: .JGGGGP! ...... ..................:^!JP?^ 7BJ7J~ .JGGGGG~ . .....................::::^!7?JJ?!^. .YG?Y7^ .~7??~:::. .. .... ... ....::::::::::::^?~^!?J7: :PPJ??: ..:^^^^^^: . .... ....::::^::::::::.:::^JP~..:75~ :YGYJ?^. .^^^^^^^:. .....:::::::::::...:::..:.::JP!~~7Y~ ~PP5J?^...::::.... ......::::::::.:.::.:::::.:::::::::^JP?7~. :75P5YJ!~^^^^!:...::^:::::::...:......::.....::::::::^^5? ?G?Y55PP5YJ!^:::::::::..:..:.:....:...:....::..::::^^7G^ ~P!^:::::.::::::::::::::...:.::::.:.:::::.:.......:::^PY :!JJ7~^::::::::::::::::..:.:.::.:::::...::.........:.JP. :5P?^:^:::::^::::::::::::.::::::.:.::.::........::7P: .P7::::::::::^::^^::::::::::::::::.:.........:::::J5. . ^G~:^^:::::::^:^^^^^:::::::::^:::::::::::::::^^::75^ :P!^^^^^^^^:^^^^^^:^:::::^:::^:::::::::::::::^^7JY^ .!5~^~^^^^^^^^^:^^^^^^^^:^^^^:^^^^^^^^^^^^^^~?55G? ~J?~~~^^~~^~~~^^^^^^^:^^^~^^^^^^^^~~!!!?Y55GP?J!. .~PYJ?77?7777!!!!!!!!!!!!7777??JJJJJ5PP5??J^ .. .777?5J??YYYYY5?7777!!!!~!~~^^::. .:: :!!~:.:^^: PENGUIN SO CUTE, I LOVE PENGUIN */ #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define NAME "" #define int long long #define pii pair<int,int> const int oo=1e9; const int base=1e6; const int mod=1e9+7; const int N=1e6; const int LG=18; const int Sqrt=350; //int hx[]={0,0,1,-1,1,1,-1,-1},hy[]={1,-1,0,0,1,-1,1,-1}; int n,m,a[N+5],p[N+4],tree[4*N+5],cnt[4*N+5]; pii b[N+5]; bool cmp(pii a,pii b) { return a.se<b.se; } void up(int id,int l,int r,int k,int val) { if(l==r) { tree[id]=val; if(val)cnt[id]=1; else cnt[id]=0; return; } int mid=(l+r)/2; if(k<=mid)up(id*2,l,mid,k,val); else up(id*2+1,mid+1,r,k,val); tree[id]=(tree[id*2]*p[cnt[id*2+1]]%mod+tree[id*2+1])%mod; cnt[id]=cnt[id*2]+cnt[id*2+1]; } main() { ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0); //freopen(""NAME".inp","r",stdin); //freopen(""NAME".out","w",stdout); cin>>n>>m; int h=0; for(int i=1;i<=n;++i) { int x;cin>>x; h=(h*base%mod+x)%mod; a[x]=i; } p[0]=1; for(int i=1;i<=m;++i)p[i]=p[i-1]*base%mod; //nén dãy b for(int i=1;i<=m;++i)cin>>b[i].fi,b[i].se=i; sort(b+1,b+m+1); for(int i=1;i<=m;++i)b[i].fi=i; sort(b+1,b+m+1,cmp); int sum=0; for(int i=0;i<n;++i)sum=(sum+p[i])%mod; queue<int>q; for(int i=1;i<=m;++i) { up(1,1,m,b[i].fi,i); if(i>=n) { int tmp=(tree[1]-sum*(i-n)%mod+mod)%mod; if(tmp==h)q.push(i-n+1); //cout<<tmp<<' '<<h<<'\n'; up(1,1,m,b[i-n+1].fi,0); } } cout<<q.size()<<'\n'; while(!q.empty()) { cout<<q.front()<<' '; q.pop(); } } /* ଘ(੭ˊᵕˋ)੭* ੈ✩‧˚huynhyen1609<3 */ /* 6 12 2 5 3 4 1 6 10 45 25 30 5 47 31 35 4 50 33 20 */

컴파일 시 표준 에러 (stderr) 메시지

mat.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main()
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...