#include <bits/stdc++.h>

using namespace std;

signed main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        char c; cin >> c;
        string s; cin >> s;
        int ans = 0;
        for (int i = 0; i < n / 2; ++i) {
            if (s[i] == s[n - i - 1]) continue;
            if (s[i] == c || s[n - i - 1] == c) ans++;
            else ans+=2;
        }
        cout << ans << '\n';
    }
}

• Great problem
• Good problem
• Bad problem
• Didn't solve

#include <bits/stdc++.h>

using namespace std;

int n, a[101], cnt[101];

void solve()
{
	cin >> n;
	
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];
		cnt[a[i]] ++;
	}
	for(int i = 1; i <= n; i ++)
	{
		for(int j = 100; j >= 1; j --)
		{
			if(cnt[j] >= i) cout << j << ' ';
		}
	}
	for(int i = 1; i <= n; i ++) cnt[a[i]] = 0;
	
	cout << '\n';
}
int main()
{
	int t;
	cin >> t;
	while(t --) solve();
}

• Great problem
• Good problem
• Bad problem
• Didn't solve

#include <bits/stdc++.h>
#define ll long long

const int N = 3e5 + 12;
using namespace std;

int n, x, a[N], p[N];
ll cnt[N];

vector <int> vc[N];

void solve()
{
	cin >> n >> x;
	
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];
		int r = a[i];
		a[i] = __gcd(a[i], x);
		
		for(auto j : vc[a[i]])
		{
			cnt[j] += r;
		}
	}
	ll ans = 0;
	
	for(auto j : vc[x])
	{
		ans = max(ans, cnt[j]);
	}
	for(int i = 1; i <= n; i ++)
	{
		for(auto j : vc[a[i]]) cnt[j] = 0;
	}
	cout << ans << '\n';
}
signed main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	
	for(int i = 2; i <= N - 12; i ++)
	{
		if(!p[i])
		{
			for(int j = i; j <= N - 12; j += i)
			{
				p[j] = 1;
				vc[j].push_back(i);
			}
		}
	}
	int test = 0;
	if(!test) cin >> test;
	while(test --) solve();
}
// solved by KluydQ

• Great problem
• Good problem
• Bad problem
• Didn't solve

#include <bits/stdc++.h>

using namespace std;

void solve()
{
	int n;
	cin >> n;
	
	int a[n + 5];
	int pos[n + 5];
	
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];
		pos[a[i]] = i % 2;
	}
	int balance = 0;
	
	for(int x = n; x > 0; x --)
	{
		if(pos[x] % 2 == 0) balance ++;
		if(pos[x] % 2 == 1) balance --;
		
		if(abs(balance) > 1)
		{
			cout << "NO\n";
			return;
		}
	}
	cout << "YES\n";
}
int main()
{
	int t;
	cin >> t;
	while(t --) solve();
}

• Great problem
• Good problem
• Bad problem
• Didn't solve

#include <bits/stdc++.h>

#define int long long
#define sz(x) (int)(x.size())
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )

using namespace std;

const int N = 2e5 + 12;
const int mod = 1e9 + 7;

int n, q, ans, cnt0, cnt1, pr[N];
string s;

void solve()
{
	cin >> n >> q >> s;
    ans = cnt0 = cnt1 = 0;
	
	FOR(i, 1, n - 1, 1)
	{
		pr[i] = 0;
		
		if(s[i - 1] != s[i])
		{
			pr[i] = 1;
			ans += i * (n - i);
		}
	}
	FOR(i, 0, n - 1, 1)
	{
	    if(s[i] == '0') cnt0 ++;
	    if(s[i] == '1') cnt1 ++;
	}
	cout << (ans + cnt0 * cnt1) / 2 << ' ';
	
	FOR(i, 1, q, 1)
	{
		int pos;
		cin >> pos;
		
		if(pos != 1)
		{
			if(pr[pos - 1] == 0) pr[pos - 1] = 1, ans += (pos - 1) * (n - pos + 1);
			else pr[pos - 1] = 0, ans -= (pos - 1) * (n - pos + 1);
		}
		if(pos != n)
		{
			if(pr[pos] == 0) pr[pos] = 1, ans += pos * (n - pos);
			else pr[pos] = 0, ans -= pos * (n - pos);
		}
		if(s[pos - 1] == '0') cnt0 --, cnt1 ++, s[pos - 1] = '1';
		else cnt1 --, cnt0 ++, s[pos - 1] = '0';
		
		cout << (ans + cnt0 * cnt1) / 2 << ' ';
	}
	cout << '\n';
}
signed main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	
	int t = 0;
	if(!t) cin >> t;
	while(t --) solve();
}

• Great problem
• Good problem
• Bad problem
• Didn't solve

#include <bits/stdc++.h>

using namespace std;

const int N = 2048;
int n, m, tim, a[N], cnt[N], ans[N];

void transform()
{
	vector <int> v;
	
	for(int i = 1; i <= n; i ++)
	{
		for(int j = i + 1; j <= n; j ++)
		{
			v.push_back(a[i] ^ a[j]);
		}
	}
	sort(v.begin(), v.end());
	for(int i = 1; i <= n; i ++) a[i] = v[i - 1];
}
void solve()
{
	cin >> n >> m;
	
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	int lim = 0;
	
	ans[lim] = a[n] - a[1];
		
	while(a[n] != 0)
	{
		lim ++, transform();
		ans[lim] = a[n] - a[1];
	}
	for(int i = 1; i <= m; i ++)
	{
		int x;
		cin >> x;
		
		if(x >= lim) cout << ans[lim] << '\n';
		else cout << ans[x] << '\n';
	}
}
signed main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	
	int test = 0;
	if(!test) cin >> test;
	while(test --) solve();
}

• Great problem
• Good problem
• Bad problem
• Didn't solve

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 12;

int n, m, tim, a[N], cnt[N], ans[N];
int t[N * 30], son[N * 30][2];

void update(int x, int v = 1)
{
	t[v] ++;
	
	for(int i = 29; i >= 0; i --)
	{
		if((x >> i) & 1)
		{
			if(!son[v][1]) son[v][1] = ++ tim;
			v = son[v][1];
		}
		else
		{
			if(!son[v][0]) son[v][0] = ++ tim;
			v = son[v][0];
		}
		t[v] ++;
	}
}
int get(int x, int k, int v = 1)
{
	int res = 0;
	
	for(int i = 29; i >= 0; i --)
	{
		int b = (x >> i) & 1;
		
		if(t[son[v][b]] >= k) v = son[v][b], res += (1 << i) * b;
		else k -= t[son[v][b]], v = son[v][b ^ 1], res += (1 << i) * (b ^ 1);
	}
	return res ^ x;
}
void transform()
{
	for(int v = 1; v <= tim; v ++) t[v] = son[v][0] = son[v][1] = 0;
	set <pair <int, int>> st; tim = 1;
	
	for(int i = 1; i <= n; i ++) update(a[i]), cnt[i] = 2;
	for(int i = 1; i <= n; i ++) st.insert({get(a[i], 2), i});
	
	vector <int> upd;
	
	for(int _ = 1; _ <= 2 * n; _ ++)
	{
		auto it = st.begin();
		int i = (*it).second;
		
		upd.push_back((*it).first);
		st.erase(it), cnt[i] ++;
		
		if(cnt[i] > n) continue;
		st.insert({get(a[i], cnt[i]), i});
	}
	for(int i = 1; i <= n; i ++) a[i] = upd[(i - 1) * 2];
}
void solve()
{
	cin >> n >> m;
	
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	int lim = 0;
	
	ans[lim] = a[n] - a[1];
	
	while(a[n] != 0)
	{
		lim ++, transform();
		ans[lim] = a[n] - a[1];
	}
	for(int i = 1; i <= m; i ++)
	{
		int x;
		cin >> x;
		
		if(x >= lim) cout << ans[lim] << '\n';
		else cout << ans[x] << '\n';
	}
}
signed main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	
	int test = 0;
	if(!test) cin >> test;
	while(test --) solve();
}

• Great problem
• Good problem
• Bad problem
• Didn't solve

#include <bits/stdc++.h>

#define sz(x) (int)(x.size())
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )

using namespace std;

const int N = (1 << 20) + 5;
const int mod = 1e9 + 7;

int n, m, c[N], dp[N], cnt[N], st[N][21];

void add(int &x, int y)
{
    x += y;
    if(x >= mod) x -= mod;
}
void solve()
{
	cin >> n >> m;
	
	FOR( i, 1, m, 1 )
	{
		cin >> c[i];
	}
	dp[0] = cnt[0] = 1;
	
	FOR( i, 1, n, 1 )
	{
		st[i][0] = 0;
		
		FOR( j, 0, 19, 1 )
		{
			st[i][j + 1] = st[i][j];
			if(!((m >> j) & 1) || i < (1 << j)) continue;
			
			else
			{
			    add(st[i][j + 1], st[i - (1 << j)][j]);
			    add(st[i][j + 1], dp[i - (1 << j)]);
			}
		}
		dp[i] = st[i][20];
	}
	FOR( i, 1, n, 1 )
	{
		st[i][0] = 0;
		
		FOR( j, 0, 19, 1 )
		{
		    st[i][j + 1] = st[i][j];
			if(!((m >> j) & 1) || i < (1 << j)) continue;
			
			else
			{
			    add(st[i][j + 1], st[i - (1 << j)][j]);
			    add(st[i][j + 1], cnt[i - (1 << j)]);
			}
		}
		cnt[i] = st[i][20];
		add(cnt[i], dp[i]);
	}
	int ans = 0;
	
	FOR( i, 1, m, 1 )
	{
		if((m & i) == i) add(ans, c[i] * 1ll * cnt[n - i] % mod);
	}
	cout << ans << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    
	int t = 0;
	if(!t) cin >> t;
	while(t --) solve();
}

• Great problem
• Good problem
• Bad problem
• Didn't solve