Solution for codeforces Forethought Future Cup - Elimination Round - C

cf_1146_tree_diam_interactive.cpp

// https://codeforces.com/contest/1146/problem/C
// To find diameter of a tree in non-interactive problem
// it would be enought to:
// 1. take a random vertex v
// 2. find the most distant from v vertex u
// 3. find the distance to the most distance from u vertex,
// this would be the answer
//
// Now, in interactive problem we want to find the most distant
// vertex from randomly chosen vertex 1.
// For that, we ask distance from 1st vertex to all others and memorize this distance
// Then we search for the index of the vertex v.
// When it is found, just return the maximum distance from v to all others.
#include <bits/stdc++.h>
using namespace std;

int ask(int v, int l, int r) {
    cout << "1 " << r - l << " " << v;
    for (int i = l; i < r; ++i)
        cout << " " << i;
    cout << endl;
    int answer;
    cin >> answer;
    if (answer == -1)
        exit(0);
    return answer;
}

int main() {
    
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    
    int t;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        int n;
        cin >> n;
        const int dist = ask(1, 2, n+1);    
        int l = 2;
        int r = n + 1;
        while (r - l > 1) {
            int m = (l + r)/2;    
            if (ask(1, l, m) == dist)
                r = m;
            else
                l = m;
        }
        
        cout << "1 " << n - 1 << " " << l;
        for (int i = 1; i <= n; ++i)
            if (i != l)
                cout << " " << i;
        cout << endl;
        int res;
        cin >> res;
        cout << "-1 " << res << endl;
        cout.flush();
    }
    
    return 0;
}