• Great:
• Good:
• Average:
• Bad:
• Trash:

• D2A:
• D2B:
• D1A:
• D1B:
• D1C1:
• D1C2:
• D1C3:
• D1D:
• D1E:
• D1F1:
• D1F2:

• D2A:
• D2B:
• D1A:
• D1B:
• D1C1:
• D1C2:
• D1C3:
• D1D:
• D1E:
• D1F1:
• D1F2:

Do you know the source of the title?

Assuming that choosing $$$\text{mex(S')}$$$ is optimal, what conditions does $$$S'$$$ need to satisfy?

Are there duplicate numbers in $$$S'$$$? Is there a number greater than $$$\text{mex(S')}$$$ in $$$S'$$$?

Assuming that choosing $$$\text{mex(S')}$$$ is optimal, there are no duplicate numbers in $$$S'$$$. And thers is not a number greater than $$$\text{mex(S')}$$$. Otherwise, we can easily construct a better answer.

Consider $$$\text{S={0,1,...,x}}$$$. We can see $$$\text{mex(S')} \gt \text{max(S')}$$$ when $$$x$$$ is $$$0$$$ or $$$1$$$. And $$$\text{mex({0,1})}=\text{mex({0})}+\text{sum({1})}$$$. Thus, we only use $$$\text{mex}$$$ operation for each single $$$0$$$.

The answer is $$$\text{sum(S)}$$$ add the number of $$$0$$$ in $$$S$$$.

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n, tmp, ans = 0;
    cin >> n;
    for(int i=0; i<n; i++){cin >> tmp; ans += tmp + (tmp == 0);}
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Casework. Consider two easy cases first: $$$\Sigma a \gt s$$$ and $$$\Sigma a=s$$$.

What if there is an index $$$i$$$ such that $$$a_i+a_{i+1}=1$$$?

To "block" $$$a_i+a_{i+1}=1$$$, what should Bob do?

Consider cases of $$$\Sigma a=s+1$$$ and $$$\Sigma a \gt s+1$$$.

The minimum path sum is the sum of the simple path from $$$1$$$ to $$$n$$$ (i.e., $$$1 \rightarrow 2 \rightarrow \dots \rightarrow n$$$), denoted as $$$\text{base_sum} = \sum_{i=1}^{n} a_i$$$.

The path can include back-and-forth movements (e.g., from $$$i$$$ to $$$i+1$$$ and back to $$$i$$$), which increases the path length and the path sum. Specifically, each back-and-forth movement between adjacent positions $$$(i, i+1)$$$ adds $$$a_i + a_{i+1}$$$ to the path sum.

Thus, the total path sum can be expressed as $$$\text{base_sum} + d$$$, where $$$d$$$ is the additional sum contributed by zero or more back-and-forth movements. Here, $$$d$$$ can be represented as a non-negative integer linear combination of the sums of adjacent pairs.

Casework:

• If $$$s \lt \text{base_sum}$$$, no path sum can equal $$$s$$$ (since the base sum already exceeds $$$k$$$, and any additional movements will further increase the sum).

• If $$$s = \text{base_sum}$$$, the simple path ($$$1 \rightarrow 2 \rightarrow \dots \rightarrow n$$$) already satisfies the condition, so Alice cannot be stopped.

• If $$$s \gt \text{base_sum}$$$, let $$$d = s - \text{base_sum}$$$:

  • If $$$d = 1$$$, we can rearrange the array to avoid adjacent pairs summing to $$$1$$$ (i.e., avoid $$$0$$$ and $$$1$$$ being adjacent). Specifically, place all $$$0$$$s first, followed by all $$$2$$$s, and then all $$$1$$$s (e.g., $$$[0, 0, \dots, 0, 2, 2, \dots, 2, 1, 1, \dots, 1]$$$). This ensures no adjacent pair sums to $$$1$$$, making $$$d = 1$$$ unachievable.
  • If $$$d \neq 1$$$, no rearrangement can prevent Alice from achieving the path sum $$$s$$$ (since sums of adjacent pairs can cover all $$$T \geq 2$$$ through linear combinations).

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n, k, tmp;
    cin >> n >> k;
    vector<int> a(3);
    for(int i=0; i<n; i++){cin >> tmp; a[tmp]++;}
    if(k == a[1] + 2*a[2] || k >= a[1] + 2*a[2] + 2){cout << -1 << '\n'; return;}
    for(int i=0; i<a[0]; i++) cout << 0 << ' ';
    for(int i=0; i<a[2]; i++) cout << 2 << ' ';
    for(int i=0; i<a[1]; i++) cout << 1 << ' ';
    cout << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Assuming that choosing $$$S$$$ is optimal, what is the value of $$$g(S)$$$?

In the case of $$$g(S)=0$$$, make $$$f(S)$$$ the length of the union of the entire set.

Assuming that choosing $$$S$$$ is optimal, $$$g(S)$$$ must be $$$0$$$ because removing an edge on the cycle will not change $$$f(S)$$$.

In the case of $$$g(S)=0$$$, we need to make $$$f(S)$$$ the length of the union of the entire set. There are many approaches.

An easiest $$$O(n^2)$$$ approach is to remove all segments contained by other segments. Afterwards, it can be proven that there are no cycles with a length greater than or equal to $$$3$$$ in the graph. If there is a cycle, note it as $$$x_1 \rightarrow x_2 \rightarrow x_3 \rightarrow ... \rightarrow x_1$$$, we can always find $$$x_{i-1} \lt x_i \gt x_{i+1}$$$, where either $$$[x_{i-1},x_i] \subseteq [x_i,x_{i+1}]$$$ or $$$[x_i,x_{i+1}] \subseteq [x_{i-1},x_i]$$$. At this point, we have deduced the contradiction, so there are no cycles with a length greater than or equal to $$$3$$$ in the graph.

Another approach is to use DSU to maintain the generate forest.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
int T,n;
int a[N],b[N];

void init()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i];
}

void solve()
{
    vector<int> tag(n+4,1),ans;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            if(a[j]<=a[i]&&b[i]<=b[j]) tag[i]=0;
        }
        if(tag[i]) ans.push_back(i);
    }
    cout<<ans.size()<<"\n";
    for(int i=0;i<ans.size();i++)
        cout<<ans[i]<<(i+1==ans.size()?"\n":" ");
}

int main()
{
    fastio;

    cin>>T;
	while(T--)
	{
		init();
		solve();
	}

	return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Try to switch to the dark mode and read the statement.

Consider $$$p_i=1$$$. If $$$a_i=1$$$, what are inversions containing $$$i$$$? If $$$a_i=2n-1$$$, what are inversions containing $$$i$$$?

Attempt to generalize the conclusion to any pair $$$(i, j)$$$.

Consider $$$p_i=1$$$ and inversions containing $$$i$$$. If $$$a_i=1$$$, it is the minimum value, and the inversions containing $$$i$$$ are $$$(1, i), (2, i),... (i-1, i)$$$; If $$$a_i=2n-1$$$, it is the maximum value, and the inversions containing $$$i$$$ are $$$(i, i+1),... (i, n)$$$. The key observation is the number of inversions containing $$$i$$$ is only related to $$$a_i$$$, and completely unrelated to other elements.

At this point, the problem has actually been solved. We can greedily choose $$$\min(i-1,n-i)$$$ and remove $$$1$$$ from $$$p$$$, and the remaining part is a completely identical subproblem with a size of $$$n-1$$$.

It can be implemented as follows: for each index $$$i$$$, calculate the number of elements to the left that are bigger than $$$p_i$$$ (note it as $$$lbigger$$$), and the number of elements to the right that are bigger than $$$p_i$$$ (note it as $$$rbigger$$$). Then greedily add $$$\min(lbigger,rbigger)$$$ to the answer.

#include <bits/stdc++.h>
using namespace std;

void solve(){
    int n, ans = 0;
    cin >> n;
    vector<int> p(n);
    for(int i=0; i<n; i++) cin >> p[i];
    for(int i=0; i<n; i++){
        int left = 0, right = 0;
        for(int j=0; j<i; j++) if(p[j] > p[i]) left++;
        for(int j=i+1; j<n; j++) if(p[j] > p[i]) right++;
        ans += min(left, right);
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--) solve();
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Try to Perform binary search to find a $$$\texttt{'('}$$$ and a $$$\texttt{')'}$$$ using $$$O(\log n)$$$ queries. It is best to complete it within $$$10$$$ operations (to pass the hard version).

Consider the easy version. Constraint implies that we use one query to determine $$$2$$$ characters.

Construct a string $$$x$$$, insert $$$s_i$$$ and $$$s_j$$$ into certain positions of $$$x$$$ to obtain string $$$y$$$, so that $$$f(y)$$$ can produce $$$4$$$ different values.

Consider the medium version. Effectively utilizing the conditions of $$$k \le 1000$$$.

Consider binary code.

Consider the hard version. The number of substrings in a string of length $$$l$$$ is $$$O(l ^ 2)$$$. How to utilize this?

At first, we need to find $$$s_x=\texttt{’(’}$$$ and $$$s_y=\texttt{’)’}$$$. Do binary search to find the smallest $$$i$$$ such that $$$f(s_1s_2...s_i) \gt 0$$$. Then we get $$$s_{i-1}=\texttt{’(’}$$$ and $$$s_i=\texttt{’)’}$$$. A corner case is $$$f(s)=0$$$. In this case, $$$s_n=\texttt{’(’}$$$ and $$$s_1=\texttt{’)’}$$$.

Ask $$$f(\texttt{"s1)s2)()"})$$$:

• If $$$f(\texttt{"s1)s2)()"})=6$$$, $$$s_1=$$$ $$$\texttt{'('}$$$ and $$$s_2=$$$ $$$\texttt{'('}$$$.

• If $$$f(\texttt{"s1)s2)()"})=2$$$, $$$s_1=$$$ $$$\texttt{'('}$$$ and $$$s_2=$$$ $$$\texttt{')'}$$$.

• If $$$f(\texttt{"s1)s2)()"})=3$$$, $$$s_1=$$$ $$$\texttt{')'}$$$ and $$$s_2=$$$ $$$\texttt{'('}$$$.

• If $$$f(\texttt{"s1)s2)()"})=1$$$, $$$s_1=$$$ $$$\texttt{')'}$$$ and $$$s_2=$$$ $$$\texttt{')'}$$$.

In this way, we can determine two characters with one query.

Read the tutorial in easy version first.

Note $$$f_0$$$ as the $$$f$$$ value of the following string:

$$$\underbrace{()()\ldots()}_{128 pairs}$$$ $$$)$$$ $$$\underbrace{()()\ldots()}_{64 pairs}$$$ $$$)$$$ $$$\dots$$$ $$$)()$$$

Then ask for the $$$f$$$ value of the following string (note it as $$$f_1$$$):

$$$\underbrace{s_8)()\ldots()}_{128 pairs}$$$ $$$)$$$ $$$\underbrace{s_7)()\ldots()}_{64 pairs}$$$ $$$)$$$ $$$\dots$$$ $$$)s_1)$$$

By checking the binary bits of $$$f_0-f_1$$$, we can determine $$$8$$$ positions with one query. For example, if $$$f_0-f_1=(10000101)_2$$$, we can get $$$s_1=s_3=s_8='('$$$.

Read the tutorial of the medium version first.

We can optimize

$$$\underbrace{s_i)()\ldots()}_{2^k pairs}$$$

to

$$$\underbrace{()()\ldots()}_{2^{\lfloor \frac{k}{2} \rfloor}-1\ pairs}$$$ $$$s_i)$$$ $$$\underbrace{()()\ldots()}_{2^{\lceil \frac{k}{2} \rceil}-1\ pairs}$$$

With this optimization, we can determine $$$12$$$ locations in one query.

Another construction also works:

$$$\underbrace{s_1)s_1)\ldots s_1)}_{g(1)\ pairs}$$$ $$$)$$$ $$$\underbrace{s_2)s_2)\ldots s_2)}_{g(2)\ pairs}$$$ $$$)$$$ $$$\underbrace{s_3)s_3)\ldots s_3)}_{g(3)\ pairs}$$$ $$$)$$$ $$$\ldots$$$ $$$\underbrace{s_{12})s_{12})\ldots s_{12})}_{g(12)\ pairs}$$$

where $$$g(i) \gt g(1)+g(2)+\ldots+g(i-1)$$$.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

typedef long long       ll;
typedef long double     ld;
typedef pair<ll, ll>   pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

const long long kk = 1000;
const long long ml = kk * kk;
const long long mod = ml * kk + 7;
const long long inf = ml * ml * ml + 7;

#define T(x, i) get<i>(x)
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define forn(i, n) for (int i = 0; i < n; i++)

template<class T, class U> inline istream& operator>>(istream& str, pair<T, U> &p) { return str >> p.F >> p.S; }
template<class T, class U> inline ostream& operator<<(ostream& str, const pair<T, U> &p) { str << p.F << ' ' << p.S << ' '; return str; }
template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; }
template<class T> inline ostream& operator<<(ostream& str, const vector<T> &a) { for (auto &i : a) str << i << ' '; return str; }

void flush() { cout << flush; }
void flushln() { cout << endl; }
template<class T> void read(T &x) { cin >> x; }
template<class T, class ...U> void read(T &x, U&... u) { read(x); read(u...); }
template<class T> void print(const T &x) { cout << x; }
template<class T, class ...U> void print(const T &x, const U&... u) { print(x); print(u...); }
template<class ...T> void println(const T&... u) { print(u..., '\n'); }
template<class T> void eprint(const T &x) { cerr << x; }
template<class T, class ...U> void eprint(const T &x, const U&... u) { eprint(x); eprint(u...); }
template<class ...T> void eprintln(const T&... u) { eprint(u..., '\n'); }

#ifdef DEBUG
	mt19937 rng(1033);
	#define var(x) cerr << #x << ": " << x << '\n';
	#define range(a, b) cerr << #a << ", " << #b << ": "; for (auto _it = a; _it != b; ++_it) cerr << *_it << ' '; cerr << '\n';
#else
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	#define cerr if (false) cerr
	#define var(x)
	#define range(a, b)
	#define eprintln if(false)eprintln
	#define eprint if(false)eprint
#endif
int rnd(int mod) { return uniform_int_distribution<int>(0, mod - 1)(rng); }


int n;

map<vector<int>, int> mem;

int ask(vector<int> ind) {
	if (!mem.count(ind)) {
		cout << "? ";
		cout << ind.size() << ' ';
		for (auto i : ind)
			cout << i + 1 << ' ';
		cout << endl;

		int res;
		cin >> res;
		mem[ind] = res;
	}

	return mem[ind];
}


bool same(vector<int> ind) {
	if (ask(ind))
		return false;
	ind.push_back(ind[0]);
	ind.erase(ind.begin());
	if (ask(ind))
		return false;
	return true;
}

pii search(vector<int> ind) {
	if (ind.size() == 2) {
		if (ask(ind))
			return {ind[0], ind[1]};
		return {ind[1], ind[0]};
	}

	vector<int> inda, indb;
	int sz = (ind.size() + 1) / 2;
	for (int i = 0; i < sz; i++) {
		inda.push_back(ind[i]);
		indb.push_back(ind[ind.size() - 1 - i]);
	}

	if (!same(inda))
		return search(inda);
	if (!same(indb))
		return search(indb);
	inda.push_back(indb[0]);
	return search(inda);
}

pii find_reg2() {
	vector<int> ind(n);
	iota(all(ind), 0);
	shuffle(all(ind), rng);
	return search(ind);
}

void solve() {
	mem.clear();
	auto [po, pc] = find_reg2();

	vector<int> to_ask(n);
	iota(all(to_ask), 0);
	if (to_ask.size() & 1)
		to_ask.push_back(0);


	string ans = string(n, '.');
	ans[po] = '(';
	ans[pc] = ')';
		
	for (int i = 0; i < to_ask.size(); i += 2) {
		int a = to_ask[i], b = to_ask[i + 1];

		vector<int> q = {po, pc, po, a, b, pc};
		int res = ask(q);

		// ()(ab) - x ab
		// ()(()) - 4 ()
		// ()((() - 2 ((
		// ()())) - 3 ))
		// ()()() - 6 )(
		map<int, pair<char, char>> results = {
			{4, {'(', ')'}},
			{2, {'(', '('}},
			{3, {')', ')'}},
			{6, {')', '('}},
		};

		assert(results.count(res));
		auto [resa, resb] = results[res];
		ans[a] = resa;
		ans[b] = resb;
	}

	cout << "! " << ans << endl;
}

signed main() {
	#ifdef DEBUG
	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0);
	cout << fixed << setprecision(20);
	int t = 1;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		solve();
	}
	#ifdef DEBUG
		cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
	#endif
}


/*


()(ab)
()(()) - 4 ()
()((() - 2 ((
()())) - 3 ))
()()() - 6 )(

2
3
)((
2
()


*/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
 
using namespace std;
 
#define _int64 long long
#define mo 998244353

char tar[110000];
int cnt;

int doask(vector<int>& a)
{
	int i,ret;
	/*
	{
		int v,tmp,j;
		string ss;
		cnt++;
		ss="";
		for (i=0;i<a.size();i++)
		{
			ss.push_back(tar[a[i]]);
		}
		tmp=0;
		for (i=0;i<ss.length();i++)
		{
			v=0;
			for (j=i;j<ss.length();j++)
			{
				if (ss[j]=='(') v++;
				else v--;
				if (v<0) break;
				if (v==0) tmp++;
			}
		}
		return tmp;
	}
	*/
	
	printf("? %d",(int)a.size());
	for (i=0;i<a.size();i++)
		printf(" %d",a[i]+1);
	printf("\n");
	fflush(stdout);
	scanf("%d",&ret);
	return ret;
	
}

char ans[1100];

void doanswer()
{
	printf("! %s\n",ans);
	cerr<<"T "<<tar<<endl;
	cerr<<"cnt:"<<cnt<<endl;
	if (string(ans)==string(tar))
	{
		cerr<<"good"<<endl;
	}
	else cerr<<"bad"<<endl;
	fflush(stdout);
}

int main()
{
	int i,j,k,n,l,t,m,x,y,o,b1,indl,indr,ll,rr,mid,tmp,v,st;
	vector<int> a;
	scanf("%d",&t);
	for (l=0;l<t;l++)
	{
		scanf("%d",&n);
		for (i=0;i<n;i++)
		{
			x=rand()%2;
			if (x==0) tar[i]='(';
			else tar[i]=')';
		}
		tar[n]='\0';
		cnt=0;
		st=0;ans[n]='\0';
		indl=-1;
		indr=-1;
		// while (st<n)
		// {
			ll=st;rr=n;
			while (rr-ll>1)
			{
				mid=(ll+rr)/2;
				a.clear();
				for (i=st;i<=mid;i++)
					a.push_back(i);
				tmp=doask(a);
				if (tmp==0) ll=mid;
				else rr=mid;
			}
			if (rr==n)
			{
				indr=st;
				/*
				if ((indl==-1)&&(indr==-1))
				{
					indr=st;
				}
				ll=st-1;rr=n;
				while (rr-ll>1)
				{
					mid=(ll+rr)/2;
					a.clear();
					a.push_back(mid);
					a.push_back(indr);
					tmp=doask(a);
					if (tmp==0) ll=mid;
					else rr=mid;
				}
				for (i=st;i<=ll;i++)
					ans[i]=')';
				for (i=rr;i<n;i++)
					ans[i]='(';
				st=n;
				break;
				*/
			}
			else
			{
				indr=rr;
				/*
				v=rr;
				ans[v]=')';
				ll=st-1;rr=v-1;
				while (rr-ll>1)
				{
					mid=(ll+rr)/2;
					a.clear();
					a.push_back(mid);
					a.push_back(v);
					tmp=doask(a);
					if (tmp==0) ll=mid;
					else rr=mid;
				}
				for (i=st;i<=ll;i++)
					ans[i]=')';
				for (i=rr;i<v;i++)
					ans[i]='(';
				st=v+1;
				indl=v-1;
				indr=v;
				*/
			}
		// }
		//cerr<<"indr:"<<indr<<endl;
		for (i=0;i<n;i+=8)
		{
			a.clear();
			for (j=0;j<8;j++)
			{
				if (i+j>=n) break;
				for (k=0;k<(1<<j);k++)
				{
					a.push_back(i+j);
					a.push_back(indr);
					a.push_back(indr);
				}
			}
			tmp=doask(a);
			for (j=0;j<8;j++)
			{
				if (i+j>=n) break;
				if (((1<<j)&tmp)!=0) ans[i+j]='(';
				else ans[i+j]=')';
			}
		}

		doanswer();
	}
}

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
 
using namespace std;
 
#define _int64 long long
#define mo 998244353

char tar[110000];
int cnt;

int doask(vector<int>& a)
{
	int i,ret;
	/*
	{
		int v,tmp,j;
		string ss;
		cnt++;
		ss="";
		for (i=0;i<a.size();i++)
		{
			ss.push_back(tar[a[i]]);
		}
		tmp=0;
		for (i=0;i<ss.length();i++)
		{
			v=0;
			for (j=i;j<ss.length();j++)
			{
				if (ss[j]=='(') v++;
				else v--;
				if (v<0) break;
				if (v==0) tmp++;
			}
		}
		return tmp;
	}
	*/
	
	printf("? %d",(int)a.size());
	for (i=0;i<a.size();i++)
		printf(" %d",a[i]+1);
	printf("\n");
	fflush(stdout);
	scanf("%d",&ret);
	return ret;
	
}

char ans[1100];

void doanswer()
{
	printf("! %s\n",ans);
	cerr<<"T "<<tar<<endl;
	cerr<<"cnt:"<<cnt<<endl;
	if (string(ans)==string(tar))
	{
		cerr<<"good"<<endl;
	}
	else cerr<<"bad"<<endl;
	fflush(stdout);
}

int main()
{
	int i,j,k,n,l,t,m,x,y,o,b1,indl,indr,ll,rr,mid,tmp,v,st,sum,len;
	vector<int> a;
	vector<int> p;
	sum=0;len=0;
	for (i=1;i<=130;i++)
	{
		tmp=i*(i+1)/2;
		if (tmp>sum)
		{
			p.push_back(i);
			//cerr<<"i:"<<i<<endl;
			sum+=tmp;
			len+=i+i;
		}
	}
	//cerr<<"p.sz:"<<p.size()<<" "<<len<<endl;
	scanf("%d",&t);
	for (l=0;l<t;l++)
	{
		scanf("%d",&n);
		for (i=0;i<n;i++)
		{
			x=rand()%2;
			if (x==0) tar[i]='(';
			else tar[i]=')';
		}
		tar[n]='\0';
		cnt=0;
		st=0;ans[n]='\0';
		indl=-1;
		indr=-1;
		// while (st<n)
		// {
			ll=st;rr=n;
			while (rr-ll>1)
			{
				mid=(ll+rr)/2;
				a.clear();
				for (i=st;i<=mid;i++)
					a.push_back(i);
				tmp=doask(a);
				if (tmp==0) ll=mid;
				else rr=mid;
			}
			if (rr==n)
			{
				indr=st;
				/*
				if ((indl==-1)&&(indr==-1))
				{
					indr=st;
				}
				ll=st-1;rr=n;
				while (rr-ll>1)
				{
					mid=(ll+rr)/2;
					a.clear();
					a.push_back(mid);
					a.push_back(indr);
					tmp=doask(a);
					if (tmp==0) ll=mid;
					else rr=mid;
				}
				for (i=st;i<=ll;i++)
					ans[i]=')';
				for (i=rr;i<n;i++)
					ans[i]='(';
				st=n;
				break;
				*/
			}
			else
			{
				indr=rr;
				/*
				v=rr;
				ans[v]=')';
				ll=st-1;rr=v-1;
				while (rr-ll>1)
				{
					mid=(ll+rr)/2;
					a.clear();
					a.push_back(mid);
					a.push_back(v);
					tmp=doask(a);
					if (tmp==0) ll=mid;
					else rr=mid;
				}
				for (i=st;i<=ll;i++)
					ans[i]=')';
				for (i=rr;i<v;i++)
					ans[i]='(';
				st=v+1;
				indl=v-1;
				indr=v;
				*/
			}
		// }
		//cerr<<"indr:"<<indr<<endl;
		for (i=0;i<n;i+=p.size())
		{
			a.clear();
			for (j=0;j<p.size();j++)
			{
				if (i+j>=n) break;
				for (k=0;k<p[j];k++)
				{
					a.push_back(i+j);
					a.push_back(indr);
				}
				a.push_back(indr);
			}
			tmp=doask(a);
			for (j=p.size()-1;j>=0;j--)
			{
				if (i+j>=n) continue;
				v=p[j]*(p[j]+1)/2;
				if (tmp>=v)
				{
					tmp-=v;ans[i+j]='(';
				}
				else ans[i+j]=')';
			}
		}

		doanswer();
	}
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Consider enumerating $$$p_i = 1$$$. After that, will the cells to the left of $$$p_i$$$ affect the cells to the right of $$$p_i$$$?

Consider range DP.

Can you find the upper bound of $$$s_i$$$?

Consider range DP.

Note $$$dp[l][r][x][y]$$$ as the number of scheme ensureing $$$s[l-1]+=x$$$ and $$$s[r+1]+=y$$$.

Transform:

For simplicity, this formula omits some edge cases. Readers are encouraged to fill in the details themselves.

The complexity seems high, but the problem can be solved with one key observation: the upper bound of $$$s_i$$$ is $$$O( \log n)$$$.

Proof: let's fix a position $$$i$$$ and only consider the cells $$$c_1, c_2, ..., c_k$$$ $$$(c_1 \lt c_2 \lt ... \lt c_k)$$$ to the left of $$$i$$$ that cause $$$s_i$$$ to increase. We can see that $$$i - c_j \gt 2(i - c_{j+1})$$$. Otherwise, $$$c_{j+1}$$$ would cause $$$s_{c_j}$$$ to increase by $$$1$$$ instead of $$$s_i$$$. Thus, We can get $$$k$$$ is $$$O( \log n)$$$.

Complexity: $$$O(n^3 \log^3n)$$$.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=110;
const int LOGN=10;
const ll  TMD=998244353;
const ll  INF=2147483647;
int T,n;
ll s[N],fac[N],inv[N];
ll dp[N][N][LOGN][LOGN];

void init_C()
{
	fac[0]=1;
	for(int i=1;i<N;i++) fac[i]=(fac[i-1]*i)%TMD;
	inv[N-1]=pw(fac[N-1],TMD-2);
 	for(int i=N-2;i>=0;i--) inv[i]=(inv[i+1]*(i+1))%TMD;
}

ll C(int n,int m)
{
	if(n<m||n<0||m<0) return 0;
	return fac[n]*inv[m]%TMD*inv[n-m]%TMD;
}

void init()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n+4;i++)
        for(int j=1;j<=n+4;j++)
            for(int ii=0;ii<LOGN;ii++)
                for(int jj=0;jj<LOGN;jj++)
                    dp[i][j][ii][jj]=0;
    dp[1][1][0][1]=(s[1]<1);
    for(int i=2;i<=n;i++)
        dp[i][i][1][0]=(s[i]<1);
    for(int i=1;i<=n;i++)   //auxiliary value
        dp[i][i-1][0][0]=dp[i+1][i][0][0]=1;
}

int ABS(int x)
{
    return x<0?-x:x;
}

void solve()
{
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j+i-1<=n;j++)
        {
            for(int ii=0;ii<LOGN;ii++)
            {
                for(int jj=0;jj<LOGN;jj++)
                {
                     int l=j,r=j+i-1;
                     for(int k=l;k<=r;k++)
                     {
                         int tagl=0,tagr=0;
                         if(l==1&&r==n) tagl=tagr=0;
                         else if(l==1) tagr=1;
                         else if(r==n) tagl=1;
                         else
                         {
                             if(ABS(l-1-k)<=ABS(k-(r+1))) tagl=1;
                             else tagr=1;
                         }
                         if(ii-tagl<0||jj-tagr<0) continue;
                         if(s[k]==-1)
                         {
                             ll suml=0,sumr=0;
                             for(int kk=0;kk<LOGN;kk++) suml=(suml+dp[l][k-1][ii-tagl][kk])%TMD;
                             for(int kk=0;kk<LOGN;kk++) sumr=(sumr+dp[k+1][r][kk][jj-tagr])%TMD;
                            dp[l][r][ii][jj]=(dp[l][r][ii][jj]+suml*sumr%TMD*C(r-l,k-l))%TMD;
                        }
                         else
                         {
                             for(int kk=0;kk<LOGN;kk++)
                             {
                                 if(s[k]-kk<0||s[k]-kk>=LOGN) continue;
                                 dp[l][r][ii][jj]=(dp[l][r][ii][jj]+dp[l][k-1][ii-tagl][kk]*dp[k+1][r][s[k]-kk][jj-tagr]%TMD*C(r-l,k-l))%TMD;
                             }
                         }
                     }
                }
            }
        }
    }
    cout<<dp[1][n][0][0]<<'\n';
}

int main()
{
    fastio;

    init_C();

    cin>>T;
	while(T--)
	{
		init();
		solve();
	}

	return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Find the nature of the problem and recall the data structures and algorithms learned. What can we utilize?

Consider a standard Mo's algorithm. Why it doesn't work in this problem?

Recalling the Handshake Theorem: $$$\Sigma_{i=1}^n degree_i=2m$$$.

Consider a variation of Mo's algorithm.

How to find the $$$k$$$-th smallest value without $$$O( \log n)$$$ complexity?

We found that merging the $$$f$$$ values of two intervals is a bit difficult. However, if we want to add a single node to the graph, it is relatively easy to update the $$$f$$$ value using brute force. This inspires us to use the Mo's algorithm.

If we use the standard Mo's Algorithm, when expanding the interval from $$$[l, r]$$$ to $$$[l, r+1]$$$, we need to examine all edges connected to $$$r+1$$$ and update the node degrees accordingly. We define a cost array: $$$cost_i=degree_i+1$$$. The cost of update node $$$r+1$$$ is $$$cost_{r+1}$$$.

However, if a node has a high degree, repeatedly processing it in Mo's Algorithm could lead to big time complexity.

We leverage the Handshaking Lemma to use modified Mo's Algorithm to efficiently handle the queries.

Recall that the Mo's algorithm relatively evenly divides array indices into blocks according to array length and assigns block numbers. Here, our dividinging strategy is different: we "relatively evenly" divide the array into blocks based on the prefix sum value of the $$$cost$$$ array. Specifically, we calculate the prefix sum of the cost array $$$precost$$$, using $$$\frac{precost_i}{B}$$$ as the block number of node $$$i$$$, where $$$B$$$ is the block length parameter.

Assuming we have a data structure that can maintain the value of $$$k$$$-th smallest value in $$$O(1)$$$, using the same analysis method as standard Mo's algorithm, we can get the complexity is $$$O((n+m+q)\sqrt{n+m})$$$.

To find the $$$k$$$-th smallest value without $$$O( \log n)$$$ complexity, we only need to maintain two arrays $$$cnt$$$ and $$$sum$$$, where $$$cnt_i$$$ is the occurrence of value $$$i$$$, and $$$sum_i=\Sigma_{j=(i-1)B+1}^{iB}cnt_j$$$ ($$$B$$$ is the block length parameter). We can perform modification in $$$O(1)$$$ and query in $$$O(\sqrt{n})$$$. The complexity is $$$O((n+q)\sqrt{n})$$$.

Regarding implementation, you need to pay attention to two common pitfalls:

• If you use $$$cost_i=degree_i$$$ instead of $$$cost_i=degree_i+1$$$, the dividing algorithm doesn't work for the graph with many nodes with degree $$$0$$$.

• Similarly, you can not set $$$B=\sqrt{m}$$$.

#include<bits/stdc++.h>
using namespace std;

#define all(a) a.begin(),a.end()
#define pb push_back
#define sz(a) ((int)a.size())

using ll=long long;
using u32=unsigned int;
using u64=unsigned long long;
using i128=__int128;
using u128=unsigned __int128;
using f128=__float128;

using pii=pair<int,int>;
using pll=pair<ll,ll>;

template<typename T> using vc=vector<T>;
template<typename T> using vvc=vc<vc<T>>;
template<typename T> using vvvc=vc<vvc<T>>;

using vi=vc<int>;
using vll=vc<ll>;
using vvi=vc<vi>;
using vvll=vc<vll>;

#define vv(type,name,n,...) \
    vector<vector<type>> name(n,vector<type>(__VA_ARGS__))
#define vvv(type,name,n,m,...) \
    vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__)))

template<typename T> using min_heap=priority_queue<T,vector<T>,greater<T>>;
template<typename T> using max_heap=priority_queue<T>;

// https://trap.jp/post/1224/
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s)))

template<typename T, typename S> constexpr T ifloor(const T a, const S b){return a/b-(a%b&&(a^b)<0);}
template<typename T, typename S> constexpr T iceil(const T a, const S b){return ifloor(a+b-1,b);}

template<typename T>
void sort_unique(vector<T> &vec){
    sort(vec.begin(),vec.end());
    vec.resize(unique(vec.begin(),vec.end())-vec.begin());
}

template<typename T, typename S> constexpr bool chmin(T &a, const S b){if(a>b) return a=b,true; return false;}
template<typename T, typename S> constexpr bool chmax(T &a, const S b){if(a<b) return a=b,true; return false;}

template<typename T, typename S> istream& operator >> (istream& i, pair<T,S> &p){return i >> p.first >> p.second;}
template<typename T, typename S> ostream& operator << (ostream& o, const pair<T,S> &p){return o << p.first << ' ' << p.second;}

#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif

template<typename T> void print(vector<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(unordered_set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void print(T && x) {cout << x << "\n";}
template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}

template<typename T> istream& operator >> (istream& i, vector<T> &vec){for(auto &x: vec) i >> x; return i;}

vvi read_graph(int n, int m, int base=1){
    vvi adj(n);
    for(int i=0,u,v; i<m; ++i){
        cin >> u >> v,u-=base,v-=base;
        adj[u].pb(v),adj[v].pb(u);
    }
    return adj;
}

vvi read_tree(int n, int base=1){return read_graph(n,n-1,base);}

template<typename T, typename S> pair<T,S> operator + (const pair<T,S> &a, const pair<T,S> &b){return {a.first+b.first,a.second+b.second};}

template<typename T> constexpr T inf=0;
template<> constexpr int inf<int> = 0x3f3f3f3f;
template<> constexpr ll inf<ll> = 0x3f3f3f3f3f3f3f3f;

template<typename T> vector<T> operator += (vector<T> &a, int val){for(auto &i: a) i+=val; return a;}

template<typename T> T isqrt(const T &x){T y=sqrt(x+2); while(y*y>x) y--; return y;}

#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())

//#include<atcoder/all>
//using namespace atcoder;

//using mint=modint998244353;
//using mint=modint1000000007;

const int N=1<<18,K=1<<10;

struct DS{
    int big[N/K],small[N];
    void ins(int x){
        small[x]++;
        big[x>>10]++;
    }
    void del(int x){
        small[x]--;
        big[x>>10]--;
    }
    int kth(int k){
        k--;
        int cur=0;
        while(big[cur]<=k) k-=big[cur++];
        cur<<=10;
        while(small[cur]<=k) k-=small[cur++];
        return cur;
    }
}ds;

void ahcorz(){
    int n,m; cin >> n >> m;
    vvi adj=read_graph(n,m);
    vi block(n);
    int cur=0;
    rep(n){
        if(cur>=n) break;
        int tot=0;
        while(cur<n&&tot<K){
            tot+=sz(adj[cur])+1;
            block[cur++]=i;
        }
    }
    int q; cin >> q;
    vc<array<int,4>> qq(q);
    vi res(q);
    rep(q){
        int l,r,k; cin >> l >> r >> k; l--,r--;
        qq[i]={l,r,k,i};
    }
    sort(all(qq),[&](array<int,4> arr1, array<int,4> arr2){
        if(block[arr1[0]]!=block[arr2[0]]) return block[arr1[0]]<block[arr2[0]];
        if(block[arr1[0]]&1) return arr1[1]>arr2[1];
        else return arr1[1]<arr2[1];
    });
    vi val(n);
    int l=0,r=0;
    ds.ins(0);
    auto ins=[&](int i){
        for(auto j: adj[i]){
            if(j>=l&&j<=r){
                ds.del(val[j]);
                val[j]^=i+1,val[i]^=j+1;
                ds.ins(val[j]);
            }
        }
        ds.ins(val[i]);
    };
    auto del=[&](int i){
        ds.del(val[i]);
        for(auto j: adj[i]){
            if(j>=l&&j<=r){
                ds.del(val[j]);
                val[j]^=i+1,val[i]^=j+1;
                ds.ins(val[j]);
            }
        }
    };
    auto gogo=[&](int l2, int r2){
        while(l>l2){
            ins(l-1);
            l--;
        }
        while(r<r2){
            ins(r+1);
            r++;
        }
        while(l<l2){
            l++;
            del(l-1);
        }
        while(r>r2){
            r--;
            del(r+1);
        }
    };
    for(auto [l2,r2,k,i]: qq){
        gogo(l2,r2);
        res[i]=ds.kth(k);
    }
    rep(i,l,r+1) ds.del(val[i]);
    rep(q) print(res[i]);
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cout << fixed << setprecision(20);
    int t=1;
    cin >> t;
    while(t--) ahcorz();
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

Consider easy version. Try to use only operation $$$1$$$ and $$$3$$$ (Due to symmetry, using operation $$$2$$$ and $$$4$$$ is the same), and only use $$$m=30$$$ in operation $$$1$$$ and $$$m=300$$$ in operation $$$3$$$.

Let $$$S_i$$$ represent the set in which queries element $$$i$$$ is accessed. Make all $$$S_i$$$ different to distinguish all elements.

Greedily choose all $$$S_i$$$ such that $$$|S_i| \lt 3$$$. Afterwards, carefully construct a set of size $$$3$$$ to reach the upper bound.

Suppose there are $$$30$$$ numbers $$$1, 2, …, 30$$$, and each number can be used up to $$$30$$$ times. Can you construct $$$900$$$ distinct triplets?

Consider hard version. How to efficiently utilize the four operations, and the condition $$$m \gt k$$$?

Using operation $$$1$$$ and operation $$$4$$$ is enough. Due to symmetry, using operation $$$2$$$ and $$$3$$$ is the same.

Recall the bottleneck of the easy version. We used too many sets of size $$$3$$$. Let’s say it another way — too many elements were determined at the cost of $$$3$$$. How to optimize it?

Consider $$$S_i=S_j$$$. This actually provides an unordered pair. In other words, we know unordered pair $$$(p_i,p_j)=(x,y)$$$, but we can not determine whether $$$p_i=x$$$ or $$$p_j=x$$$. To determine it, we can add one of $$$x$$$ or $$$y$$$ to the query of type $$$4$$$.

Suppose there are $$$300$$$ unordered pairs $$$(x_1, y_1), (x_2, y_2), …, (x_{300}, y_{300})$$$. We can add one element of $$$(x_i, y_i)$$$ into query $$$4$$$, then query to determine all unordered pairs. However, the average cost is still near to $$$3$$$, which is no better than the easy version.

Try to determine $$$435$$$ unordered pairs using single query $$$4$$$.

Use only operation $$$1$$$ and $$$3$$$, with $$$m=30$$$ in operation $$$1$$$ and $$$m=300$$$ in operation $$$3$$$.

Let $$$S_i$$$ represent the set accessed by query element $$$i$$$. To distinguish all elements, we need to ensure that all $$$S_i$$$ ($$$1 \le i \le n$$$) are distinct.

After selecting all $$$S_i$$$ such that $$$|S_i| \lt 3$$$, we must also construct a set of size $$$3$$$ to reach the upper bound.

Another way to phrase this: We have $$$30$$$ numbers $$$1, 2, \ldots, 30$$$, where $$$1$$$ through $$$29$$$ can each be used $$$30$$$ times, and $$$30$$$ can be used $$$270$$$ times. The goal is to construct as many distinct triplets as possible to maximize the count.

A natural approach is to prioritize consuming the usage count of $$$30$$$. Since $$$29$$$ is prime, the sequence $$$x = [1, k \mod 29 + 1, 2k \mod 29 + 1, \ldots, 28k \mod 29 + 1]$$$ ensures all elements are distinct. For $$$1 \le k \le 9$$$, we can construct triplets $$$(x_1, x_2, 30), (x_2, x_3, 30), \ldots, (x_{29}, x_1, 30)$$$.

After this, $$$1$$$ through $$$29$$$ will each have $$$12$$$ remaining uses, and $$$30$$$ will have $$$9$$$ remaining uses. This distribution is not ideal. Instead, we can use $$$(1, 2, 3)$$$ and $$$(4, 5, 6)$$$ in place of $$$(1, 2, 30), (3, 4, 30),$$$ and $$$(5, 6, 30)$$$. This adjustment ensures that $$$1$$$ through $$$30$$$ each have $$$12$$$ remaining uses.

Define a perfect set $$$S_x$$$ as a set of triplets where each number from $$$1$$$ to $$$x$$$ appears exactly once.

For numbers $$$1, 2, \ldots, 3l$$$, define:

• $$$al = [1, 2, \ldots, l]$$$,

• $$$am = [l+1, l+2, \ldots, 2l]$$$,

• $$$ar = [2l+1, 2l+2, \ldots, 3l]$$$.

Let $$$\text{lshift}(a, i) = [a_{1+i}, a_{2+i}, \ldots, a_{(n+i-1) \mod n + 1}]$$$. Then, define:

We can generate $$$l^2$$$ distinct perfect sets of the form $$$S_l(al, \text{lshift}(am, i), \text{lshift}(ar, j))$$$ for $$$0 \le i, j \le l$$$.

Now that all numbers have equal remaining usage counts, we can apply the above construction.

Using the above construction, there are many different approaches.

Overall, we can construct a total of $$$846$$$ distinct sets, which is sufficient to pass the easy version.

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1010;
int T,n;
vector<int> Sv[N],Sp[N];

void init()
{
    cin>>n;
    for(int i=1;i<N;i++)
        Sv[i].clear(),Sp[i].clear();
}

vector<int> ask(int ty,vector<int> &v)
{
    cout<<ty<<" "<<v.size();
    for(int i=0;i<v.size();i++)
        cout<<" "<<v[i];
    cout<<"\n"<<flush;
    int k;
    if(ty<3) k=min(60,(int)v.size());
    else k=min(300,(int)v.size());
    vector<int> res;
    for(int i=1;i<=k;i++)
    {
        int t;
        cin>>t;
        res.push_back(t);
    }
    return res;
}

void solve()
{
    int cnt=0;
    vector<int> p(n+4);
    for(int i=1;i<=30;i++)
        Sv[++cnt].push_back(i);
    for(int i=1;i<=30;i++)
    {
        for(int j=i+1;j<=30;j++)
        {
            cnt++;
            Sv[cnt].push_back(i),Sv[cnt].push_back(j);
        }
    }
    for(int i=1;i<=9;i++)
    {
        int cur=1;
        while(1)
        {
            int nxt=cur+i;
            if(nxt>29) nxt-=29;
            cnt++;
            Sv[cnt].push_back(30);
            Sv[cnt].push_back(cur);
            Sv[cnt].push_back(nxt);
            cur=nxt;
            if(nxt==1) break;
        }
    }
    vector<int> vl(11),vm(11),vr(11);
    for(int i=1;i<=10;i++)
        vl[i]=i,vm[i]=10+i,vr[i]=20+i;
    for(int i=1;i<=9;i++)
    {
        for(int j=1;j<=10;j++)
        {
            cnt++;
            Sv[cnt].push_back(vl[j]);
            Sv[cnt].push_back(vm[j]);
            Sv[cnt].push_back(vr[j]);
        }
        for(int j=0;j<10;j++)
            vr[j]=vr[j+1];
        vr[10]=vr[0];
    }
    for(int i=1,cur=1;i<=29;i++)
    {
        int x=cur,y=cur+1,z=cur+2;
        while(x>29) x-=29;
        while(y>29) y-=29;
        while(z>29) z-=29;
        cnt++;
        Sv[cnt].push_back(x);
        Sv[cnt].push_back(y);
        Sv[cnt].push_back(z);
        cur+=3;
    }
    for(int i=1;i<=30;i++)
    {
        vector<int> v,t;
        for(int j=1;j<=n;j++)
            if(find(Sv[j].begin(),Sv[j].end(),i)!=Sv[j].end())
                v.push_back(j);
        if(v.empty()) continue;
        if(i<30) t=ask(2,v);
        else t=ask(4,v);
        for(int j=0;j<t.size();j++)
            Sp[t[j]].push_back(i);
    }
    for(int i=1;i<=n;i++)
         sort(Sp[i].begin(),Sp[i].end()), sort(Sv[i].begin(),Sv[i].end());
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if((!Sp[i].empty())&&Sp[i]==Sv[j]) p[i]=j;
    cout<<"! ";
    for(int i=1;i<=n;i++)
        cout<<p[i]<<(i==n?'\n':' ');
    cout<<flush;
}

int main()
{
    fastio;

    cin>>T;
	while(T--)
	{
		init();
		solve();
	}

	return 0;
}

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <unordered_map>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1010;
int T,n;
vector<int> Sv[N],Sp[N],prv[N],prp[N];

void init()
{
    srand(time(0));
    cin>>n;
    for(int i=1;i<N;i++)
        Sv[i].clear(),Sp[i].clear(),prv[i].clear(),prp[i].clear();
}

vector<int> ask(int ty,vector<int> &v)
{
    cout<<ty<<" "<<v.size();
    for(int i=0;i<v.size();i++)
        cout<<" "<<v[i];
    cout<<"\n"<<flush;
    int k;
    if(ty<3) k=min(60,(int)v.size());
    else k=min(300,(int)v.size());
    vector<int> res;
    for(int i=1;i<=k;i++)
    {
        int t;
        cin>>t;
        res.push_back(t);
    }
    return res;
}

void solve()
{
    int cnt=0,cntr=871,cntpr=30;
    vector<int> p(n+4);
    for(int i=1;i<=29;i++)
    {
        cnt++;
        Sv[cnt].push_back(i);
        cntr--;
        Sv[cntr].push_back(i);
    }
    for(int i=1;i<=29;i++)
    {
        for(int j=i+1;j<=29;j++)
        {
            cnt++;
            Sv[cnt].push_back(i),Sv[cnt].push_back(j);
            cntr--;
            Sv[cntr].push_back(i),Sv[cntr].push_back(j);
        }
    }
    for(int i=871,hd=1;i<890;i++,hd+=3)
    {
        int x=hd,y=hd+1,z=hd+2;
        if(x>29) x-=29;
        if(y>29) y-=29;
        if(z>29) z-=29;
        Sv[i].push_back(x),Sv[i].push_back(y),Sv[i].push_back(z);
    }
    for(int i=1;i<=29;i++)
    {
        vector<int> v,t;
        for(int j=1;j<=n;j++)
            if(find(Sv[j].begin(),Sv[j].end(),i)!=Sv[j].end())
                v.push_back(j);
        if(v.empty()) continue;
        t=ask(2,v);
        for(int j=0;j<t.size();j++)
            Sp[t[j]].push_back(i);
    }
    for(int i=1;i<=n;i++)
         sort(Sp[i].begin(),Sp[i].end()), sort(Sv[i].begin(),Sv[i].end());
    for(int i=1;i<=n;i++)
    {
        for(int j=871;j<=n;j++)
            if(Sp[i]==Sv[j]) p[i]=j;
    }
    for(int i=1;i<=n;i++)
    {
        if(Sp[i].size()==1) prp[Sp[i][0]].push_back(i);
        else if(Sp[i].size()==2) prp[30*Sp[i][0]+Sp[i][1]].push_back(i);    //hash the set
        //|S|>2 and empty set are ignored
    }
    for(int i=1;i<=n;i++)
    {
        if(Sv[i].size()==1) prv[Sv[i][0]].push_back(i);
        else if(Sv[i].size()==2) prv[30*Sv[i][0]+Sv[i][1]].push_back(i);    //hash the set
    }
    //necessary shuffle
    for(int i=1;i<N;i++)
    {
        if(prp[i].size()<2) continue;
        if(rand()&1) swap(prp[i][0],prp[i][1]);
    }
    for(int i=1;i<=1;i++)
    {
        vector<int> v,t;
        for(int j=1;j<N;j++)
        {
            if(prp[j].empty()) continue;
            else if(prp[j].size()==1)
            {
                p[prp[j][0]]=prv[j][0];
                prp[j].clear();
                prv[j].clear();
                continue;
            }
            v.push_back(prp[j][0]);
        }
        if(v.empty()) continue;
        t=ask(3,v);
        for(int j=1;j<N;j++)
        {
            if(prp[j].empty()) continue;
            if(t.empty()) break;
            if(prv[j][1]==t.back())
            {
                t.pop_back();
                p[prp[j][0]]=prv[j][1];
                p[prp[j][1]]=prv[j][0];
            }
            else
            {
                p[prp[j][0]]=prv[j][0];
                p[prp[j][1]]=prv[j][1];
            }
            prp[j].clear();
            prv[j].clear();
        }
    }
    cout<<"! ";
    for(int i=1;i<=n;i++)
        cout<<p[i]<<(i==n?'\n':' ');
    cout<<flush;
}

int main()
{
    fastio;

    cin>>T;
	while(T--)
	{
		init();
		solve();
	}

	return 0;
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve: