Hi there,

I hope you all are doing very good. I'm trying to solve rated 1600 problems, and recently got this interactive problem: Problem Link

For solving this problem, I followed this below approach:

Step1: I decided to ask these (n-1) queries: ? index n (for all index in [1, n-1]).

Step2: Then, I created an empty array remArray of size n for storing all the (n-1) remainder values provided by the judge of each query asked by the user. Obviously, judge will return values between [0, p[n]-1] in each query.

Step3: Now, once I took all the (n-1) remainder values, I stopped asking for remainder values input. I started my implementation following the below procedure:

a) Calculating maximum value in the remainder array so that I could identify which value needs to be present at nth index in the final result. I think that value must be present at the nth index is num (num = maximumValue in remainder array + 1).

b) Then, created adjacency list of size num for storing all the values from [1, n] after performing mod with num. i.e.,

            vector<int> adjList[num];
            for(int i=1;i<=n;i++){
                int rem = i%num;
                adjList[rem].push_back(i);
            }

c) Then, stored num in result[n]

d) After that, I filled resultant array result from [1, n-1] using the values present in the adjacency list at the remArray[i] position like this:

            for(int i=1;i<=n-1;i++){
                result[i] = adjList[remArray[i]].back();
                adjList[remArray[i]].pop_back();
            }

Step4: Final step is just to print the result[] array.

I tried very hard to understand why my above approach is failing, but couldn't understand. I tried to debug it many times on various test cases, but seems correct solution for me. As this is an interactive problem, I can't take much help from problem test cases too.

int main(){
    int n;
    cin>>n;

    vector<int> result(n+1, 0);
    vector<int> remArray(n, 0);
    int query = 2*n;

    int index = 1;
    while(query--){
        cout << "? " << index << " " << n << endl;
        int modVal;
        cin>>modVal;
        cout.flush();
        if(modVal == -1){
            return 0;
        }
        remArray[index] = modVal;
        index++;
        if(index == n){
            int maxVal = *max_element(all(remArray));
            int num = maxVal+1;
            vector<int> adjList[num];
            for(int i=1;i<=n;i++){
                int rem = i%num;
                adjList[rem].push_back(i);
            }
            result[n] = num;
            for(int i=1;i<=n-1;i++){
                result[i] = adjList[remArray[i]].back();
                adjList[remArray[i]].pop_back();
            }
            cout << "! ";
            for(int i=1;i<=n;i++){
                cout << result[i] << " ";
            }
            cout << endl;
            return 0;
        }
    }
}

Kindly help me in resolving this issue. Please help me understanding why my above approach is wrong. Any help will be appreciated. Thanks in advance for your time and efforts. It means a lot to me.