Show all threads Hide all threads Show all messages Hide all messages | About new lines | Igor Parfenov | 1542. Autocompletion | 11 Jul 2023 15:44 | 1 | There is no checker in this problem. In my solution I 1. Print new line after query even if there is no strings which satisfy it 2. Don't print new line after last query | if you have WA#10 try this: | hoan | 1542. Autocompletion | 26 Mar 2023 18:27 | 2 | input: 2 b 1 a 1 2 a b output: a [empty] b hope can help you! GOOD LUCK! also, it has more than 10 matches | It seem like that the lenth of the words is greater than 15? | zwqzwq | 1542. Autocompletion | 21 May 2021 04:34 | 2 | I set the length of my array to 15 then got WA at #14 while I set16 then I got AC But I dont know why,could anyone help me? | WA on Test 2 | silent82lion90 | 1542. Autocompletion | 5 Dec 2019 08:21 | 2 | My code doesn't leave empty line after the last query. What can be the cause of WA2? Seeing many people also got WA2 :(( Edited by author 21.04.2017 07:33 Edited by author 21.04.2017 07:33 if no word found with any query dont print any new line | WA#2 don't know what's the problem. HELP! | ZHENG WANG | 1542. Autocompletion | 5 Dec 2019 08:20 | 2 | Can someone help me? Please? I do it with Python3 ,and does not print out empty line after last queue here's my code: def getSecond(temp): return temp[1] if __name__ == '__main__': while True: try: N = int(input()) Words = [] for n in range(N): Words.append(input().split()) Words[n][1] = int(Words[n][1]) M = int(input()) Beginners = [] for m in range(M): Beginners.append(input()) for mm in range(M): start = list(Beginners[mm]) matchs = [] for nn in range(N): word = list(Words[nn][0]) flag = True for s in range(len(start)): if start[s] != word[s]: flag = False break if(flag): matchs.append(Words[nn]) if matchs != []: matchs.sort() matchs.sort(key = getSecond, reverse = True) count = 0 for match in matchs: if count > 10: break print(match[0]) count += 1
if mm != M-1: print() except: break
if no word found with any query dont print any new line | idk why but my code do not work on TOJ compiler but it works on my pycharm compiler | Oleg Bozhenov | 1542. Autocompletion | 18 Nov 2019 03:36 | 1 | So, when user starts looking for words, my program immediately writes the answer. Maybe that's why it isn't correct. For example: user -> 2 user -> ab program -> abc user -> xz program -> xzy | TEST 3 | Prodip Datta | 1542. Autocompletion | 11 Sep 2018 15:52 | 1 | TEST 3 Prodip Datta 11 Sep 2018 15:52 WA On TEST#3 .. any help plz ??? Edited by author 11.09.2018 15:53 Edited by author 11.09.2018 15:53 | If you've got WA #11 | Pavel Khaustov [Tomsk PU] | 1542. Autocompletion | 30 Jun 2018 19:16 | 4 | If you've got WA #11 then your program deals bad with repeatative queries. Try this test: -------------------- 2 acm 10000 acmicpc 10000 2 ac ac --------------------- Correct answer is: --------------------- acm acmicpc acm acmicpc --------------------- this code works fine for above input but still gives wa#11 I believe, this will help you 18 a 10 ba 0 bb 1 bc 1 bd 1 be 1 bf 1 bg 1 bh 1 bi 1 bj 1 bk 1 bl 1 bm 1 bn 1 bo 1 bp 1 bq 1 1 b ba can't be with zero frequency: 1 ≤ n_i ≤ 106 | How i must output anwser? | Felix_Mate | 1542. Autocompletion | 25 Apr 2017 15:38 | 2 | Написал лобовой вариант и всё равно WA10! Значит, вывод не верен. Кто может подсказать, как выводить ответ?(Форум не помог) #define _CRT_SECURE_NO_WARNINGS #define mk make_pair #include <string> #include <map> #include <iostream> using namespace std; typedef map <string, int> mymap; const int nmax = 100005; mymap t[4 * nmax]; mymap answer[nmax]; string word[nmax]; int cnt[nmax]; int n, m; string w_print[11]; int c_print[11]; mymap Search(int L, int R); int BinaryDown(int L, int R, string s); int BinaryUp(int L, int R, string s); mymap Optimal(mymap map1, mymap map2); void Print(mymap M); void QSort_W(int L, int R); void QSort2(int L, int R); void QSort3(int L, int R); int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> word[i] >> cnt[i]; QSort_W(1, n); cin >> m; for (int i = 1; i <= m; i++) { string s; cin >> s; int L, R; L = BinaryDown(1, n, s); R = BinaryUp(1, n, s); answer[i].clear(); if (L != -1 && R != -1) answer[i] = Search(L, R); } for (int i = 1; i <= m; i++) { Print(answer[i]); if(i!=m) cout<<endl; if(!(answer[i].empty()) && i!=m) cout<<endl; } return 0; } mymap Search(int L, int R) { mymap res; res.clear(); for(int i=L;i<=R;i++) { mymap x; x.insert(mk(word[i],cnt[i])); res=Optimal(res,x); } return res; } void Print(mymap M) { int n = 0; for (mymap::iterator it = M.begin(); it != M.end(); it++) { w_print[++n] = it->first; c_print[n] = it->second; } if (n == 0) return; QSort2(1, n); for (int i = 1; i <= n;) { int j = i + 1; while (j <= n && c_print[j] == c_print[i]) j++; QSort3(i, j - 1); i = j; } for (int i = 1; i<n; i++) cout << w_print[i] << endl; cout << w_print[n]; } void QSort2(int L, int R) { int i, j; int X = c_print[(L + R) / 2]; i = L, j = R; while (i <= j) { while (c_print[i] > X) i++; while (c_print[j] < X) j--; if (i <= j) { string Y = w_print[i]; w_print[i] = w_print[j]; w_print[j] = Y; int k = c_print[i]; c_print[i] = c_print[j]; c_print[j] = k; i++; j--; } } if (L < j) QSort2(L, j); if (i < R) QSort2(i, R); } void QSort3(int L, int R) { int i, j; string X = w_print[(L + R) / 2]; i = L, j = R; while (i <= j) { while (w_print[i] < X) i++; while (w_print[j] > X) j--; if (i <= j) { string Y = w_print[i]; w_print[i] = w_print[j]; w_print[j] = Y; int k = c_print[i]; c_print[i] = c_print[j]; c_print[j] = k; i++; j--; } } if (L < j) QSort3(L, j); if (i < R) QSort3(i, R); } void QSort_W(int L, int R) { int i, j; string X = word[(L + R) / 2]; i = L, j = R; while (i <= j) { while (word[i] < X) i++; while (word[j] > X) j--; if (i <= j) { string Y = word[i]; word[i] = word[j]; word[j] = Y; int k = cnt[i]; cnt[i] = cnt[j]; cnt[j] = k; i++; j--; } } if (L < j) QSort_W(L, j); if (i < R) QSort_W(i, R); } int BinaryDown(int L, int R, string s) { for(int i=L;i<=R;i++) if(s==word[i].substr(0, s.length())) return i; return -1; } int BinaryUp(int L, int R, string s) { for(int i=R;i>=L;i--) if(s==word[i].substr(0, s.length())) return i; return -1; } mymap Optimal(mymap map1, mymap map2) { mymap res; res.clear(); if (map1.size() + map2.size() <= 10) { res = map1; for (mymap::iterator it = map2.begin(); it != map2.end(); it++) res.insert(mk(it->first,it->second)); return res; } else { res = map1; for (mymap::iterator it = map2.begin(); it != map2.end(); it++) { if (res.size() < 10) res.insert(mk(it->first, it->second)); else { if (res.begin()->second < it->second) { res.erase(res.begin()); res.insert(mk(it->first, it->second)); } } } return res; } } void Print(mymap M) { ... for (int i = 1; i<=n; i++) cout << w_print[i] << endl; } for (int i = 1; i <= m; i++) { Print(answer[i]); if(i!=m) cout<<endl; } | if you have wa#1 | Baurzhan | 1542. Autocompletion | 22 Jul 2016 19:32 | 3 | don't print endline symbol after last query: for(int i=0;i<queries;i++){ answer_the_query(); if(i!=queries-1) printf("\n") //without this line it got wa#1! } Edited by author 15.09.2010 08:42 Your solution works.Thanks a lot!!! | WA2 | PagucT | 1542. Autocompletion | 24 Dec 2015 09:49 | 1 | WA2 PagucT 24 Dec 2015 09:49 Can anyone help with this? I do not print at the end of an empty string. all the tests of the discussions my program passes. | Help!!!!!!!!Wa on test 11!!!!!!! | Eazy jobb | 1542. Autocompletion | 19 Nov 2014 12:32 | 3 | /* My program got WA on test 11!!! What's wrong with my code? Anyone can help me!!! */ #include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <vector> #include <string> #include <cstdlib> #include <cstring> #include <utility> #include <iostream> #include <algorithm> #define FI first #define SE second #define LSON(x) (x<<1) #define RSON(x) ((x<<1)|1) #define Benefit(x,y) x=max(x,y) #define CS const static #define SORT_CMP(s,l,r,cmp) sort(s+(l),s+(r)+1,cmp) #define SORT(s,l,r) sort(s+(l),s+(r)+1) #define MP(x,y) make_pair(x,y) #define Randomize srand( (unsigned int) time ( NULL ) ) #define INOUT(x,y) freopen(x,"r",stdin),freopen(y,"w",stdout) using namespace std; typedef char name[20]; CS int MaxN = 100010 ; struct word { name x; int val,len; word() {x[0] = 0; val = 0;} }; struct Trie { Trie * next[26]; word * ans[10]; Trie() { for(int i=0;i<26;i++) next[i] = NULL ; for(int i=0;i<10;i++) ans[i] = NULL ; } } * Tree; word p[MaxN]; name ask; int n,m,asklen; void Insert(Trie * x,int _y,int pos) { int i; word & y = p[_y]; for(i=0;i<10;i++) if((x->ans[i]==NULL)||(x->ans[i]->val<y.val)) break; if(i<10) { for(int j=9;j>i;j--) x -> ans[j] = x->ans[j-1]; x -> ans[i] = p + _y; } if(pos!=y.len) { int u = y.x[pos] - 'a'; if(!x->next[u]) x -> next[u] = new Trie ; Insert(x->next[u],_y,pos+1); } } void Init() { scanf("%d\n",&n); Tree = new Trie ; for(int i=1;i<=n;i++) { scanf("%s %d\n",p[i].x,&p[i].val); p[i].len=strlen(p[i].x); Insert(Tree,i,0); } } void Query(Trie * x,int pos) { if(pos == asklen) { for(int i=0;i<10;i++) if(x->ans[i]) printf("%s\n",x->ans[i]->x); else break; return ; } int u = ask[pos] - 'a'; if(x->next[u]) Query(x->next[u],pos+1); } void Solve() { scanf("%d\n",&m); while(m--) { scanf("%s\n",ask); asklen = strlen(ask) ; Query(Tree,0); if(m) printf("\n"); } } int main() { Init(); Solve(); return 0; } Edited by author 31.05.2012 14:40 you are an idiot. why so many inclusions? and your code is delirium. ...wrote Nikolay, 43 solved problems and 6000+-th place, to blablabla, 280 solved problems and place within top 1000. P.S. And the code style is not great, but quite okay. Edited by author 19.11.2014 12:32 | RE2??? | endtimes | 1542. Autocompletion | 14 Jan 2014 17:59 | 1 | RE2??? endtimes 14 Jan 2014 17:59 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace _1542 { public class word { public string line; public int count; public word(string g="", int f=0) { line=g; count =f; } } class sortim: IComparer<object > { public int Compare(object x, object y) { word a, b; a = (word)x; b = (word)y; if (a.count < b.count) return 1; else if (a.count > b.count) return -1; else return String.Compare(a.line, b.line); } } class Program { static void Main(string[] args) { sortim sort = new sortim(); int n = Convert.ToInt32(Console.ReadLine()); word[] wor = new word[n]; for (int i = 0; i < n; i++) { string[] temp = Console.ReadLine().Split(' '); wor[i] = new word(temp[0], Convert.ToInt32(temp[1])); } int g= Convert.ToInt32(Console.ReadLine()); for (int i = 0; i < g; i++) { string request = Console.ReadLine(); word[] select = Array.FindAll(wor, e => e.line.Substring(0,request.Length)==request ); Array.Sort(select, sort); for (int i1 = 0; i1 < Math.Min(select.Length,10); i1++) { Console.WriteLine(select[i1].line); } if (i!=g-1) Console.WriteLine(); } } } } | RE test#11 | zhuchenxi | 1542. Autocompletion | 15 Jul 2013 18:32 | 1 | why?? #include<cstdio> #include<algorithm> #include<iostream> #include<cmath> #include<climits> #include<string> #include<string.h> #include<vector> #define sf scanf #define pf printf #define cls(a) memset(a,0,sizeof(a)) #define _cls(a) memset(a,-1,sizeof(a)) using namespace std; struct Edge_t{ int to,next; }edge[400000]; int hed[200000]; int et; struct tree{ tree *br[26]; vector<int>vec; tree(){ for(int i=0;i<26;++i) br[i]=NULL; vec.clear(); } }; struct Input{ char str[18]; int val; }inp[100010]; tree *head; inline void adde(int u,int v){ edge[et].to=v,edge[et].next=hed[u],hed[u]=et++; } inline void addtree(char *st,int index){ int id,i; tree *s=head; for(i=0;st[i];++i){ id=st[i]-'a'; if(!s->br[id]) s->br[id]=new tree; s=s->br[id]; } s->vec.push_back(index); } inline bool cmp(int a,int b){ if(inp[a].val==inp[b].val) return strcmp(inp[a].str,inp[b].str)<0; return inp[a].val>inp[b].val; } void DEL(tree *s){ int i; for(i=0;i<26;++i) if(s->br[i]) DEL(s->br[i]); s->vec.clear(); delete(s); } int res[1000010]; void deal(char *st,int index){ int i,id,j; tree *s=head; for(i=0;st[i];++i){ id=st[i]-'a'; if(!s->br[id]) return; s=s->br[id]; for(j=0;j<s->vec.size();++j) adde(s->vec[j],index); } } int main(){ int i,j; int n,m,sk; char str[18]; while(scanf("%d",&n)!=EOF){ head=new tree; _cls(hed); for(i=et=0;i<n;++i) sf("%s%d",inp[i].str,&inp[i].val); sf("%d",&m); for(j=0;j<m;++j){ sf("%s",str); addtree(str,j); } for(i=0;i<n;++i) deal(inp[i].str,i); int e; for(i=0;i<m;++i){ if(i) puts(""); for(sk=0,e=hed[i];e!=-1;e=edge[e].next) res[sk++]=edge[e].to; if(!sk) continue; sort(res,res+sk,cmp); //if(sk>0) for(j=0;j<sk && j<10;++j) pf("%s\n",inp[res[j]].str); } DEL(head); } return 0; } /* 2 ab 10 ac 20 1 f */ | Can you help me with test 9? | seregacorsar | 1542. Autocompletion | 11 Mar 2013 01:17 | 1 | I can't pass test 9. Who can help me? | Can somebody tell me what to do if WA9? | OwenOu | 1542. Autocompletion | 11 Aug 2012 09:33 | 1 | | What about 10 test? My program here. | Alexander Goncharov | 1542. Autocompletion | 6 Aug 2012 16:25 | 1 | #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; bool compar1(pair<string, int> a, pair<string,int> b) { if (a.second>b.second) return true; else return false; } int main(int argc, char *argv[]) { int n = 0; cin >> n; vector<pair<string, int> > v(n); for (int i = 0; i<n; i++) { string tmp; int num; cin >> tmp; cin >> num; v.push_back(make_pair(tmp, num)); } sort(v.begin(), v.end(), compar1); int m = 0; cin >> m; for (int i = 0; i<m; i++) { string str; cin >> str; for (int j = 0; j<n; j++) { if (v[j].first.find(str)==0&&j<10) { cout << v[j].first << endl; } } if (i!=m-1) cout << endl; } system("PAUSE"); return 0; } | If you have WA2# | Zura Isakadze [Tbilisi SU] | 1542. Autocompletion | 23 May 2012 01:02 | 1 | Be sure that you don't print empty line when it's the last query. Edited by author 23.05.2012 01:02 | Unclear problem statement | Denis Koshman | 1542. Autocompletion | 12 Aug 2011 19:08 | 3 | 1) What should be output when there are no words starting with input string? 2 successive empty lines in the output are weird, so I ask. 2) If input contains some word exactly as it is, should I place this word in the output? I.e. does the verb "start" allow equality as well? Ok, my AC solution treats equal strings as starting and it will output two blank lines in case of empty result between two non-empty ones. What about ten empty results between two non-empty ones? | any hint about how to avoid MLE? | fOrgIvE | 1542. Autocompletion | 3 May 2011 15:40 | 4 | My old prob got AC before rejudge, but MLE 21 now, I tried to make it better but failed. Any hint? There are less requests than words |
|
|