Repository navigation
Expand file tree
/
Copy pathnewCode.cpp
More file actions
100 lines (80 loc) · 1.54 KB
/
Copy pathnewCode.cpp
File metadata and controls
100 lines (80 loc) · 1.54 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//
// Created by Ashish Raj Singh on 26/09/26.
//
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
// --- Macros & Type Aliases ---
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
// --- Debugging (Only active on local machine) ---
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " = " << x << endl;
#else
#define debug(x)
#endif
// --- Core Logic ---
void solve() {
int n;
cin>>n;
vector<pair<int, int>> v(n);
for(int i=0;i<n;i++) {
int a;
cin>>a;
v[i]={a,i};
}
sort(all(v));
vector<ll> prefix(n);
prefix[0]=v[0].first;
for(int i=1;i<n;i++) {
prefix[i]=prefix[i-1]+v[i].first;
}
int l =0, r = n-1;
while (l<=r) {
if (l == r) {
cout<<"! "<<v[l].second+1<<endl;
return;
}
int m = l + (r-l)/2;
long long sum;
if (l == 0) {
sum = prefix[m];
} else {
sum = prefix[m] - prefix[l-1];
}
cout<<"? "<<m-l+1<<" ";
for (int i =l; i<=m; i++) cout<<v[i].second+1<<" ";
cout<<endl;
int x;
cin>>x;
if (x > sum) {
r = m;
} else {
l = m+1;
}
}
}
int main() {
fast_io;
int t = 1;
cin >> t; // Comment this out if the problem has only one test case
while (t--) {
solve();
}
return 0;
}