Time Complexity of my program in competitive programming question City Plan

Question

F. City Plan

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

Problem Description: There are 𝑛 houses in one particular city that were built along one straight road. For simplicity, we can say that the 𝑖-th house is located at integer point 𝑥𝑖 (0≤𝑥𝑖≤10^9, all 𝑥𝑖 are distinct).

You are participating in one project, and you were asked to calculate for each house 𝑖 the distance 𝑑𝑖 from the 𝑖-th house to the farthest other house.

Let's say that the distance between the houses 𝑖 and 𝑘 is equal to |𝑥𝑖−𝑥𝑘|, where |𝑎| is the absolute value of 𝑎. Then 𝑑𝑖 can be calculated as max1≤𝑘≤𝑛(|𝑥𝑖−𝑥𝑘|).

Spending some time, you finally calculated all 𝑛 values 𝑑1,𝑑2,…,𝑑𝑛. But, at the same time, you've lost a piece of paper containing a list of all house positions 𝑥𝑖.

You are too lazy to measure all house positions, and you believe that actual house positions are not so important for the project. So the question is: can you create an array 𝑥1,𝑥2,…,𝑥𝑛 that is consistent with the array 𝑑 you've calculated?

Input: The first line contains a single integer 𝑡 (1≤𝑡≤10^4) — the number of test cases. Next 𝑡 cases follow.

The first line of each test case contains the single integer 𝑛 (2≤𝑛≤2⋅10^5) — the number of houses in the city.

The second line of each test case contains 𝑛 integers 𝑑1,𝑑2,…,𝑑𝑛 (1≤𝑑𝑖≤10^7), where 𝑑𝑖 is the maximum distance from house 𝑖 to some other house.

Additional constraints on the input:

• The array 𝑑 is correct, i. e. there exists at least one array 𝑥 that is consistent with array 𝑑.
• The total sum of 𝑛 among all test cases doesn't exceed 2⋅105.

Output: For each test case, print 𝑛 integers 𝑥1,𝑥2,…,𝑥𝑛 (0≤𝑥𝑖≤10^9) — the positions of houses that produce the given array 𝑑. All 𝑥𝑖 must be distinct.

If there are several solutions, print any. Note that the order of 𝑥𝑖 matters since it affects the value of 𝑑𝑖.

I wrote a solution that runs in O(n) time but I am still getting TLE. Maybe there something wrong I might be doing?? I am confused

Here is my soution

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n, maximum = -1;
    cin >> n;
    vector<int> a(n, 0);

    for (int i=0; i < n; ++i) {
        cin >> a[i];
        maximum = max(a[i], maximum);
    }

    vector<bool> mark(maximum + 1, 0);
    for (int i=0; i < n; ++i) {
        if (mark[maximum - a[i]])
            cout << 0 + a[i] << " ";
        else {
            cout << maximum - a[i] << " ";
            mark[maximum - a[i]] = 1;
        }
    }
    cout << '\n';
    return;
}   
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve(); 
    return 0;
}

Answer 1

#include <bits/stdc++.h>
#include <unordered_set>

using namespace std;

void solve() {
    int n, maximum = -1;
    cin >> n;
    int a[n];

    for (int i=0; i < n; ++i) {
        cin >> a[i];
        maximum = max(a[i], maximum);
    }

    //bool mark[maximum+1];
    // for (int i=0; i < maximum+1; ++i) 
    //  mark[i] = 0;

    unordered_set<int> mark;
    
    // vector<bool> mark(maximum + 1, 0);
    for (int i=0; i < n; ++i) {
        if (mark.count(maximum - a[i]))
            cout << a[i] << " ";
        else {
            cout << maximum - a[i] << " ";
            mark.insert(maximum - a[i]);
        }
    }
    cout << '\n';
    return;
}
    
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve(); 
    return 0;
}

I used this for submission.

When I used bool array(commented in the code) It causes a segmentation fault for the test

1
2
10000000 10000000

When I used vector<bool>(commented in the code) the code works as expected but causes TLE at 2000ms.

When I used unordered_set<int>(used in the code) the submission was successful and ran under 109 ms.

The only change in the code was the declaration of mark as bool[], vector and unordered_set and this code below

for bool[] and vector<bool> I used

for (int i=0; i < n; ++i) {
    if (mark[maximum - a[i]])
        cout << 0 + a[i] << " ";
    else {
        cout << maximum - a[i] << " ";
        mark[maximum - a[i]] = 1;
    }
}

I was still directly accessing indices after calculating maximum - a[i].

I knew vector was slow but couldn't figure out why bool[] was getting a segmentation fault.

I was sure it would work because I used the exact same logic for the bool[] and the vector<bool>. Not a single change.