The problem is designed to deceive and seem like a graph problem, but the constraint that a mountain of a lower level must always be chosen before a mountain of a higher level makes the solution much easier. With this, we can see that it is always possible to pick the mountain of level $$$1$$$ before level $$$2$$$, and so on.

Formally speaking, it is always possible to pick a mountain $$$i$$$ before a mountain $$$j$$$ if $$$i \lt j$$$. Therefore, the smallest lexicographical order is the numbers from $$$1$$$ to $$$N$$$, sorted.

It is always possible to have an answer, so the possibility of printing $$$-1$$$ was also included to distract the competitors.

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int n,m; cin >> n >> m;
 
    for(int i = 0; i < m; i++){
        int a,b; cin >> a >> b;
    }
 
    for(int i = 1; i<=n; i++){
        cout << i << ' ' ;
    }
}

The numbers on the cards in the deck are represented as powers of the number $$$n$$$. Thus, the value of a move is the sum of different powers of $$$n$$$. Since each power can appear only once in a move, the value of the move, when represented in base $$$n$$$, consists only of $0$s and $1$s.

Here, $$$s_k$$$ is the value of the $$$k$$$-th term in the sequence, and each $$$a_i$$$ can only be $$$0$$$ or $$$1$$$.

In this way, we can observe a correspondence between the representation of $$$s_k$$$ in base $$$n$$$ and the binary representation of the number $$$k$$$. We note that the term $$$a_i$$$ will be equal to $$$1$$$ only if the $$$i$$$-th bit in the binary representation of $$$k$$$ is $$$1$$$.

Therefore, we just need to iterate over the bits of the number $$$k$$$ and add $$$n^i$$$ to the result whenever the $$$i$$$-th bit is active. The time complexity is $$$O(log(k))$$$.

#include <bits/stdc++.h>
using namespace std;
#define sws ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
 
#define int long long
 
const int MOD = 1e9 + 7;
 
 
int32_t main(){sws;
 
    int n, k;
    cin >> n >> k;
 
    int np = 1, ans = 0;
    for(int b=0; b<32; b++){
        if((k >> b) & 1){
            ans = (ans + np) % MOD;
        }
 
        np = (np * n) % MOD;
    }
 
    cout << ans << '\n';
 
    return 0;
}

The key observation is: when $$$B_{t,i,j} = 1$$$, $$$A_{t,i,j} = 1$$$, and $$$Prob(S, t_l, t_r)$$$, for any $$$S$$$ containing $$$(i, j)$$$ and $$$t_l \leq t \leq t_r$$$, is $$$\frac{1}{1}$$$, which has a value of $$$1$$$ mod $$$M$$$ — not greater than $$$\lfloor \frac{M}{2} \rfloor$$$ for any $$$M \gt 2$$$. We can verify that for $$$B_{0,i,j}$$$ from $$$1$$$ to $$$10^5$$$, there exists an $$$X$$$ such that $$$B_{X,i,j} = 1$$$. Moreover, this holds for small $$$X \leq T_{max}$$$, where $$$T_{max} = 244$$$. Thus, we can precalculate all $$$A_{t,i,j}$$$, $$$B_{t,i,j}$$$, $$$A'_{t,i,j}$$$, and $$$B'_{t,i,j}$$$ with $$$t$$$ up to $$$T_{max}$$$ at a cost of $$$O(M\log(M) + HWT_{max}\log(M))$$$. This is because, to find $$$NCP(X, M)$$$ with $$$X \lt M$$$, we store the coprimes to $$$M$$$ in a vector and search for the function result using binary search.

Thus, for each query, we can iterate over the subgrids of $$$K_i$$$ in $$$O(H^2W^2)$$$ and, for each of them, check if they meet the condition imposed by the statement. If $$$t_l \gt t_r$$$ or $$$t_r \gt T_{max}$$$, we can already discard the subgrid. Otherwise, we need to calculate the probability mod $$$M$$$. For this, we can directly use the probability values $$$\frac{A'_{t,i,j}}{B'_{t,i,j}}$$$ mod $$$M$$$ and combine them using the probability union formula.

In the end, we want to perform the probability union over a multidimensional interval in time $$$t$$$ and coordinates $$$i$$$ and $$$j$$$ (union of $$$Prob((i,j,i,j), t, t)$$$ with $$$t_l \leq t \leq t_r$$$, $$$x1 \leq i \leq x2$$$, $$$y1 \leq j \leq y2$$$). We can observe that the union operation with probabilities mod $$$M$$$ forms a monoid. Thus, we will use a multidimensional Disjoint Sparse Table ( DiST ) to perform this operation in an interval of dimension $$$D$$$ in $$$O(2^D)$$$ (in this case, $$$D = 3$$$). The preprocessing for this has a cost of $$$O(H\log(H)W\log(W)T_{max}\log(T_{max}))$$$.

In the end, our complexity is $$$O((M\log(M) + HWT_{max}\log(M)) + (H\log(H)W\log(W)T_{max}\log(T_{max}) + (QH^2W^22^D))$$$, with the first phase being the preprocessing of $$$A$$$ and $$$B$$$, the second phase the preprocessing of the DiST, and the third phase the calculation of the queries. We can verify that this meets the limits with the input constraints.

#include<bits/stdc++.h>
using namespace std;
 
// Multidimensional Disjoint Sparse Table (DiST)
 
#define MAs template<class...As>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define repinv(i, a, b) for(int i = (a); i >= (b); i--)
template<int D, class S>
struct MDiST{ using T = S::T;
	int n, h; vector<vector<MDiST<D-1, S>>> t;
	int lg(signed x){return __builtin_clz(1)-__builtin_clz(x);}
	MAs MDiST(int s, As... ds):n(1<<(lg(s)+(s!=(1<<lg(s))))), 
	h(lg(n)), t(h+(n==1), vector(n, MDiST<D-1, S>(ds...))){}
	MAs void set(T x, int p, As... ps){t[0][p].set(x, ps...);}
	void join(MDiST& a, MDiST& b){
		rep(d,0,h)rep(i,0,n)t[d][i].join(a.t[d][i], b.t[d][i]);
	}
	void init(){
		rep(i,0,n)t[0][i].init();
		for(int d = 1, s = 2; d < h; d++, s *= 2)
		for(int m = s; m < n; m += 2*s){
			t[d][m] = t[0][m]; t[d][m-1] = t[0][m-1];
			rep(i, m+1, m+s)t[d][i].join(t[d][i-1], t[0][i]);
			repinv(i, m-2, m-s)t[d][i].join(t[0][i], t[d][i+1]);
		}
	}
	MAs T query(int l, int r, As... ps){
		if (l==r)return t[0][l].query(ps...);
		int k = lg(l^r);
		return S::op(t[k][l].query(ps...), t[k][r].query(ps...));
	}
};
 
template<class S>
struct MDiST<0, S>{ using T = typename S::T;
	T val = S::id;
	void set(T x){val = x;}
	void join(MDiST& a, MDiST& b){val = S::op(a.val, b.val);}
	void init(){}
	T query(){return val;}
};
 
// End of Multidimensional Disjoint Sparse Table (DiST)
 
int CF(int x){return x%2 ? (3*x + 1)/(x%4 == 1 ? 4 : 1) : x/2;}
int MOD(int a, int b){return b ? (a < 0 ? a : a%b) : 0;}
int SSF(int a, int b, int c){return MOD(a-c, b-c) + c;}
 
int M;
int mod_mul(int a, int b){return (int)((long long)a*b%M);}
vector<int> coprimes;
int inverse(int a){
	int res = 1, b = ((int)coprimes.size())-1;
	for(;b;a=mod_mul(a, a),b>>=1)if(b&1)res=mod_mul(res,a);
	return res;
}
int NCP(int x){return *lower_bound(coprimes.begin(), coprimes.end(), x);} //NCP(x, M)
 
pair<int, int> get_prob(int a, int b){
	int nb = NCP(SSF(b, M, 2));
	int na = SSF(a, nb, 1);
	return {na, nb};
}
 
struct ProbUnionMonoid{
	using T = int;
	static constexpr T id = 0;
	static T op(T a, T b){return (M + a + b - mod_mul(a, b))%M;}
};
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int h, w; cin >> h >> w >> M;
	for(int i = 1; i < M; i++)if (gcd(i, M) == 1)coprimes.push_back(i);
	constexpr int MAX_T = 255;
	vector A(MAX_T, vector(h, vector(w, 0))), B(MAX_T, vector(h, vector(w, 0)));
	for(int i = 0; i < h; i++)for(int j = 0; j < w; j++){
		cin >> A[0][i][j];
		for(int t = 1; t < MAX_T; t++)A[t][i][j] = CF(A[t-1][i][j]);
	}
	for(int i = 0; i < h; i++)for(int j = 0; j < w; j++){
		cin >> B[0][i][j];
		for(int t = 1; t < MAX_T; t++)B[t][i][j] = CF(B[t-1][i][j]);
	}
	MDiST<3, ProbUnionMonoid> dist(h, w, MAX_T);
	for(int i = 0; i < h; i++)for(int j = 0; j < w; j++)for(int t = 0; t < MAX_T; t++){
		auto [na, nb] = get_prob(A[t][i][j], B[t][i][j]);
		int prob = mod_mul(na, inverse(nb));
		dist.set(prob, i, j, t);
	}
	dist.init();
	int q; cin >> q;
	while(q--){
		int T, x1, y1, x2, y2; cin >> T >> x1 >> y1 >> x2 >> y2;
		int ans = 0;
		for(int a = x1; a <= x2; a++)for(int b = y1; b <= y2; b++)
		for(int c = a; c <= x2; c++)for(int d = b; d <= y2; d++){
			int tl = a+b+x1+y1, tr = T-(c+d+x2+y2);
			if (tl > tr)continue;
			if (tr >= MAX_T)continue;
			ans += dist.query(a-1,c-1,b-1,d-1,tl,tr) > (M/2);
		}
		cout << ans << endl;
	}
}

The volume of the cone is given by $$$\frac{\pi r_C^2 h_C}{3}$$$ and the volume of the semi-sphere by $$$\frac{2\pi r_C^3}{3}$$$. Thus, the volume $$$V_C$$$ of ice cream supported by the cone is $$$\frac{\pi}{3} (r_C^2 h_C + 2 r_C^3)$$$.

The volume of Lucas Sala's bottle is $$$V_L = \pi r_L^2 h_L$$$; therefore, we should print ``Injusto'' if and only if $$$V_L \gt V_C$$$, which is equivalent to $$$\pi r_L^2 h_L \gt \frac{\pi}{3} (r_C^2 h_C + 2 r_C^3)$$$. Simplifying, we see that this happens exactly when $$$3 r_L^2 h_L \gt r_C^2 h_C + 2 r_C^3$$$. This last inequality can be checked directly.

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
	int rl,hl;
	cin>>rl>>hl;
	int rc, hc;
	cin>>rc>>hc;
 
	// pi rl^2 hl > pi rc^2 hc /3 + 2 pi rc^3 / 3
	// rl^2 hl > rc^2 hc/3 + 2 rc^3 /3
	// 3 rl^2 hl > rc^2 hc + 2rc^3
	if ( 3 * rl*rl * hl > rc*rc*hc + 2*rc*rc*rc) {
		cout << "Injusto\n";
	} else {
		cout << "Justo\n";
	}
 
	return 0;
}

Due to the symmetry of permutation, the only states that matter are $$$N$$$, how many letters we need to add, and $$$K$$$, how many distinct letters we have already used. Thus, we can construct the following DP.

$$$ DP[N][K] = K*DP[N-1][K] + DP[N-1][K+1] $$$

In this transition, we can either add a letter that has already appeared or add a letter that has not appeared yet.

Since the maximum number of distinct letters we can add is 26, the number of DP states is $$$O(N * 26)$$$, and the transition is $$$O(1)$$$.

#include <bits/stdc++.h>
 
using namespace std;
 
const int mxN = 1e6;
long long dp[mxN + 1][26 + 1];
const long long MOD = 1e9 + 7;
 
long long rec(int n, int qtd) {
	if (qtd > 26) return 0;
	if (n == 0) return 1;
	long long & ans = dp[n][qtd];
	if (ans != -1) return ans;
	return ans = (rec(n-1, qtd) * qtd + rec(n-1, qtd+1)) % MOD;
}
 
void solve() {
	int n; cin >> n;
	memset(dp, -1, sizeof(dp));
	cout << rec(n, 0) << endl;
}
 
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1;
	// cin >> t;
	for (int i = 0; i < t; i++) {
		solve();
	}
	return 0;
}

Note that the Fibonacci sequence modulo $$$M$$$ is periodic. Indeed, there are only $$$M^2$$$ possible pairs $$$(a,b)$$$ of numbers in the interval $$$[0, M-1]$$$ that can be attained by consecutive terms of this sequence, and such a pair uniquely determines the rest of the sequence. Moreover, it is not difficult to see that the first such repetition is the pair $$$(0,1)$$$. The strategy for solving the problem will be to find a multiple $$$k$$$ of this period, which will be less than $$$5 \cdot 10^{18}$$$. Denoting by $$$r$$$ the remainder of the division of $$$a^b$$$ by $$$k$$$, it will suffice to compute $$$f_r$$$ modulo $$$M$$$, using, for example, matrix exponentiation.

We will denote by $$$\pi(k)$$$ the period of the Fibonacci sequence modulo $$$k$$$, where $$$k$$$ is any positive integer. Note that this function has the following property: if $$$a$$$ and $$$b$$$ are coprime positive integers, then $$$\pi(ab) = \operatorname{lcm}(\pi(a), \pi(b))$$$. Thus, it is enough to determine the values of $$$\pi$$$ at powers of primes.

First, we analyze the behavior of the function at primes. Fix a prime $$$p$$$ different from $$$5$$$ (the value of $$$\pi(5)$$$, which is 20, can be found naively). Assuming some familiarity with field theory, we will show that $$$p^2-1$$$ is a multiple of $$$\pi(p)$$$. A simple calculation shows that $$$\pi(2) = 3$$$, so the statement holds when $$$p=2$$$, and we can assume that $$$p \neq 2$$$.

Suppose that $$$\phi_1, \phi_2$$$ are solutions to the equation $$$x^2 = x+1$$$ in some field of characteristic $$$p$$$. It follows immediately by induction that

for every integer $$$n \geq 1$$$. Subtracting the equations, we obtain $$$\phi_1^n - \phi_2^n = f_n (\phi_1 - \phi_2)$$$. Therefore, if $$$\phi_1 \neq \phi_2$$$, we have the Binet formula:

Since $p \neq 2, 5$, the quadratic formula shows that we can take $$$\phi_1, \phi_2 = \frac{1 \pm \sqrt{5}}{2}$$$ as distinct solutions for $$$x^2 = x+1$$$. Note that $$$\phi_1, \phi_2$$$ belong to an extension $$$K$$$ of $$$F_p$$$ of degree at most $$$2$$$. Thus, the order of the multiplicative group of $$$K$$$ (denoted by $$$|K^*|$$$) is $$$p-1$$$ or $$$p^2-1 = (p-1)(p+1)$$$. Lagrange's theorem and Binet's formula then imply that $$$\pi(p)$$$ divides $$$|K^*|$$$, which in turn divides $$$p^2-1$$$, as we wanted to show.

Finally, it holds that $$$\pi(p^k)$$$ divides $$$\pi(p) \cdot p^{k-1}$$$. This follows immediately from [1, Th. 5].

[1] Wall, D. D. (1960). Fibonacci Series Modulo m. The American Mathematical Monthly, 67(6), 525--532. https://doi.org/10.2307/2309169

#include <bits/stdc++.h>
 
#define ll long long
 
using namespace std;
 
array<int,4> mul(array<int,4>& a, const array<int,4>& b, int MOD) {
	array<int,4> c={0,0,0,0};	
	c[0] = ((ll)a[0] * b[0] + (ll)a[1] * b[2]) % MOD;
	c[2] = ((ll)a[2] * b[0] + (ll)a[3] * b[2]) % MOD;
	c[1] = ((ll)a[0] * b[1] + (ll)a[1] * b[3]) % MOD;
	c[3] = ((ll)a[2] * b[1] + (ll)a[3] * b[3]) % MOD;
 
	return c;
}
 
array<int,4> fpow(array<int,4> m, ll b, int MOD) {
	array<int,4> x = {1,0,0,1};
	while(b) {
		if (b&1) x=mul(x,m,MOD);
		m=mul(m,m,MOD);
		b >>= 1;
	}
	return x;
}
 
ll fpow(ll a, ll b, ll MOD) {
	ll x=1;
	while(b) {
		if (b&1) x=(__int128)a*x%MOD;
		a=(__int128)a*a%MOD;
		b >>= 1;
	}
	return x;
}
 
ll prime_period(int p) {
	return p == 5 ? 20 : (ll)p*p-1;
}
 
signed main() {
	int a,b,MOD; cin>>a>>b>>MOD;
 
	int x=MOD;
	ll period=1;
	for (int p=2; p*p <= x; p++) {
		if (x % p) continue;
		int e;
		int pow;
		for (e=0,pow=1;x%p==0; x/=p, e++, pow*=p);
		period=lcm(period, prime_period(p) * (pow/p));
	}
 
	if (x != 1) period=lcm(period, prime_period(x));
 
	assert(period <= 1000000018000000080ll);
 
	ll n = fpow(a,b,period);
	assert(n >= 0);
	int ans = fpow(array<int,4>{0,1,1,1}, n, MOD)[1];
	assert(ans >= 0);
	cout << ans << endl;
}

The problem asks us to calculate the maximum matching considering the edges of the graph as bidirectional and disregarding edges from a vertex to itself.

We can verify that Iasmim's graph is a functional graph. Functional graphs are always formed by several components, where in each component there is exactly one cycle. In this problem, we will disregard cycles of a single vertex. What we have, in each component, is a structure that is almost a tree, but may contain one extra edge (forming a cycle). The problem can be solved independently for each component, summing the answers for each of them at the end.

To solve the problem in a component, we will consider that we know how to solve it if the component were a tree (search for Tree Matching — there is a problem in CSES with that name), in a complexity sufficiently small for the limits of this problem (for example, $$$O(N)$$$ or $$$O(N \sqrt{N})$$$). Now, we can think about the following if there is a cycle: removing an edge from it or its vertices transforms the component into a tree.

So, take any edge from the cycle. Solve the problem disregarding that edge in the remaining tree — we have the largest matching without that edge. Now, remove the vertices of that edge and solve the problem again in the remaining tree — adding $$$1$$$ to the result, we have the largest matching with the edge. Thus, the largest matching in the component is simply the maximum between the largest matching without and with that arbitrary edge from the cycle.

#include<bits/stdc++.h>
using namespace std;
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	vector g(n, vector<int>());
	for(int a = 0; a < n; a++){
		int b; cin >> b; b--;
		if (a == b)continue;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	int ans = 0;
	vector vis1(n, 0), vis2(n, 0), taken1(n, 0), taken2(n, 0);
	auto dfs1 = [&](auto rec, int v, int p, int& prob1, int& prob2)->int{
		int res = 0;
		vis1[v] = 1;
		for(int f : g[v]){
			if (f == p)continue;
			if (vis1[f]){
				prob1 = f;
				prob2 = v;
				continue;
			}
			res += rec(rec, f, v, prob1, prob2);
			if (not taken1[f] and not taken1[v])taken1[f] = taken1[v] = 1, res++;
		}
		return res;
	};
	auto dfs2 = [&](auto rec, int v, int p, const int prob1, const int prob2)->int{
		int res = 0;
		vis2[v] = 1;
		for(int f : g[v]){
			if (f == p or vis2[f])continue;
			res += rec(rec, f, v, prob1, prob2);
			if (not taken2[f] and not taken2[v])
				if (not (v == prob1 or v == prob2))
					if (not (f == prob1 or f == prob2))
						taken2[f] = taken2[v] = 1, res++;
		}
		return res;
	};
	for(int i = 0; i < n; i++){
		if (vis1[i])continue;
		int prob1 = -1, prob2 = -1;
		int res1 = dfs1(dfs1, i, i, prob1, prob2);
		int res2 = dfs2(dfs2, i, i, prob1, prob2);
		ans += max(res1, res2+(prob1 != prob2));
	}
	cout << ans << endl;
}

We can state that two triangles intersect if and only if at least one edge of the first triangle intersects an edge of the second triangle.

Furthermore, since the velocity is constant, we can also state that if two edges do not intersect at time $$$t$$$, but did intersect at some earlier time before $$$t$$$, then for any time after $$$t$$$, those two edges will no longer intersect. This occurs because the distance between two segments moving at constant velocity over time describes a convex function.

Thus, we can conclude that the time at which the collision between the triangles occurs corresponds to the earliest time at which an edge of the first triangle intersects an edge of the second triangle. Therefore, we can iterate over all pairs of edges, one from each triangle, and determine the earliest time at which the edges intersect. The problem then reduces to: finding the earliest time at which two line segments, moving with constant velocities, intersect.

To this end, we consider the function $$$\vec l_1(\lambda_1)$$$ which parameterizes a line segment whose endpoints are the points $$$A$$$ and $$$B$$$:

Here, $$$\vec l_1$$$ represents a two-dimensional vector with the coordinates of a point along the segment. Knowing that the points move with constant velocity $$$\vec v_1$$$, we define the function $$$\vec s_1(\lambda_1, t)$$$, which describes the motion of the segment over time:

We do the same for the second line segment, considering points $$$C$$$ and $$$D$$$ as its endpoints:

The two segments intersect at a given time if there exists a point that belongs simultaneously to both $$$\vec s_1(\lambda_1, t)$$$ and $$$\vec s_2(\lambda_2, t)$$$. Therefore, the condition for the existence of an intersection is:

This equation represents a system of two equations (one for each coordinate) with three variables.

Finally, we can observe that when two segments begin to intersect, the initial collision always involves an endpoint of one of the segments. Thus, we only need to consider four cases: when $$$\lambda_1 = 0$$$, $$$\lambda_1 = 1$$$, $$$\lambda_2 = 0$$$, or $$$\lambda_2 = 1$$$. In each case, the equation $$$\vec s_1(\lambda_1, t) = \vec s_2(\lambda_2, t)$$$ becomes a system of two equations with two variables. Therefore, for each case, we solve the system and identify the smallest value of $$$t$$$ at which the intersection occurs. The minimum among the four cases will be the earliest time at which the two segments intersect.

With the result for each pair of edges, we can then determine the moment at which the collision between the triangles occurs.

#include <bits/stdc++.h>
using namespace std;
 
struct Point{
    long long x, y;
 
    Point(long long _x = 0, long long _y = 0){
        x = _x;
        y = _y;
    }
 
    Point operator -(Point b){
        return {x - b.x, y - b.y};
    }
 
    long long operator ^(Point b){
        return x*b.y - y*b.x;
    }
 
};
 
struct Triangle{
    Point p[3], v;
};
 
long long sgn(long long a){
    if(a == 0){
        return 0;
    }
    else if(a > 0){
        return 1;
    }
    return -1;
}
 
long double solve2x2(Point a1, Point a2, Point b){
    long long D = a1^a2, Dt = b^a2, Dt1 = a1^b;
    if(D == 0){
        if(Dt == 0 and Dt1 == 0){
            long double ans = -1;
            if(b.x == 0 or sgn(a1.x) == sgn(b.x)){
                ans = b.x;
                ans = ans/a1.x;
            }
            if((b.x - a2.x == 0) or sgn(a1.x) == sgn(b.x - a2.x)){
                long double aux = b.x - a2.x;
                aux = aux/a1.x;
                if(ans < 0 or aux < ans){
                    ans = aux;
                }
            }
            return ans;
        }
        return -1;
    }
 
    if(Dt != 0 and sgn(Dt) != sgn(D)){
        return -1;
    }
    if((Dt1 != 0 and sgn(Dt1) != sgn(D)) or abs(Dt1) > abs(D)){
        return -1;
    }
 
    long double t = Dt;
    t = t/D;
 
    return t;
}
 
void update_ans(long double &ans, long double a){
    if(a >= 0 and (a < ans or ans < 0)){
        ans = a;
    }
}
 
int main(){
 
    Triangle T[2];
    for(int t=0; t<2; t++){
        for(int i=0; i<3; i++){
            cin >> T[t].p[i].x >> T[t].p[i].y;
        }
        cin >> T[t].v.x;
        cin >> T[t].v.y;
    }
 
 
    long double ans = -1;
    Point a1 = T[1].v - T[0].v, a2, b;
    for(int i=0; i<3; i++){
        int ii = (i + 1) % 3;
        for(int j=0; j<3; j++){
            int jj = (j + 1) % 3;
 
            Point A = T[0].p[i], B = T[0].p[ii];
            Point C = T[1].p[j], D = T[1].p[jj];
 
            a2 = D - C;
            // t1 = 0;
            b = A - C;
            update_ans(ans, solve2x2(a1, a2, b));
            // t1 = 1;
            b = B - C;
            update_ans(ans, solve2x2(a1, a2, b));
 
            a2 = A - B;
            // t2 = 0;
            b = A - C;
            update_ans(ans, solve2x2(a1, a2, b));
            // t2 = 1;
            b = A - D;
            update_ans(ans, solve2x2(a1, a2, b));
        }
    }
 
    cout << fixed << setprecision(12) << ans << '\n';
 
    return 0;
}

To solve the problem, we simply need to iterate through the $$$N+1$$$ lexicographically smallest possible names according to the constraints of the statement and choose the lexicographically smallest one that does not appear in the input list. We can do this recursively: we start with an empty string and decide which character to add next, in order from $$$a$$$ to $$$z$$$. If the string after adding the character is not in the list, it is the answer; otherwise, we call the recursion considering the current string. If the recursion finds a name that is not in the list, we have found the answer; otherwise, we move on to the next character and continue the search.

This process is $$$O(N \cdot X)$$$, where $$$X$$$ is the complexity of checking if a string is in the input list. If we use a Trie containing the input names, we can keep track of the Trie node we are in while performing the recursion and check in $$$O(1)$$$ if the current string is in the list.

Despite this, due to the constraints on the total size of the input, we can use a simple set of strings and call the count method of the set (total complexity $$$O(N \cdot K \cdot log(N))$$$). This works because, given the constraints that the input strings are distinct and the sum of their lengths is limited, it is not possible to generate a test case that would cause this solution to exceed the time limit. You can verify this by generating the $$$N$$$ lexicographically smallest strings for each value of $$$K$$$ until the sum of their lengths does not exceed the limit.

#include<bits/stdc++.h>
using namespace std;
 
#define vi vector<int>
#define pb push_back
#define sz(x) ((int)x.size())
template<class T>
struct Trie{
	vector<unordered_map<T, int>> g; vi cnt;
	Trie():g(1),cnt(1,0){}
	int new_node(){g.pb(unordered_map<T, int>()); cnt.pb(0); return sz(g)-1;}
	template<class S> void insert(const S & s){
		int cur = 0;
		for(T c : s){
			if (g[cur].count(c))cur = g[cur][c];
			else cur = g[cur][c] = new_node();
		}
		cnt[cur]++;
	}
};
 
int main(){ //Trie solution
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, k; cin >> n >> k;
	Trie<char> names;
	for(int i = 0; i < n; i++){
		string name; cin >> name;
		names.insert(name);
	}
	string ans;
	auto dfs = [&](auto rec, int i = 0, int p = 0)->bool{
		if (i == k)return false;
		for(char c = 'a'; c <= 'z'; c++){
			ans.push_back(c);
			if (not names.g[p].count(c))return true;
			int np = names.g[p][c];
			if (not names.cnt[np])return true;
			if (rec(rec, i+1, np))return true;
			ans.pop_back();
		}
		return false;
	};
	dfs(dfs); cout << ans << endl;
}

For a single query, the answer can be solved with xor-basis in $$$O(N \log (\max(A_i)))$$$.

Knowing that elements $$$A_i$$$ can be interpreted as vectors in the vector space of $$$\mathbb{Z}_2$$$, the single query subproblem can be solved by iterating the range $$$[L, R]$$$ and checking if each element (vector) will be added or not to the basis of this vector space.

On the one hand, if a new element is linearly independent to all the vectors already in the basis, then this new element cannot be derived from any linear combination of the elements of the basis and needs to be included in the basis of this vector space.

On the other hand, if a new element is not linearly independent to all vectors already in the basis, this means that this element can be formed by a linear combination of the vectors in the basis and, therefore, this new element is redundant and will be included in the kernel of this vector space instead.

With the xor-basis of $$$[L, R]$$$ computed, answering if an element $$$X$$$ can be formed by a subset of this range is easy: simply check if it is linearly independent to the basis. If it is linearly independent, then it cannot be formed. Otherwise, it can. In addition, it can be proved that the total number of different subsets that can form $$$X$$$ is given by $$$2^{|kernel|}$$$ if $$$X$$$ is not linearly independent of the basis.

The basis will have at most $$$\log(A_i))$$$ elements in any instant, and to verify whether a new element can be added to this basis, only the vectors of the basis need to be compared with this new element. This derives the total complexity of $$$O(N \log (\max(A_i)))$$$ for the single query subproblem.

Now, to solve the problems with more queries, we can use a heuristic to solve the queries offline. While iterating from $$$[1, N]$$$ with the pointer $$$r$$$, we can compute the xor-basis for all sub-ranges starting in a $$$l$$$ (with $$$l \leq r$$$) and ending in $$$r$$$.

When iterating a new element $$$r$$$ and checking if it is linearly independent to the basis of all sub-ranges, we can start trying to add it in the smallest sub-range first. If it is linearly independent, add it, proceed to the next smallest sub-range, and continue doing it.

But when this new element is not linearly independent to this considered sub-range, we can break the sub-range loop because the next bigger sub-ranges (which contain the current smaller sub-range) will not need this element to be added in their basis either.

With this heuristic, the final time complexity is $$$O( (N + Q) \log (\max(A_i)))$$$ and the total memory complexity is $$$O(N \log (\max(A_i)))$$$.

Observation: knowing that every answer is 0 or a power of 2, you can pre compute the values under the MOD beforehand.

#include <bits/stdc++.h>
using namespace std;
 
#define sws cin.tie(0)->sync_with_stdio(0)
#define endl '\n'
#define pb push_back
typedef long long ll;
 
const ll MOD = 998'244'353;
 
struct XorBasis {
    vector<ll> B;
    
    ll reduce(ll vec) { // O(log(a_max))
        for(auto b : B) vec = min(vec, vec^b);
        return vec;
    }
 
    bool add(ll vec) { // O(log(a_max))
        ll val = reduce(vec);
        if (val) {
            B.pb(val);
            return true;
        }
        return false;
    }
 
    ll dim() { return B.size(); }
};
 
int32_t main(){ sws;
    ll n; cin >> n;
    
    vector<ll> pow(n+1);
    pow[0] = 1;
    for(ll i=1; i<=n; i++) {
        pow[i] = (pow[i-1] * 2) % MOD;
    }
 
    vector<ll> lego(n+1);
    for(ll i=1; i<=n; i++) {
        cin >> lego[i];
    }
 
    using T = array<ll, 3>;
    vector<vector<T>> queries(n+1);
    ll q; cin >> q;
    for(ll i=1; i<=q; i++) {
        ll l, r, x; cin >> l >> r >> x;
        queries[r].pb({l, i, x});
    }
    
    vector<XorBasis> xb(n+1);
    vector<ll> ans(q+1);
 
    for(ll r=1; r<=n; r++) {
 
        for(ll l=r; l>=1; l--) {
            if (!xb[l].add(lego[r])) break;
            // We can break here, because this xor-basis of L already contains a basis that doesn't need x[r].
            // Therefore, the xor-basis of {L-1}, {L-2}, ..., which contains the xor-basis of L, also doesn't need x[r].
        }
 
        // solve all queries ending in r,
        // knowing that all xor-basis are computed up to r.
        for(auto [left, i, x] : queries[r]) {
            if (xb[left].reduce(x) == 0) {
                ll kernel = (r - left + 1) - xb[left].dim();
                ans[i] = pow[kernel];
            }
            else {
                ans[i] = 0;
            }
        }
    }
 
    for(ll i=1; i<=q; i++) {
        cout << ans[i] << endl;
    }
}

If the line contains the pokemon Torterra print "Staraptor, eu escolho voce!", if it contains Staraptor print "Luxray, eu escolho voce!", if it contains Luxray print "Torterra, eu escolho voce!".

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    string s; cin >> s;
    cin >> s;
    cin >> s;
    if(s[0] == 'T'){
        cout << "Staraptor, eu escolho voce!" << '\n';
    }
    else if(s[0] == 'S'){
        cout << "Luxray, eu escolho voce!" << '\n';
    }
    else{
        cout << "Torterra, eu escolho voce!" << "\n";
    }
}

The problem is simple; just do exactly what is asked in the statement; there is no trick or specific technique needed here.

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
	int a,b,c,q;
	cin>>a>>b>>c>>q;	
 
	auto f=[&](int x) -> int {
		return abs((a+c) * x*x*x - b*x*x + b*c*x + (x+c)*(x-a));
	};
 
	int result=0;
	for (int i=0; i < q; i++) {
		int x;cin>>x;
		result ^= f(x);
	}
	cout << result << endl;
}

Summary of the first solution: In the DAG of shortest paths, find with dynamic programming the path that minimizes the longest edge.

Summary of the second solution: Find the length $$$w$$$ of the shortest path and perform binary search to find the path that minimizes the longest edge.

Details of the first solution:

First, we construct a graph called the DAG of shortest paths from the input graph $$$G$$$. This graph has the same vertices as $$$G$$$ and contains an edge $$$(a_i, b_i, w_i)$$$ if and only if $$$G$$$ contains this edge and it is present in some shortest path from $$$1$$$ to $$$N$$$. To check if this second condition holds, we do the following: run Dijkstra from $$$1$$$ in graph $$$G$$$ and another Dijkstra from $$$N$$$ in the reverse graph of $$$G$$$ (the graph obtained by reversing the direction of the edges of $$$G$$$). This way, we obtain for each vertex $$$a$$$ the distance from $$$1$$$ to $$$a$$$ and the distance from $$$a$$$ to $$$N$$$. Thus, to check if the edge $$$(a_i, b_i, w_i)$$$ from $$$G$$$ belongs to the DAG of shortest paths, it is enough to verify if (the distance from $$$1$$$ to $$$a_i$$$ + w_i + the distance from $$$b_i$$$ to $$$N$$$) is equal to the distance from $$$1$$$ to $$$N$$$.

It is not difficult to demonstrate that the constructed graph is indeed acyclic and has the following property: any path in this graph that starts at $$$1$$$ and ends at a vertex $$$v$$$ is a shortest path from $$$1$$$ to $$$v$$$ in the original graph. Moreover, every shortest path in the original graph exists in the DAG of shortest paths. Thus, it is enough to find any path that minimizes the longest edge in this DAG. For this, for each vertex $$$a$$$, denote by $$$f(a)$$$ the minimum value of the longest edge on the path from $$$a$$$ to $$$N$$$ in the DAG of shortest paths. We also define that $$$f(N) = -\infty$$$. If $$$N(a)$$$ is the set of neighbors of $$$a$$$, it holds that

$$$f(a) = \min_{b \in N(a)}(f(b))$$$

We can use this equation to calculate $$$f$$$ recursively. To ensure good complexity, it is necessary to memoize the values of $$$f$$$. This step has a complexity of $$$O(N + M)$$$. Since we need to run two Dijkstras, the final complexity is $$$O(M + N \log(N))$$$.

Details of the second solution:

First, find the length $$$w$$$ of the shortest path from $$$1$$$ to $$$N$$$ using Dijkstra's algorithm. Define the value of a path as the length of its longest edge. We will use binary search to find the smallest value of a shortest path from $$$1$$$ to $$$N$$$. To do this, it is enough to check for each $$$c$$$ whether there exists a shortest path from $$$1$$$ to $$$N$$$ with a value less than or equal to $$$c$$$. This is simple: just remove the edges from $$$G$$$ with a length greater than $$$c$$$ and run Dijkstra from $$$1$$$. If (and only if) the value found for the distance from $$$1$$$ to $$$N$$$ in this new graph is also $$$w$$$, then there exists a shortest path from $$$1$$$ to $$$N$$$ with a value less than or equal to $$$c$$$.

#include <bits/stdc++.h>
 
#define ll long long
 
using namespace std;
 
constexpr ll oo=0x3f3f3f3f3f3f3f3f;
constexpr int MAX = 1e5;
 
vector<ll> dijkstra(vector<vector<pair<int,int>>>& g, int s) {
	int n = g.size();
	vector<ll> dist(n, oo);		
	vector<int> vis(n);
	
	priority_queue<pair<ll,int>> pq;
	pq.emplace(0, s);
	dist[s]=0;
 
	while(!pq.empty()) {
		auto [d, a] = pq.top(); pq.pop();		
		d = -d;
 
		if (vis[a]) continue;
		vis[a]=true;
 
		for (auto [b,w] : g[a]) {
			if (vis[b] or dist[b] <= d + w) continue; 	
			dist[b]=d+w;
			pq.emplace(-dist[b], b);
		}
	}
 
	return dist;
}
 
 
signed main() { //first solution
	ios_base::sync_with_stdio(0);cin.tie(0);
 
	int n,m;cin>>n>>m;	
	vector<vector<pair<int,int>>> g(n), ig(n);
	for (int i=0; i < m; i++) {
		int a,b,w;cin>>a>>b>>w; a--;b--;
		g[a].emplace_back(b,w);
		ig[b].emplace_back(a,w);
	}
 
	vector<vector<pair<int,int>>> dag(n);
	auto dist_g = dijkstra(g,0);
	auto dist_ig = dijkstra(ig,n-1);
 
	for (int a=0; a < n; a++) 
		for (auto [b,w] : g[a]) 
			if (dist_g[a] + w + dist_ig[b] == dist_g[n-1]) dag[a].emplace_back(b,w);
	
 
	vector<int> dp(n, -1);
	auto calc=[&](auto self, int a) -> int {
		if (a == n-1) return 0;	
		
		int& ans = dp[a];
		if (ans != -1) return ans;
		ans=MAX;
		for (auto [b,w] : dag[a]) ans=min(ans, max(w,self(self, b)));
		return ans;
	};
	
	assert(dist_g[n-1] > 0);
	cout << dist_g[n-1] << ' ' << calc(calc, 0) << endl;
}

We will preprocess all intervals that are permutations. For each $$$1 \leq i \leq n$$$, we denote by $$$p(i)$$$ the position where $$$i$$$ occurs in the list $$$a_1, \dots, a_n$$$. Note that this position exists and is unique, since the given list is a permutation.

We initialize an integer $$$r$$$ with the value $$$p(1)$$$, and observe that the interval $$$[p(1), r]$$$ is a permutation. Then, we increment or decrement $$$r$$$ repeatedly until $$$r$$$ reaches the value $$$p(2)$$$. In this process, we compute the maximum value $$$M$$$ reached by $$$a_r$$$, the minimum value $$$L$$$ reached by $$$r$$$, and the maximum value $$$R$$$ reached by $$$r$$$. Note that the sublist of $$$b$$$ between $$$L$$$ and $$$R$$$ contains exactly $$$R-L+1$$$ integers, its smallest element is $$$1$$$, and its largest element is $$$M$$$. Thus, for this sublist to be a permutation, it is necessary and sufficient that $$$M = R-L+1$$$. If this is the case, we store the fact that the interval determined by $$$(L, R)$$$ is a permutation.

After this preprocessing, to answer a query of the form $$$l_i, r_i$$$, it is enough to check if the interval $$$l_i, r_i$$$ is a permutation. For this, we simply need to ensure that, in the previous step, every time we verified that the interval determined by $$$L, R$$$ is a permutation, we inserted the pair $$$(L,R)$$$ into a set. Upon receiving the query, we check if the pair $$$(l_i, r_i)$$$ belongs to the set.

The complexity of the preprocessing is $$$O(n \log(n))$$$ due to the insertions in the set, and the complexity of answering each query is $$$O(\log(n))$$$, to check if an element belongs to a set. In total, we have a complexity of $$$O((n + q) \log(n))$$$.

We observe that it is possible to solve the problem in complexity $$$O(n + q\log(n))$$$. For this, instead of using a set, we insert the pairs $$$(L,R)$$$ into a list and at the end of the preprocessing, we sort this list using counting sort. This sorting can be done in $$$O(n)$$$, due to the fact that $$$1 \leq L,R \leq n$$$.

#include <bits/stdc++.h>
 
#define int long long
#define endl '\n'
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(int i=(int)(a);i < (int)(b);i++) // [a,b)
#define irep(i, a, b) for(int i=(int)(a);i >= (int)(b);i--) // [b,a]
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi>
#define sz(x) ((int)(x).size())
#define chmax(a,b) a=max(a, (b))
#define chmin(a,b) a=min(a, (b))
 
#ifdef LOCAL
#define debug(var) cerr << #var << ": " << (var) << endl
#else
#define debug(var)
#endif
 
 
using namespace std;
 
void solve()
{
	int n,q;cin>>n>>q;	
	vector<int> a(n), ia(n);
	rep(i,0,n) {
		cin>>a[i];
		a[i]--;
	}
	rep(i,0,n) ia[a[i]]=i;
	set<pii> good_itvls;
 
	int p=ia[0];
	int l=p, r=p;
	int mx = 0;
 
	rep(i,0,n) {
		// ia[i]	
		if (p < ia[i]) {
			p=min(ia[i], r);
			for(;p+1 <= ia[i]; chmax(mx,a[p+1]), p++);
			r=max(r, p);
		} else if (p > ia[i]) {
			p=max(ia[i], l);
			for(;p-1 >= ia[i]; chmax(mx,a[p-1]), p--);
			l=min(l,p);
		}
 
		if (r-l+1 == mx+1) good_itvls.emplace(l, r);
	}
 
	while(q--) {
		int l,r;cin>>l>>r;l--;r--;
		cout << (good_itvls.count(pair<int,int>(l,r)) ? "TAK":"NIE") << endl;
	}
}
 
signed main() {
	#ifndef LOCAL
	ios_base::sync_with_stdio(0);cin.tie(0);
	#endif
	int t=1;
	//cin>>t;		
	while(t--) solve();
}