제출 #348195

#제출 시각아이디문제언어결과실행 시간메모리
348195algorithm16Matching (CEOI11_mat)C++14
63 / 100
562 ms65540 KiB
#include<iostream> #include<vector> #include<algorithm> using namespace std; typedef long long int llint; llint arr[1000005],ind[1000005],arr2[1000005],p1[1000005],t[2200005],p2[2200005],cnt2[2200005],cnt=1,off=1,p=31337; vector <llint> v,v2,sol; void update(int x,llint v,llint c) { p2[off+x]=v; cnt2[off+x]=c; //if(x==3) cout << p2[off+x] << " " << cnt2[off+x] << " " << v << " " << c << "\n"; for(int i=(off+x)/2;i>=1;i/=2) { t[i]=t[i*2]+t[i*2+1]; p2[i]=p2[i*2]+p2[i*2+1]; cnt2[i]=cnt2[i*2]+cnt2[i*2+1]; //if(x==3) cout << t[i] << " " << cnt2[x*2] << " " << p2[x*2+1] << "\n"; //if(x==3) i*2 << " " << i*2+1 << "\n"; t[i]+=cnt2[i*2]*p2[i*2+1]; //if(x==3) cout << t[i] << "\n"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m; cin >> n >> m; while(off<m) off*=2; llint h=0,h2=0; for(int i=0;i<n;i++) { cin >> arr[i]; ind[arr[i]]=i; } for(int i=0;i<n;i++) { h*=p; h+=ind[i+1]; } for(int i=0;i<m;i++) { cin >> arr2[i]; v.push_back(arr2[i]); } p1[0]=1; for(int i=1;i<=m;i++) { p1[i]=p1[i-1]*p; } sort(v.begin(),v.end()); for(int i=0;i<m;i++) { arr2[i]=lower_bound(v.begin(),v.end(),arr2[i])-v.begin()+1; if(i<n) v2.push_back(arr2[i]); } sort(v2.begin(),v2.end()); for(int i=0;i<n;i++) { h2*=p; h2+=lower_bound(v2.begin(),v2.end(),arr2[i])-v2.begin()+1; update(arr2[i]-1,p1[m-1-i],1); //cout << arr2[i]-1 << " " << p1[m-1-i] << " " << t[1] << "\n"; } //cout << "\n"; /*for(int i=0;i<n;i++) { cout << ind[i+1] << " "; } cout << "\n"; for(int i=0;i<m;i++) { cout << arr2[i] << " "; } cout << "\n";*/ //cout << h << " " << h2 << "\n"; //cout << (lower_bound(v2.begin(),v2.end(),arr2[0])-v2.begin()+1)*p1[n] << " " << h2 << "\n"; //cout << t[1] << "\n"; //cout << h << "\n"; for(int i=0;i+n-1<m;i++) { if(h*p1[m-n-i]==t[1]) sol.push_back(i+1); update(arr2[i]-1,0,0); update(arr2[i+n]-1,p1[m-n-i-1],1); //cout << arr2[i]-1 << " " << arr2[i+n]-1 << " " << p1[m-n-i-1] << "\n"; //cout << t[1] << "\n"; } cout << sol.size() << "\n"; for(int i=0;i<sol.size();i++) { cout << sol[i] << " "; } return 0; }

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

mat.cpp: In function 'int main()':
mat.cpp:81:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(int i=0;i<sol.size();i++) {
      |              ~^~~~~~~~~~~
#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...