제출 #739131

#제출 시각아이디문제언어결과실행 시간메모리
739131huynhyen1609Matching (CEOI11_mat)C++14
36 / 100
2083 ms35720 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 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],bit[N+5],c[N+5],k[N+4]; pii b[N+5]; bool cmp(pii a,pii b) { return a.se<b.se; } void up(int i,int val) { while(i<=m) { bit[i]+=val; i+=i&-i; } } int get(int i) { int g=0; while(i>0) { g+=bit[i]; i-=i&-i; } return g; } 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; for(int i=1;i<=n;++i) { int x;cin>>x; a[x]=i; } 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); /*for(int i=1;i<=n;++i) { c[i]=get(a[i])+1; up(a[i],1); }*/ memset(bit,0,sizeof(bit)); queue<int>q; for(int i=1;i<=m;++i) { if(i>n)up(b[i-n].fi,-1); up(b[i].fi,1); if(i>=n) { int d=0; for(int j=i-n+1;j<=i;++j) { int x=get(b[j].fi); if(x==a[j-i+n])++d; //cout<<x<<' '; }//cout<<'\n'; if(d==n)q.push(i-n+1); } } 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:79:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   79 | 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...