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 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 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? 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 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 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 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 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 Написал лобовой вариант и всё равно 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; } 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!!! 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. /* 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 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(); } } } } 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 */ I can't pass test 9. Who can help me? #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; } Be sure that you don't print empty line when it's the last query. Edited by author 23.05.2012 01:02 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? 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 |
|