Author : shailesh_2004
Required Knowledge : Interactive, Constructive
Time Complexity :
Editorialist : shailesh_2004
Consider and are two elements of the array. If they are not equal we can find the minimum among them by posing two queries and .
Let's say
so assign because small number modulo large number is always the small number itself.
If the two elements are equal then we get results of two quries as and
Use two variables and to traverse the entire array.
Initially assign and and go on querying till the last index as
{ } and { }
If both results are 0 then append index of j to i in a vector and increment j. After you get the value at index i, fill all the values at indices which you previously appended to i.
Otherwise, fill the minimum element as discussed above.
// Author : Shailesh
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define endl "\n"
#define mod 1000000007
#define tot(a) a.begin(), a.end()
#define minii *min_element
#define maxii *max_element
void solve()
{
ll n, maxx;
cin >> n >> maxx;
ll i, j;
if (n == 1)
{
cout << "! " << maxx << endl;
cout.flush();
return;
}
i = 1;
j = 2;
ll a[n + 1];
ll yup[n + 1], prev = 0;
while (j <= n)
{
ll m1, m2;
cout << "? " << i << " " << j << endl;
cout.flush();
cin >> m1;
cout << "? " << j << " " << i << endl;
cout.flush();
cin >> m2;
if (m1 < m2)
{
a[j] = m2;
j++;
}
else if (m2 < m1)
{
a[i] = m1;
for (ll k = 0; k < prev; k++)
a[yup[k]] = a[i];
prev = 0;
i = j;
j++;
}
else
{
yup[prev] = j;
prev++;
j++;
}
}
a[i] = maxx;
for (ll k = 0; k < prev; k++)
a[yup[k]] = a[i];
cout << "! ";
for (i = 1; i <= n; i++)
cout << a[i] << " ";
cout << endl;
cout.flush();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t=1;
cin >> t;
while (t--)
solve();
return 0;
}
// Author: D.Nisritha Reddy
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define ndl "\n"
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define mod (int)(1e9 + 7)
#define F first
#define S second
#define vi vector<int>
#define vc vector<char>
#define vpi vector<pair<int,int>>
#define pi pair<int,int>
#define mi map<int, int>
#define miv map<int,vector<int>>
#define maxEle(a) *max_element(a.begin(), a.end())
#define minEle(a) *min_element(a.begin(), a.end())
#define sortAll(a) sort(a.begin(), a.end())
#define revAll(a) reverse(a.begin(), a.end())
#define sumAll(a) accumulate(a.begin(), a.end(), 0LL)
using namespace std;
int power2(int x){
int ans = 1;
while(x!=0){
ans *= 2;
x--;
}
return ans;
}
int log2(int x){
int ans = 0;
while(x>1){
x/=2; ans++;
}
return ans;
}
///////////////////////////////////////////////////////////////////////////////////////////////////
/* Interactive Question */
/* You need to find an array of size n in atmost 2n queries. The maximum element of the array is given
In each query, you give two indices i and j and you get the value of a[i]%a[j] as response
There can be repeated elements in the array */
void solve(){
int n, maxEle; cin >> n >> maxEle;
int i = 0, j = n-1;
vi res(n, -1);
map<int, vi>mp;
while(i<j){
cout <<"? "<< i+1 <<" " << j+1 <<"\n"; cout.flush();
int a1; cin >> a1;
cout <<"? "<< j+1 <<" "<< i+1 << "\n"; cout.flush();
int a2; cin >> a2;
/* a[i] == a[j] */
if(a1==a2 && a1==0){
mp[i].pb(j);
/* when the value of i is found, all the elements in mp[i] are updated with the same value */
j--;
}
/* a[i] < a[j], a[i] = a1 */
else if(a2 < a1){
res[i] = a1;
if(mp[i].empty()){
i++;continue;
}
for(auto it: mp[i])res[it] = a1;
i++;
}
/* a[i] > a[j], a[j] = a2 */
else{
res[j] = a2; j--;
}
}
res[i] = maxEle;
if(!mp[i].empty()){
for(auto it: mp[i])res[it] = maxEle;
}
cout <<"! ";
for(int x: res){
cout << x<<" "; cout.flush();
}
cout <<"\n"; cout.flush();
}
///////////////////////////////////////////////////////////////////////////////////////////////////
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1; cin>>t;
while(t--){
solve();
}
}
// Author : Naveen
// Program Start
// Libraries and Namespace Start
#include <bits/stdc++.h>
using namespace std;
// Libraries and Namespace End
//----------------------------------------------------------------
// Important Shortcuts Start
// Macros Start
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(), v.end()
// Macros End
// Declarations Start
typedef long long int ll;
typedef vector<ll> vll;
// Declarations End
// Constants Start
const char spc = ' ';
const char newl = '\n';
// Constants End
// Disjoint Set Union Start
class DisjointSet {
private:
vll parent, depth, set_size, max_set, min_set;
ll num_sets, max_size;
public:
DisjointSet() {}
DisjointSet(ll n, ll start = 1) {
init(n, start);
}
DisjointSet(const DisjointSet& obj) : parent(all(obj.parent)), depth(all(obj.depth)), set_size(all(obj.set_size)), min_set(all(obj.min_set)), max_set(all(obj.max_set)), max_size(obj.max_size), num_sets(obj.num_sets) {}
void init(ll n, ll start = 1) {
num_sets = n;
max_size = 1;
n += start;
parent.assign(n, 0);
max_set.assign(n, 0);
min_set.assign(n, 0);
for (ll i = start; i < n; ++i) {
parent[i] = max_set[i] = min_set[i] = i;
}
depth.assign(n, 0);
set_size.assign(n, 1);
}
ll find_set(ll n) {
return parent[n] = (parent[n] == n ? n : find_set(parent[n]));
}
ll find_set(ll n, bool p) {
stack<ll> st;
ll v;
while (n != parent[n]) {
st.push(n);
n = parent[n];
}
while (!st.empty()) {
v = st.top();
st.pop();
parent[v] = n;
}
return n;
}
bool is_same_set(ll a, ll b) {
return find_set(a) == find_set(b);
}
void union_set(ll a, ll b) {
ll x = find_set(a), y = find_set(b);
if (x == y) {
return;
}
if (depth[x] > depth[y]) {
swap(x, y);
}
if (depth[x] == depth[y]) {
depth[y]++;
}
parent[x] = y;
set_size[y] += set_size[x];
max_size = max((ll)max_size, (ll)set_size[y]);
min_set[y] = min(min_set[y], min_set[x]);
max_set[y] = max(max_set[y], max_set[x]);
num_sets--;
}
ll num_of_sets() {
return num_sets;
}
ll size_of_set(ll n) {
return set_size[find_set(n)];
}
ll max_of_set(ll n) {
return max_set[find_set(n)];
}
ll min_of_set(ll n) {
return min_set[find_set(n)];
}
ll max_size_of_sets() {
return max_size;
}
};
// Disjoint Set Union End
//----------------------------------------------------------------
// Solution Class Start
class Solution {
public:
void solve(ll index) {
//----------------------------------------------------------------
ll n, m, i, j, k;
cin >> n >> m;
if (n == 1) {
cout << "! " << m << endl;
fflush(stdout);
return;
}
vll arr(n + 1, -1);
DisjointSet d(n);
i = 1;
ll inx1 = 1, inx2;
for (j = 1;j <= n;j++) {
inx2 = j % n + 1;
cout << "? " << inx1 << " " << inx2 << endl;
fflush(stdout);
ll r1, r2;
cin >> r1;
cout << "? " << inx2 << " " << inx1 << endl;
fflush(stdout);
cin >> r2;
if (r1 == r2) {
d.union_set(inx1, inx2);
inx1 = inx2;
}
else if (r1 < r2) {
arr[inx2] = r2;
}
else {
arr[inx1] = r1;
inx1 = inx2;
}
}
for (i = 1;i <= n;i++) {
if (arr[i] != -1) {
arr[d.find_set(i)] = arr[i];
}
}
for (i = 1;i <= n;i++) {
if (arr[i] == -1) {
arr[i] = arr[d.find_set(i)];
if (arr[i] == -1) {
arr[i] = m;
arr[d.find_set(i)] = m;
}
}
}
cout << "! ";
for (i = 1;i < arr.size();i++) {
cout << arr[i] << spc;
}
cout << endl;
fflush(stdout);
// cout << "Case #" << index << ": " << ans << newl;
//----------------------------------------------------------------
}
bool test_cases = true;
};
// Solution Class End
// Main Function Start
int main() {
Solution sol;
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ll test_cases = 1;
if (sol.test_cases) {
cin >> test_cases;
}
for (ll test_case = 1; test_case <= test_cases; ++test_case) {
sol.solve(test_case);
}
return 0;
}
// Main Function End
// Program End
//----------------------------------------------------------------