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

I set the length of my array to 15 then got WA at #14 while I set16 then I got AC

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

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

WA On TEST#3 .. any help plz ???

Edited by author 11.09.2018 15:53

Edited by author 11.09.2018 15:53

Написал лобовой вариант и всё равно 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;
    }
}

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

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.

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;
}

/*
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

Be sure that you don't print empty line when it's the last query.

Edited by author 23.05.2012 01:02

Timotius Sakti got AC with strange time about 2.5 sec...

input:
2
b 1
a 1

2
a
b

output:
a
[empty]
b

hope can help you!
GOOD LUCK!

Time limit was reduced from 3 sec to 2 sec. Submissions were rejudged. 15 authors lost AC.

Edited by author 11.02.2011 01:13

At first I got lots of WA #1 at this problem, but I was confident in my algo.

When I replaced stl::merge with stl::sort, I got AC.
When I replaced stl::merge with stl::inplace_merge, I got AC, too.
After that, I tried to rewrite the stl::merge myself, and also got AC.
Then I copied the source code of stl::merge from "include\c++\3.4.2\bits\stl_algo.h", and ... also AC.

Does it mean that there is something strange in stl::merge of Visual C++ 2010?


UPD: I have found that the stl::merge in Visual C++ 2010 sometimes will modify the elements in the origin vector. Be careful to use it!

PS:

/* G++ merge */

  template<typename _InputIterator1, typename _InputIterator2,
       typename _OutputIterator>
    _OutputIterator
    merge(_InputIterator1 __first1, _InputIterator1 __last1,
      _InputIterator2 __first2, _InputIterator2 __last2,
      _OutputIterator __result)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
      __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
        typename iterator_traits<_InputIterator1>::value_type>)
      __glibcxx_function_requires(_SameTypeConcept<
        typename iterator_traits<_InputIterator1>::value_type,
        typename iterator_traits<_InputIterator2>::value_type>)
      __glibcxx_function_requires(_LessThanComparableConcept<
        typename iterator_traits<_InputIterator1>::value_type>)
      __glibcxx_requires_sorted(__first1, __last1);
      __glibcxx_requires_sorted(__first2, __last2);

      while (__first1 != __last1 && __first2 != __last2)
    {
      if (*__first2 < *__first1)
        {
          *__result = *__first2;
          ++__first2;
        }
      else
        {
          *__result = *__first1;
          ++__first1;
        }
      ++__result;
    }
      return std::copy(__first2, __last2, std::copy(__first1, __last1,
                            __result));
    }


/* VC++ 2010 merge */

template<class _InIt1,
    class _InIt2,
    class _OutIt> inline
    _OutIt _Merge(_InIt1 _First1, _InIt1 _Last1,
        _InIt2 _First2, _InIt2 _Last2,
        _OutIt _Dest)
    {    // copy merging ranges, both using operator<
    for (; _First1 != _Last1 && _First2 != _Last2; ++_Dest)
        if (_DEBUG_LT(*_First2, *_First1))
            {    // merge first
            *_Dest = _Move(*_First2);
            ++_First2;
            }
        else
            {    // merge second
            *_Dest = _Move(*_First1);
            ++_First1;
            }

    _Dest = _Move(_First1, _Last1, _Dest);    // copy any tail
    return (_Move(_First2, _Last2, _Dest));
    }

Edited by author 17.12.2010 14:20

Edited by author 24.10.2010 21:58