For this test:
2
1492
1492
4
1492
65536
1492
100
Answer is 2 or 4?

#include <cstdio>
#include <map>
std:: map <int, int> a;
int n, m, q, i, x, ans;
void solve(){
    scanf("%d", &n);
    for(i = 0 ; i < n ; i ++) scanf("%d", &x), a[x] ++;
    scanf("%d", &m);
    for(i = 0 ; i < m ; i ++){
        scanf("%d", &q);
        if(a[q]) ans ++;
    }
    printf("%d", ans);
}
int main(){
    solve();
}

给二分查找的参数传错了，传的是m。
弄得我都快崩溃了。
不过还好看了解答发现了。
下面是C代码
**********************************************************************************************
#include<stdio.h>
int teacher[15001]={0};
int exist_temp(int temp,int m){
    int first=0,last=m-1,count=0;
    while(first<=last){
        int mid=(first+last)/2;
        if(teacher[mid]==temp){
            count++;
            return count;
        }
        else{
            if(teacher[mid]>temp) last=mid-1;
            else first=mid+1;
        }
    }
    return count;
}
int main(){
    int n,m,i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&teacher[i]);
    scanf("%d",&m);
    int count=0,hi=m;
    while(hi--){
        int temp;
        scanf("%d",&temp);
        if(exist_temp(temp,n)!=0)
            count++;
    }
    printf("%d\n",count);
    return 0;
}

var
a:array[1..15000] of integer;
i:integer;
m,n,k:integer;
b:array[1..1000000] of longint;
j:integer;
Begin
k:=0;
readln(n);
for i:=1 to n do read(a[i]);
readln(m);
for j:=1 to m do readln(b[j]);
for i:=1 to n do
for j:=1 to m do
if b[j]=a[i] then k:=k+1;
writeln(k);
end.

Не знаю английского, извините админы :( Помогите пожалуйста, всё время выскакивает эта ошибка на 8 или на 9 тесте. Пишу на C# помогите оптимизировать код.


using System;

namespace EkzamenIstorii
{
    class Program
    {
        static void Main()
        {
            Work work = new Work();
            work.Start();
        }
    }

    class Work
    {
        int[][] TichersDate;
        int[] UchenikDate;
        int Sovpadenia, buf=0;

        public void Start()
        {
            Input();
            Algoritm();
            Output();
        }

        void Input()
        {

            int CountTichersDates = int.Parse(Console.ReadLine());
            buf = CountTichersDates / 1000;
            buf += 1;
            TichersDate = new int[buf][];
            for (int i = 0; i < buf; i++)
            {
                TichersDate[i] = new int[1];
                for (int j = 0; j < CountTichersDates; j++)
                {

                    TichersDate[i][j] = int.Parse(Console.ReadLine());
                    Array.Resize(ref TichersDate[i], TichersDate[i].Length + 1);
                    if (i == 999)
                    {
                        CountTichersDates -= 1000;
                        break;
                    }
                }

                Array.Resize(ref TichersDate[i], TichersDate[i].Length-1);
            }

            int CountUchenikDate = int.Parse(Console.ReadLine());
            UchenikDate = new int[CountUchenikDate];
            for (int i = 0, j=0; i < UchenikDate.Length; i++)
                UchenikDate[i] = int.Parse(Console.ReadLine());

        }

        void Algoritm()
        {
            for (int k = 0; k < UchenikDate.Length; k++)
            {
                bool flag = false;
                for (int i = 0; i < buf; i++)
                {
                    if (UchenikDate[k] >= TichersDate[i][0] && UchenikDate[k] <= TichersDate[i][TichersDate[i].Length-1])
                        for (int j = 0; j < TichersDate[i].Length; j++)
                            if (UchenikDate[k] == TichersDate[i][j])
                            {
                                Sovpadenia++;
                                flag = true;
                                break;
                            }
                    if (flag) break;
                }
            }
        }

        void Output()
        {
            Console.WriteLine(Sovpadenia);
        }
    }
}

Can someone tell me the test case 2 please.

#include <iostream>

int main()
{
 long int i, n, m, z, s, k, a[16000], l, r, mid;
 std::cin >> n;
 k=0;
 for (i=0; i<n; i++)
 {
  std::cin >> z;
  if ((i!=0) && (z!=a[k]))
  {
   a[k]=z; k++;
  }
  if (i==0)
  {
   a[k]=z; k++;
  }
 }
 n=k-1;
 std::cin >> m;
 s=0;
 k=0;
 for (i=0; i<m; i++)
 {
  l=0; r=n; k=0;
  std::cin >> z;
  if ((z>a[0]) && (z<a[n]))
   while ((l<r) && (k<n-1))
   {
    k=k+1;
    mid=(l+r)/2;
    if (a[mid]>z)
     r=mid;
     else if (a[mid]<z)
     l=mid;
     else if (a[mid]==z)
      break;
   }
  else if ((z==a[0]) || (z==a[n]))
   s++;
  if ((a[mid]==z) && (mid!=0))
   s++;
 }
 std::cout << s;
}

Does any one have a faster code of python than this

p=int(input())
plist=set()
for i in range (p):
    a=int(input())
    plist.add(a)

s=int(input())
slist=[]
count=0
for i in range (s):
    a=int(input())
    if a in plist:
        count+=1
print (count)

Here are some tips for passing with Java code.

      Read      |    Data/Search   | Result
Scanner         |      TreeSet     | TLE on 8
Scanner         |      HashSet     | TLE on 8
Scanner         |a[n]&binary search| TLE on 5 ???
StringTokenizer |      TreeSet     | 0.765
StringTokenizer |      HashSet     | 0.546
StringTokenizer |a[n]&binary search| TLE on 5 ???

Conclusions:
Use StringTokenizer(Scanner is very slow) and HashSet.
I think HashSet outperforms TreeSet for two reasons:
1. data doesn't cause too many collisions
2. inserting in a tree is still O(log(n)) even for sorted data,while for HashSet it is O(1)

Question: I have no clue why the simple binary search I wrote took so long ...
It should have outperformed at least the treeset(no insertion costs; search is the same O(log(n)) but with no overhead from method calls...)

I tried everything to do that but i got TLE, and then MLE.

So I used index table with 1024*1024 elements and got AC.
But the problem said that 10^9.

Maybe it's a joke ?

#include<stdio.h>
int main()
{
    int n, i, j;
    long int m;
    long long int pro[15000], stu[15000];
    int count = 0;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        scanf("%lld\n", &pro[i]);
    }
    scanf("%ld\n", &m);
    for (i = 1; i <= m; i++)
    {
        scanf("%lld\n", &stu[i]);
        for (j = 1; j <= n; j++)
        {
            if (stu[i] == pro[j])
                count++;
        }
    }
    printf("%d", count);
    return 0;
}

#include<iostream>
#include<conio.h>
#include<Math.h>

using namespace std;

int  binarySearch(int  A[], int n, int x) {
    int low, high, mid;
    low = 0;
    high = n-1;

    while (low <= high) {
        mid = (low + high) / 2;
        if  (x == A[mid]) return(mid);
        else if (x < A[mid])  high = mid-1;
        else low = mid + 1;
    }
    return(-1);
}

int main()
{
    int n, a[ 15001 ];
    int m, counter = 0;
    int b;
    cin>>n;
    for(int i = 0; i < n; i ++ )
        cin>>a[ i ];
    cin>>m;
    for(int i = 0; i < m; i ++ )
    {
        cin>>b;
        if(binarySearch(a, n, b ) != -1 )
            counter ++;
    }
    cout<<counter<<endl;
    return 0;
}

:)

Very good task.Thanks!!!

var   a:array[1..15000] of longint;
i,n,j,k,flag,b,m:longint;
 k1 :longint;
begin
  k:=0;
  read(n);
read(a[1]);k:=1;
if n>1 then begin
for i:=2 to n do begin
read(b);
flag:=0;
j:=1;
repeat
if a[j]=b then begin flag:=1; end;
j:=j+1;
until (flag=1) or (j>k);
if flag=0 then begin k:=k+1; a[k]:=b;end;
end; end;
read(m);
for i:=1 to m do begin
read(b);
j:=1;    flag:=0;
repeat
if a[j]=b then begin flag:=1; k1:=k1+1;end;
j:=j+1;
until (flag=1) or (j>n);
end;
  writeln(k1);
end.
Тайм лимитед на 8 тесте. Что не так?? Где я что прохлопала.... Прохелпите мне, плиз

import java.util.Scanner;

public class _1991 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a, b, i;

        a = sc.nextInt();

        int[] str = new int[a];
        for (i = 0; i < a; i++) {
            str[i] = sc.nextInt();
        }
        b = sc.nextInt();
        int counter = 0;
        for (i = 0; i < b; i++) {
            int c = sc.nextInt();
            for (int aStr : str) {
                if (aStr == c) {
                    counter++;
                }
            }
        }
        System.out.println(counter);
    }
}

i understood my mistake

Edited by author 06.04.2014 16:16

Edited by author 06.04.2014 16:16

Edited by author 06.04.2014 16:27

const y=1;
type Tarray=array[-1..15002] of int64;
var m,n,b,c,h,l,ans:int64;i,j:longint;d:Tarray;e:array[0..100002] of int64;
function binp(a:Tarray;k,k1,k2:int64):int64;
begin
l:=k2;
b:=(k1+k2) div 2;
while a[b]<>k do
begin
if a[b]<k then
begin
k1:=b;
b:=(k1+k2) div 2;
if b=k1 then b:=b+1;
if (b>l) or (a[b]>k) then exit;
end;
if a[b]>k then
begin
k2:=b;
b:=(k1+k2) div 2;
if b=k2 then b:=b-1;
if (b<1) or (a[b]<k) then exit;
end;
end;
if a[b]=k then binp:=1 else binp:=0;
end;
begin
readln(n);
For i:=1 to n do
readln(d[i]);
readln(m);
For i:=1 to m do
readln(e[i]);
For i:=1 to m do
ans:=ans+binp(d,e[i],y,n);
write(ans);
end.

Edited by author 24.01.2014 15:24

#include <iostream>
using namespace std;

int main()
{
    int N, M;  int S[15001];
 int S1[1000001];

    cin >> N;
    for (int i1 = 1; i1 <= N; i1++)
        cin >> S[i1];


    int f = 0;

    cin >> M;
    for (int i = 1; i <= M; i++)
        cin >> S1[i];

    for (int i1 = 1; i1 <= N; i1++)
    for (int i = 1; i <= M; i++)
    if (S[i1] == S1[i]) f++;

    cout << f;
}

#include <iostream>
using namespace std;


int main()
{
    int n = 0, m = 0, a = 0, s = 0, k = 0;
    int arr[15001];
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> arr[i];
    }
    cin >> m;
    bool flag = true;
    int j = 0;
    int left = 0, right = n-1;
    for(int i = 0; i < m; i++)
    {
        cin >> a;
        j = 0;
        left = 0;
        right = n-1;
        flag = true;

        if(a == arr[0])
        {
            flag = false;
            s++;
        }
        else
        {
            if(a == arr[n-1])
            {
                flag = false;
                s++;
            }
        }
        if(a > arr[n-1])
        {
            flag = false;
        }

        while(flag)
        {
            if(a > arr[j])
            {
                left = j;
                j = (left + right)/2;
                if(a == arr[j])
                {
                    {
                        flag = false;
                        s++;
                    }
                }
                if(right-left <= 1)
                {
                    flag = false;
                    if(a == arr[j+1]) s++;
                }
            }
            else
            {
                right = j;
                j = (left + right)/2;
                if(a == arr[j])
                {
                    {
                        flag = false;
                        s++;
                    }
                }
                if(right-left <= 1)
                {
                    flag = false;
                    if(a == arr[j+1]) s++;
                }
            }
        }
    }
    cout << s;
    return 0;
}

Edited by author 17.11.2013 16:03