how can it be improved????

n = int(input())
sp = []
a = []
c = 0
for i in range(n):
    sp.append(int(input()))
m = int(input())
for i in range(m):
    x = int(input())
    if x in sp:
        c += 1
print(c)

Edited by author 08.09.2024 07:01

N =int(input())
Nl = []

for i in range(N):
    Nl.append(int(input()))

M = int(input())
Ml = []

for j in range(M):
    Ml.append(int(input()))

answerl = []


Nl = set(Nl)
Nl = list(Nl)
Nl.sort()

for ni in Nl:
    for mi in Ml:
        if mi == ni:
            answerl.append(mi)
        else:
            continue

print(len(answerl))

what are mistakes in this code?
#include <iostream>
using namespace std;
long long int a[15000];
long long int b[1000000];
int main()
{
    int c, f, d, e, g,l;
    l = 0;
    cin >> c;
    for (f = 0; f != c; f++)
    {
        cin >> a[f];
    }
    cin >> d;
    for (e = 0; e != d; e++)
    {
        cin >> b[e];
    }
    for (e = 0; e != d; e++)
    {
        g = b[e];
        for (f = 0; f != c; f++)
        {
            if (g == a[f])
            {
                l = l++;
                break;
            }

        }
    }
    cout << l << endl;
    system("pause");
    return 0;
}

Edited by author 18.02.2022 18:53

I've used those thing:
- binary search
- sys.stdin.readline() instead of input
- http://acm.timus.ru/forum/thread.aspx?id=30704&upd=636446663176701082
- checked min/max teacher's dates and didn't below/over them

and still have just 1.514-1.544

What's wrong? What's idea behind that?

Сначала пробовал через множества, потом сократил через map
всегда валился на 8 тесте по времени
Решил напрячься
Сел и написал два модуля, чтобы работать с битами
На преподавателе включаю биты
На студенте проверяю и прибавляю к ответу
Сдаю задачу, уже в предвкушении надписи "Accepted", как тут мои глаза лезут на лоб. Снова "TL8"
Что это за монстр такой этот восьмой тест?)

Could anyone give a piece of advice if i have a time limit exceeded with binary search?

time limit exceed on python3
there a code:
a=[]
for i in range(int(input())):
    a.append(input())
b=[]
n=0
for j in range(int(input())):
    if input() in a:
        n+=1
print(n)

please help me

import sys
p = input()
p_list = []
for i in range(int(p)):
    x = input()
    p_list.append(x)
s = input()
s_list = []
for i in range(int(s)):
    x = input()
    s_list.append(x)

count = 0
l = set(s_list).intersection(p_list)

for i in l:
    count += s_list.count(i)

print (count)

var
m,n,i,j,k,s,l:integer;
A: array [1..15000] of LongInt;
B: array [1..1000000] of LongInt;

begin
s:=0;
readln(n);
        for i:=1 to n do readln(A[i]);
readln(m);
        for j:=1 to m do begin readln(B[j]);     end;
i :=  1;
j :=  n;
k := 1;
for l:=1 to m do
        begin
                while  (i <=j) do
                begin
                k := (i + j) div 2;
                if B[l] > A[k] then i := k + 1
                                else j := k -1;

                end;
                if A[k] = B[l]  then s:=s+1;



        end;


writeln();
writeln(s);
readln;
end.

#include <iostream>
using namespace std;
int main()
{
     int n,m,teacher[1500],student[100000],same=0;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>teacher[i];
    cin>>m;
    for(int i=0;i<m;i++)
        cin>>student[i];

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            if(teacher[i]==student[j]) same++;

    cout<<same;
    return 0;
}

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Lesson {

    public static void main(String[] args) throws Exception {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int countPrepod = Integer.parseInt(bufferedReader.readLine());
        TreeSet<Long> prepod = new TreeSet();
        for (int i = 0; i < countPrepod; ++i) {
            prepod.add(Long.parseLong(bufferedReader.readLine()));
        }

        int countStudent = Integer.parseInt(bufferedReader.readLine());
        ArrayList<Long> student = new ArrayList();
        for (int i = 0; i < countStudent; ++i) {
            student.add(Long.parseLong(bufferedReader.readLine()));
        }

        student.sort(((o1, o2) -> Long.compare(o1,o2)));
        int result=0;
        for (long find:prepod)
        {
                while (Collections.binarySearch(student,find)>=0)
                {
                    ++result;
                    student.remove(find);
                }
        }
        System.out.println(result);
    }

}

First method:
Use multiple baskets, each basket is a list (in my case, i use vector<int>). Put the date d into the basket numbered d % number_of_baskets. To check the student answer, just pick the basket out and perform binary search. I chose 100 000 as the number of baskets, tried 1 000 000 baskets but it works much worse.

Second method:
Use vector<bool> (not bool array, the later cost 8 times more) to mark numbers under 300 000 000 (actually the vector size can go up to 500 000 000, but for some unknown reason, this smaller size run faster). Create another vector<int> to store the numbers that can't be marked using the bool vector above. Use binary_search to check for existence.

It seem like the IO is bottleneck, I used ios::sync_with_stdio(false) and my program run from ~1.5s to ~0.2s

Edited by author 01.10.2018 12:46

I submitted my solution, but it says Test Case 2 didn't pass.
Could anyone tell me what the test case is?

What's wrong in this code?
#include <bits/stdc++.h>
using namespace std;
int main () {
    setlocale(LC_ALL, "Russian");
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string k;
    map <int,int> mp;
    int i,j,m,n,s=0;
    cin>>n;
    for (i=0;i<n;i++){
        cin>>j;
        mp[j]=1;
    }
    cin>>m;
    for (i=0;i<m;i++){
        cin>>s;
        if (mp[s]>=1)
            mp[s]++;

    }
    int d=0;
    for (auto q:mp){
        if (q.second>1)
            cout<<q.second-1<<endl;
        else
            d++;
    }
    if (d==mp.size()) cout<<0<<endl;
}

Create an array of Boolean elements. Size = billion.
For i:=1 to n {{ introduce a variable; element of array with index [variable] equals true }}
For i:=1 to m {{ introduce a variable; if element of array with index [variable] equals true then increase the counter }}

And finally, we output counter))
That's all), sorry for bad english

But this solution takes 58 mb of memory... ((

Edited by author 06.04.2014 16:17

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {

            int count = 0, j, n, m, t, i;
            n = int.Parse(Console.ReadLine());
            int[] p_dat = new int[n];

            for (i = 0; i < n; i++)
            {
                p_dat[i] = int.Parse(Console.ReadLine());

            }
            m = int.Parse(Console.ReadLine());
            int[] s_dat = new int[m];
            for (i = 0; i < m; i++)
            {
                s_dat[i] = int.Parse(Console.ReadLine());
            }
            for (i = 0; i < n - 1; i++)
            {
                if (p_dat[i] == p_dat[i + 1])
                {
                    p_dat[i] = p_dat[i + 1];
                    i--;
                    n--;
                }

            }

            p_dat = p_dat.Distinct().ToArray();

            count = 0;
            for (i = 0; i < m; i++)
            {
                for (j = 0; j < n; j++)
                {
                    if (s_dat[i] == p_dat[j])
                    {
                        count++;
                    }
                }
            }
            Console.WriteLine(count);
            //Console.ReadKey();
        }
    }
}

Hallo,
On February 1st, 2017 I submitted a solution on Python, which was accepted with the time 0.9 sec.  Yesterday I optimised it and submitted, but got "time limit exceeded" message.  I then tried my original solution (from 01/02/2017), and it also exceeded time limit.

Questions:
1) has something changed in the methodology, or you added some new or modified old tests so it takes more time?

2) is timing dependent on the server load or each solution is tested independently on a dedicated thread? (THis may be a good question for the FAQ)

Thank you in advance.

the same c++ code was accepted when I used visual studio, but gave TLE 8 with g++ 9 (or g++ 9, C11)

Now, if you have time limit, use Buffered Reader + Hashset. It is really works.
Если вы столкнулись с Ограничением по времени, попробуйте использовать связку из Buffered Reader + Hashset. Оно реально работает!!!!
Java 1.8.0