|
|
This can be easily done on python В задачах с условием, на прочтение которых уходит 10 минут (или более) предлагаю писать краткое содержание в форуме! Can somebody give me some tests? I can;t find what's wrong with my prog. Thanks a lot. oh... very stupid error. you should use .clone() in java. now TLE 10 Edited by author 21.02.2010 18:22 10 years have passed) I hope it will help somebody. I had WA3, i forgot to clear vector after set intersection, very stupid mistake Edited by author 24.03.2019 23:54 Edited by author 24.03.2019 23:54 this test helped me: 2 a: fuck it b: fuck this shit 1 a b answer: fuck reason: I indexed the words from 0, but I should from 1 Use unordered map and unordered set. max_load_factor(0.25) reserve (1<<x) I used such variables: map<string,int> id; set<string> list[1003]; map<string,int> mp; vector<string> res; but got TL test 10. Can i get AC with same solution? Yes if instead string use struct{ int num; int row; int poz1; int poz2; }; to have deal with segments of char S[1000][125] to pass test 10 you must do 1) compare hash codes instead of string compare 2) use vectors+sort. In this case vector is way faster than std::set 3) fast I/O. 4) fast list intersection good luck! Words can be easily hashed like: int hash = 0; while(..){ hash = hash * 31 + 'readed byte' } So equals will looks like: @Override public boolean equals(Object o) { return this.hash == o.hashCode(); } On my data program works fine, but got WA. Help me, please :( I can't understand where is trouble in my code #include<iostream> #include<map> #include<string> #include<algorithm> #include<list> #include<vector> #include <set> using namespace std; int main() { map<string,vector <string> > stored; int n; cin >> n; string str; for(int i=0;i<n;i++) { cin>>str; str.erase(str.length()-1,str.length()); vector<string> vec; while(cin.peek()!='\n') { string tmp; cin>>tmp; vec.push_back(tmp); } stored[str]=vec; } int m; cin>>m; for(int i=0;i<m;i++) { cin.ignore(); vector<string> tmp; while(cin.peek()!='\n' && !cin.eof()) { string tmp1; cin>>tmp1; tmp.push_back(tmp1); } vector<string> v1 = stored[tmp[0]]; for (int i = 1; i<tmp.size(); i++) { vector<string> v2 = stored[tmp[i]]; std::vector<string> v(v1.size()+v2.size()); // Sort as required by set_intersection std::sort(v1.begin(),v1.end()); std::sort(v2.begin(),v2.end()); // Compute std::vector<string>::iterator it = std::set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),v.begin()); // Display v.erase(it,v.end()); //for(std::vector<string>::iterator it = v.begin();it < v.end(); ++it) std::cout<<*it<<" "; //cout << endl; v1=v; } if (v1.size()!=0) { for (int i = 0; i<v1.size(); i++) { cout << v1[i] << " "; } cout << endl; } else { cout << "No solution." << endl; } } system("pause"); return 0; } Do not make many copies of strings where you can use only pointers on them. Here is my code. I think that all is good. Please help me. I am studing STL and I want solve this problem with STL. #pragma warning (disable:4786) #include<iostream> #include<map> #include<set> #include<string> #include<algorithm> using namespace std; int main() { map<string,set<string, less <string> >, less<string> > mp; set<string, less <string> >::iterator it,end; int m,n,i,j,q,minidx,min; bool t; string vec[126],str; cin>>n; for(i=0;i<n;i++) { cin>>str; str.erase(str.length()-1,str.length()); q=0; while(cin.peek()!='\n') { cin>>vec[q]; q++; } mp[str].insert(vec,vec+q); } cin>>m; for(i=0;i<m;i++) { minidx=0; min=1000000; q=0; cin.ignore(); while(cin.peek()!='\n' && !cin.eof()) { cin>>vec[q]; if(mp[vec[q]].size()<min) { min=mp[vec[q]].size(); minidx=q; } q++; } end=mp[vec[minidx]].end(); t=false; for(it=mp[vec[minidx]].begin();it!=end;it++) { for(j=0;j<q && mp[vec[j]].find(*it)!=mp[vec[j]].end();j++); if(j==q) { cout<<*it<<' '; t=true; } } if(!t) cout<<"No solution."; cout<<endl; } return 0; } Edited by author 17.11.2009 21:00 what is this - test 13 Edited by author 24.08.2009 15:46 sort. :-) Edited by author 26.08.2009 17:50 Edited by author 26.08.2009 17:51 Почему нет общего ограничения на количество всех вместе взятых ассоциаций, моя прога использует этот факт, как оказалось их даже больще чем 10000!) Придется переписывать( i found my mistake, now AC |
|
|