I assume that you can solve 60 points in $$$O(k(m + n))$$$.

Build a segment tree (basically, memoized D&C) over range $$$[1, k]$$$. Take the middle point $$$m = (k + 1) / 2$$$. There is a set of reachable nodes from $$$m$$$, and the nodes that can reach $$$m$$$. Let them be $$$L, R$$$ respectively.

If $$$L \cap R \neq \emptyset$$$, it means there is a cycle, so terminate.

Otherwise, you recurse down. For the left subproblem, you can only consider vertex set $$$L$$$, and for the right subproblem, you can only consider vertex set $$$R$$$: This means, for each vertices, as long as they are not in any cycle, they belong to at most $$$\log k$$$ subproblems.

When adding an edge, you can determine the set of vertices that are either appended to $$$L$$$ or $$$R$$$. If you have to add to both, then you have a cycle. Depending on the position you added, you can determine which direction to recurse down. You may have to add a large set of vertices at once, but the amortized bound still holds.

I think it is related to this thing.

When the grid has size $$$5 \times 5$$$, we can store the entire grid directly. Let $$$h = \lfloor \frac{n}{2} \rfloor$$$.

We store these rows $$$[0,h),[h, n), [n,n+h),[n+h,2n),[2n,2n]$$$. We can see that $$$h \leq 10$$$ when $$$n \leq 20$$$, so are able to directly store the entire grid in this fashion.

Now, we want to transfer the $$$5 \times 5$$$ grid into $$$3 \times 3$$$ grid (Actually I only used $$$4$$$ tiles of the $$$9$$$ tiles).

We want to store each $$$(n+1) \times (n+1)$$$ square in a compact way such that we are able to get all the information we need. Let us focus on the top-left region (the one with the red square).

We only care about the cells in this yellow band and the connectivity between them. There might be islands that are already formed that do no touch the yellow band. We will count them separately.

Now, when $$$n=20$$$, we need to use $$$41$$$ bits to store the entire state of the yellow band. and there can be up to $$$100$$$ islands in the white region that is not connected to the yellow band. So we have already used about $$$48$$$ bits.

Now, we need to store the connectivity of those lands in the yellow band using the other bits. We can actually do this in $$$42$$$ bits only. Firstly, let us focus on the yellow band only. There are at most $$$21$$$ connected components. If $$$2$$$ lands are adjacent in the yellow region, they belong to the same connected component.

The worst case where the number for connected components for $$$n=3$$$ is shown here.

Now, here is the crucial observation. Let us label the connected components in some order of walking along the line.

Suppose $$$a<b<c<d$$$. If $$$(a,c)$$$ is connected and $$$(b,d)$$$ is connected. Then the entire $$$(a,b,c,d)$$$ must necessarily be all connected.

There is no way you can not make the red and blue lines intersect because $$$b$$$ is inside the red shape, while $$$d$$$ is outside it.

This means that we can view this as a bracket sequence. That is, if $$$(a,c)$$$ are connected and there is no $$$a < b <c$$$ such that $$$(a,b)$$$ is connected, then we add an edge between $$$a$$$ and $$$c$$$. This can be viewed as adding a $$$\texttt{(}$$$ to $$$a$$$ and $$$\texttt{)}$$$ to $$$c$$$.

So if the connectivity looks like this, we will store $$$\texttt{(}_a \texttt{)}_c \texttt{(}_c \texttt{(}_d \texttt{)}_e \texttt{)}_f$$$. Notice that for each index, there is at most a single copy of $$$\texttt{(}$$$ or $$$\texttt{)}$$$. Since we have shown that there are at most $$$21$$$ connected components on the yellow band, we only have to use $$$42$$$ additional bits to store the connectivity. Therefore, we can store the important things we need from a corner of the grid in $$$41+21+21+7=90$$$ bits.

#include "mars.h"

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

bool bad(int i,int j){
	return i<0 || 10<=i || j<0 || 10<=j;
}

const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};

bool has[45][45];
int id[45][45];
vector<ii> al[45][45]; //extra shit
void dfs(int i,int j){
	rep(z,0,4){
		int i2=i+dx[z],j2=j+dy[z];
		if (i2<0 || j2<0) continue;
		if (has[i2][j2] && id[i2][j2]==-1){
			id[i2][j2]=id[i][j];
			dfs(i2,j2);
		}
	}
	for (auto [i2,j2]:al[i][j]){
		if (has[i2][j2] && id[i2][j2]==-1){
			id[i2][j2]=id[i][j];
			dfs(i2,j2);
		}
	}
}

int read(string s,int l,int r){
	int curr=0;
	rep(x,r+1,l){
		curr<<=1;
		if (s[x]=='1') curr++;
	}
	return curr;
}

string write(int i,int len){
	string s(len,'0');
	rep(x,0,min(len,20LL)) if (i&(1<<x)) s[x]='1';
	return s;
}

string process(vector <vector<string>> S, signed i, signed j, signed k, signed m){
	rep(x,0,45) rep(y,0,45){
		has[x][y]=false;
		id[x][y]=-1;
		al[x][y].clear();
	}
	
	int n=2*m+1;
	if (m==1){ //pretty retarded case
		rep(x,0,n) rep(y,0,n) has[x][y]=(S[x][y][0]=='1');
		
		int ans=0;
		rep(x,0,45) rep(y,0,45) if (has[x][y] && id[x][y]==-1){
			id[x][y]=0; //dont care
			dfs(x,y);
			ans++;
		}
		
		return write(ans,100);
	}
	
	ii arr[45][45];
	ii brr[45][45];
	rep(x,0,n) rep(y,0,n) arr[x][y]={min(max(x*m/2,x),x+2*k),min(max(y*m/2,y),y+2*k)};
	rep(x,0,n) rep(y,0,n) brr[x][y]={min(max(x*m/2,x),x+2*(k+1)),min(max(y*m/2,y),y+2*(k+1))};
	
	//our goal
	//( 0,0) ( 0,10) ( 0,20)
	//(10,0) (10,10) (10,20)
	//(20,0) (20,10) (20,20)
	
	vector<ii> imp[4];
	rep(x,0,m+1){
		imp[0].pub({m,x});
		imp[1].pub({m,2*m-x});
		imp[2].pub({m,x});
		imp[3].pub({m,2*m-x});
	}
	rep(x,m,0){
		imp[0].pub({x,m});
		imp[1].pub({x,m});
		imp[2].pub({2*m-x,m});
		imp[3].pub({2*m-x,m});
	}
	
	if (k==m-2){ //second last step
		//there are 4 regions we want to care about here
		
		if (i%2==1 || j%2==1) return string(100,'0');
		
		//rep(x,0,5){
			//rep(y,0,5) cout<<arr[x][y].fi<<"_"<<arr[x][y].se<<" ";
			//cout<<endl;
		//}
		
		int num=i+j/2;
		//cout<<"start: "<<i<<" "<<j<<" "<<num<<endl;
		
		int xl,xr;
		int yl,yr;
		
		if (i==0) xl=0,xr=m;
		else xl=m,xr=2*m;
		if (j==0) yl=0,yr=m;
		else yl=m,yr=2*m;
		
		//cout<<xl<<" "<<xr<<endl;
		//cout<<yl<<" "<<yr<<endl;
		//for (auto [a,b]:imp[num]) cout<<a<<"_"<<b<<" "; cout<<endl;
		
		rep(x,xl,xr+1) rep(y,yl,yr+1){
			rep(a,3,0) rep(b,3,0){
				int nx=x-arr[i+a][j+b].fi;
				int ny=y-arr[i+a][j+b].se;
				
				if (bad(nx,ny)) continue;
				
				has[x][y]=S[a][b][nx*10+ny]=='1';
				
				goto done2;
			}
			
			done2:;
		}
		
		//rep(x,xl,xr+1){
			//rep(y,yl,yr+1) cout<<has[x][y]<<" "; cout<<endl;
		//}
		
		int IDX=0;
		int internal=0;
		for (auto [x,y]:imp[num]) if (has[x][y] && id[x][y]==-1){
			id[x][y]=IDX++;
			dfs(x,y);
		}
		
		rep(x,0,45) rep(y,0,45) if (has[x][y] && id[x][y]==-1){
			id[x][y]=IDX++;
			dfs(x,y);
			internal++;
		}
		
		bool pp=false;
		vector<ii> head;
		string mask(41,'0');
		
		rep(x,0,sz(imp[num])){
			int a,b;
			tie(a,b)=imp[num][x];
			
			if (has[a][b]){
				mask[x]='1';
				if (!pp) head.pub({x,id[a][b]});
				pp=true;
			}
			else{
				pp=false;
			}
		}
		
		//for (auto [a,b]:head) cout<<a<<"_"<<b<<" "; cout<<endl;
		
		string F(21,'0');
		string B(21,'0');
		
		rep(x,0,sz(head)){
			bool ok=true;
			rep(y,0,x) if (head[y].se==head[x].se) ok=false;
			if (ok) F[x]='1';
		}
		rep(x,0,sz(head)){
			bool ok=true;
			rep(y,x+1,sz(head)) if (head[y].se==head[x].se) ok=false;
			if (ok) B[x]='1';
		}
		
		//cout<<mask<<" "<<F<<" "<<B<<endl;
		//cout<<"inside: "<<internal<<endl;
		
		return mask+F+B+write(internal,17);
	}
	else if (k==m-1){
		//finally we solve everything here
		//we only care about the 4 corners
		
		//cout<<"!!!!"<<endl;
		
		//rep(x,0,4){
			//cout<<"imp "<<x<<": "; for (auto it:imp[x]) cout<<it.fi<<"_"<<it.se<<" "; cout<<endl;
		//}
		
		int ans=0;
		
		rep(i,0,2) rep(j,0,2){
			int num=i*2+j;
			
			string mask=S[i*2][j*2].substr(0,41);
			string F=S[i*2][j*2].substr(41,21);
			string B=S[i*2][j*2].substr(62,21);
			int internal=read(S[i*2][j*2],83,99);
			
			ans+=internal;
			
			ii pp={-1,-1};
			
			vector<ii> head;
			rep(x,0,sz(imp[num])){
				int a,b;
				tie(a,b)=imp[num][x];
				
				if (mask[x]=='1'){
					has[a][b]=true;
					if (pp==ii(-1,-1)) head.pub({a,b});
					pp={a,b};
				}
				else{
					pp={-1,-1};
				}
			}
			
			vector<ii> stk;
			rep(x,0,sz(head)){
				int a,b;
				tie(a,b)=head[x];
				
				if (F[x]=='1'){
					stk.pub({a,b});
				}
				else{
					int c,d;
					tie(c,d)=stk.back();
					//cout<<a<<"_"<<b<<" "<<c<<"_"<<d<<endl;
					
					al[a][b].pub({c,d});
					al[c][d].pub({a,b});
				}
				if (B[x]=='1'){
					stk.pob();
				}
			}
		}
		
		//rep(x,0,n){
			//rep(y,0,n) cout<<has[x][y]; cout<<endl;
		//}
		
		rep(x,0,45) rep(y,0,45) if (has[x][y] && id[x][y]==-1){
			id[x][y]=0;
			dfs(x,y);
			ans++;
		}
		
		return write(ans,100);
	}
	else{ //just compress stuff...
		string res(100,'0');
	
		rep(x,0,10) rep(y,0,10){
			rep(a,3,0) rep(b,3,0) {
				int nx=brr[i][j].fi+x-arr[i+a][j+b].fi;
				int ny=brr[i][j].se+y-arr[i+a][j+b].se;
				
				if (bad(nx,ny)) continue;
				
				res[x*10+y]=S[a][b][nx*10+ny];
				
				goto done;
			}
			
			done:;
		}
		
		return res;
	}
	
}

Since $$$k \le 90$$$, a simple construction is $$$k - 2, k - 3, \dots, 1, 0$$$.

Observation 1: A permutation $$$0, 1, \dots, n - 1$$$, has $$$2^n$$$ increasing subsequences.

After making this observation, it is reasonable now to think about $$$k$$$ in terms of powers of $$$2$$$.

We now know how to obtain $$$k$$$ increasing subsequences in our permutation if $$$k$$$ is a power of $$$2$$$, so let's start with the permutation $$$0, 1, \dots, \lfloor log_2k \rfloor$$$, and see how the number of increasing subsequences changes when adding new elements.

Assume for now that the length of our current permutation is $$$n$$$.

Observation 2: Inserting $$$n$$$ at index $$$i$$$ adds $$$2^i$$$ new increasing subsequences to our current permutation.

Now it is easy to find a construction after making the second observation. You can see the implementation below for more details.

vector<int> construct_permutation(long long k) {
  int z = __lg(k);
  vector<int> p(z);
  iota(p.begin(), p.end(), 0);
  for (int i = z - 1; i >= 0; i--) {
    if ((k >> i) & 1) {
      p.insert(p.begin() + i, z++);
    }
  }
  return p;
}

For a sequence $$$X$$$ let $$$f(X)$$$ denote the number of increasing subsequences that it has. We must construct a sequence small enough $$$X$$$ with distinct elements (these can be converted into a permutation at the end) such that $$$f(X) = k$$$ where $$$k$$$ is the given value. Let's make some observations:

1. If we have a sequence $$$X$$$ with $$$f(X) = x$$$ then we can create $$$X'$$$ with $$$|X'| = |X|+1$$$ and $$$f(X') = x+1$$$ by appending a small enough number to $$$X$$$. For eg $$$(5, 4, 2, 1) \to (5, 4, 2, 1, -1)$$$
2. If we have a sequence $$$X$$$ with $$$f(X) = x$$$ then we can create $$$X'$$$ with $$$|X'| = |X|+1$$$ and $$$f(X') = x+2$$$ by decreasing the minimum element of $$$X$$$ by $$$1$$$ and appending the original minimum at the end. For eg $$$(5, 4, 2, 1) \to (5, 4, 2, 0, 1)$$$
3. If we have a sequence $$$X$$$ with $$$f(X) = x$$$ then we can create $$$X'$$$ with $$$|X'| = |X|+1$$$ and $$$f(X') = 2x$$$ by appending a large enough number to $$$X$$$. For eg $$$(5, 4, 2, 1) \to (5, 4, 2, 1, 6)$$$
4. If we have a sequence $$$X$$$ with $$$f(X) = x$$$ then we can create $$$X'$$$ with $$$|X'| = |X|+2$$$ and $$$f(X') = 3x$$$ by appending $$$M+2, M+1$$$ to the end of $$$X$$$ where $$$M$$$ is the original largest element of $$$X$$$. For eg $$$(5, 4, 2, 1) \to (5, 4, 2, 1, 7, 6)$$$

One of the $$$91.36$$$ solutions is to use steps $$$1, 3$$$ to reduce the number (the binary solution). Anyone who has gotten the $$$91.36$$$ solution like this will know that the issue were odd numbers, they required $$$2$$$ steps to reduce. This is precisely what we fix.

Say we have to find $$$list(k)$$$ for some $$$k$$$. If $$$k = 2$$$ we return $$$(0)$$$. If $$$k = 3$$$ we return $$$(1, 0)$$$. If $$$k$$$ is even, we find $$$list(k)$$$ recursively from $$$list(k/2)$$$ by using observation $$$3$$$. If $$$k$$$ is divisibly by $$$3$$$ we find $$$list(k)$$$ recursively from $$$list(k/3)$$$ by using observation $$$4$$$. Otherwise we find $$$list(k)$$$ recursively from $$$list(k-k \bmod 3)$$$ by using observation 1 or observation 2 (depending on whether $$$k \bmod 3 = 1$$$ or $$$2$$$).

Implementing this in the straightforward way will give $$$94.96$$$ points.

i now know a crazy randomised solution that passes for $$$100$$$ points but not going to share bcuz am evil

Greedily maintain the permutation and add one element to the right each time, until we have the needed number of increasing subsequences. The value added to the permutation will be the largest possible value such that we do not pass the needed number of increasing subsequences.

Note that if we add x to the right, we increase all other values in the permutation that are at least x by 1. For example, adding 3 to the permutation (5, 2, 0, 1, 3, 4) would result in: (6, 2, 0, 1, 4, 5 ,3).

This alone gives 91.36. To improve to 99.64, we simply try to extend all initial permutations of length 3 (length 2 gives about 97).

Unfortunately, my solution during the contest didn’t count the number of increasing subsequences efficiently (didn't have time to remove an O(permutation-length) factor from the complexity), so I could only fix the first 3 values to fit the time limits. Had I maintained the number of increasing subsequences efficiently, my code would have run about 100 times faster, and I would have been able to fix more initial permutations, which I’m convinced would have given a 100.

Even not improving the efficiency of the code, but stopping to check all initial permutations if the best permutation so far is already small enough, could be fast enough.

Unfortunately, I did none of these improvements during the contest, and so I got 173.64. The cutoff for silver medal was 174. Just sad.