#include <bits/stdc++.h> using namespace std; double n, a[100007], x; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; x = 0; for (int j = 0; j < i; j++) { if (a[i] == a[j]) { x++; break; } if (a[i] != a[j]) { x = 0; } } if (x > 0) cout << "YES" << endl; else cout << "NO" << endl; } }Hello guys, i do a task from my teacher on DM::OJ service, and there 50 tests, but my code goes through only 45. There problem: TLE (Time Limit Exceeded). If you know how to solve it, optimize > help meee )
task: "Did the number occur?" Time limit:1.0s Memory limit:64M A sequence of N numbers is given.
For each number, print "YES" if such a number has already occurred in the sequence before, otherwise print "NO".
Input format The first line contains an integer N (1≤N≤105) — the number of numbers in the sequence.
The next line contains N integer numbers Ai (1≤Ai≤109)
Answer
Your complexity is O(n*n) for nothing, it can be in O(n) just not memorizing all the read numbers but if a number was already read or not:
#include <iostream>
#define MAX_NUMBERS 105
#define MIN_VALUE 1
#define MAX_VALUE 109
int main()
{
static bool known[MAX_VALUE - MIN_VALUE + 1];
int n;
if (!(std::cin >> n) || (n < 1) || (n > MAX_NUMBERS)) {
std::cerr << "invalid number of numbers" << std::endl;
return -1;
}
else {
int x;
for (int i = 0; i != n; ++i)
{
if (!(std::cin >> x) || (x < MIN_VALUE) || (x > MAX_VALUE)) {
std::cerr << "invalid number rank " << i+1 << std::endl;
return -1;
}
std::cout << ((known[x - MIN_VALUE]) ? "YES" : "NO") << std::endl;
known[x - MIN_VALUE] = true;
}
}
return 0;
}