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:

#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:

#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

pair<int,int> ma[610000];


int main()
{
	int i,j,k,n,l,t,m,x,y,o,b1;
	vector<int> ans;
	scanf("%d",&t);
	for (l=0;l<t;l++)
	{
		scanf("%d",&n);
		for (i=0;i<n+n;i++)
		{
			ma[i]=make_pair(-1,-1);
		}
		for (i=0;i<n;i++)
		{
			scanf("%d%d",&x,&y);

			x--;y--;
			ma[x]=max(ma[x],make_pair(y,i));
		}
		ans.clear();
		for (i=0;i<n+n;i++)
		{
			if (ma[i]==make_pair(-1,-1)) continue;
			ans.push_back(ma[i].second);
		}
		printf("%d\n",(int)ans.size());
		for (i=0;i<ans.size();i++)
			printf("%d ",ans[i]+1);
		printf("\n");
	}
}

Amazing problem:

Good problem:

Average problem:

Bad problem:

Didn't solve:

#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:

#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:

#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:

#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:

#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;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
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;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
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: