Hope you enjoy those tasks!

1332A - Прогулка

t = int(input())
for _ in range(t):
	a, b, c, d = map(int, input().split())
	x, y, x1, y1, x2, y2 = map(int, input().split())
	x += b - a
	y += d - c
	if a + b > 0 and x1 == x2:
		print("No")
	elif c + d > 0 and y1 == y2:
		print("No")
	elif x1 <= x <= x2 and y1 <= y <= y2:
		print("Yes")
	else:
		print("No")

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

int a,b,c,d,x,y,x1,y1,x2,y2,xx,yy;

int main(){
    int t;
    cin>>t;
    while (t--){
        cin>>a>>b>>c>>d;
        cin>>x>>y>>x1>>y1>>x2>>y2;
        xx=x,yy=y;
        x+=-a+b, y+=-c+d;
        if (x>=x1&&x<=x2&&y>=y1&&y<=y2&&(x2>x1||a+b==0)&&(y2>y1||c+d==0)){
            cout<<"Yes\n";
        }
        else{
            cout<<"No\n";
        }
    }
    return 0;
}

1332B - Непростая покраска

from math import gcd

def getprime(x):
	for i in range(2, x):
		if x % i == 0:
			return i
	return -1

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	used = [False for i in range(11)]
	clr = []
	for i in range(n):
		x = primes.index(getprime(a[i]))
		used[x] = True
		clr.append(x)
	cnt = 0
	num = []
	for i in range(11):
		num.append(cnt)
		if used[i]:
			cnt += 1
	print(cnt)
	for i in range(n):
		x = primes.index(getprime(a[i]))
		print(num[x] + 1, end = " ")
	print()

#include<bits/stdc++.h>
using namespace std;
 
int n,t;
vector<int> ans[1007];
int res[1007];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    auto f=[&](int u){
        for (int i=2;i<=u;++i){
            if (u%i==0) return i;
        }
    };
    cin>>t;
    while (t--){
        cin>>n;
        for (int i=1;i<=1000;++i) ans[i].clear();
        for (int i=1;i<=n;++i){
           int u;
           cin>>u; ans[f(u)].push_back(i);
        }
        int ret=0;
        for (int i=1;i<=1000;++i){
            if (ans[i].size()){
                ++ret;
                for (auto c:ans[i]){
                    res[c]=ret;
                }
            }
        }
        cout<<ret<<"\n";
        for (int i=1;i<=n;++i){
            cout<<res[i]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

1332C - K-полное слово

from sys import stdin

t = int(stdin.readline())
for _ in range(t):
	n, k = map(int, stdin.readline().split())
	s = stdin.readline()
	cnt = [[0 for i in range(26)] for j in range((k + 1) // 2)]
	for i in range(n):
		cnt[min(i % k, k - i % k - 1)][ord(s[i]) - ord('a')] += 1
	ans = 0
	for i in range(k // 2):
		ans += 2 * n // k - max(cnt[i])
	if k % 2 == 1:
		ans += n // k - max(cnt[k // 2])
	print(ans)

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

const int maxn=200007;

int n,k,ans=0;
int cnt[maxn][26];
string s;

int differ(int u,int v){
    int ret=0,mx=0;
    for (int j=0;j<26;++j){
        ret+=cnt[u][j]+cnt[v][j];
        mx=max(mx,cnt[u][j]+cnt[v][j]);
    }
    return ret-mx;
}

int main(){
    int t;
    cin>>t;
    while (t--){
        cin>>n>>k>>s;
        for (int i=0;i<k;++i){
            for (int j=0;j<26;++j){
                cnt[i][j]=0;
            }
        }
        for (int i=0;i<n;++i){
            cnt[i%k][s[i]-'a']++;
        }
        int ans=0;
        for (int i=0;i<k;++i){
            ans+=differ(i,k-1-i);
        }
        cout<<ans/2<<"\n";
    }
    return 0;
}

1327D - Бесконечный путь

Idea: adedalic

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);

int n;
vector<int> p, c;

inline bool read() {
    if(!(cin >> n))
        return false;
    p.resize(n);
    c.resize(n);
    
    fore(i, 0, n) {
        cin >> p[i];
        p[i]--;
    }
    fore(i, 0, n)
        cin >> c[i];
    return true;
}

inline void solve() {
    vector<int> used(n, 0);
    
    int ans = INF;
    fore(st, 0, n) {
        if(used[st])
            continue;
        
        vector<int> cycle;
        int v = st;
        while(!used[v]) {
            used[v] = 1;
            cycle.push_back(v);
            v = p[v];
        }
        
        fore(step, 1, sz(cycle) + 1) {
            if(sz(cycle) % step != 0)
                continue;
            
            fore(s, 0, step) {
                bool eq = true;
                for(int pos = s; pos + step < sz(cycle); pos += step) {
                    if(c[cycle[pos]] != c[cycle[pos + step]])
                        eq = false;
                }
                if(eq) {
                    ans = min(ans, step);
                    break;
                }
            }
        }
    }
    cout << ans << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
    
    int tc; cin >> tc;
    
    while(tc--) {
        read();
        solve();
        
#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}

1327E - Посчитайте блоки

Idea: adedalic

MOD = 998244353
p = [1] * 200005
for i in range(1, 200005):
    p[i] = (p[i - 1] * 10) % MOD

n = int(input())
for i in range(1, n):
    res = 2 * 10 * 9 * p[n - i - 1]
    res += (n - 1 - i) * 10 * 9 * 9 * p[n - i - 2]
    print(res % MOD, end = ' ')
print(10)

1327F - Отрезки И

Idea: Neon

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)

typedef pair<int, int> pt;

const int MOD = 998244353;
const int N = 500 * 1000 + 13;

int n, k, m;
pair<pt, int> q[N];

int ones[N];
int mx[N], sum[N];

int add(int x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
    return x;
}

int calc(int t) {
    memset(ones, 0, sizeof(ones));
    memset(mx, -1, sizeof(mx));
    
    forn(i, m) {
        int l = q[i].x.x, r = q[i].x.y;
        if (q[i].y & (1 << t)) {
            ones[l]++;
            ones[r + 1]--;
        } else {
            mx[r] = max(mx[r], l);
        }
    }
    
    int j = -1;
    forn(i, n) {
        int cur = 0;
        if (!ones[i]) {
            cur = sum[i];
            if (j == -1) cur = add(cur, 1);
            else cur = add(cur, -sum[j]);
        }
        
        sum[i + 1] = add(sum[i], cur);
        ones[i + 1] += ones[i];
        j = max(j, mx[i]);
    }
    
    return add(sum[n], j != -1 ? -sum[j] : 1);
}

int main() {
    scanf("%d%d%d", &n, &k, &m);
    forn(i, m) {
        scanf("%d%d%d", &q[i].x.x, &q[i].x.y, &q[i].y);
        --q[i].x.x; --q[i].x.y;
    }
    
    int ans = 1;
    forn(i, k) ans = (ans * 1ll * calc(i)) % MOD;
    printf("%d\n", ans);
}

1327G - Буквы и знаки вопроса

Idea: BledDest

#include<bits/stdc++.h>

using namespace std;

const int N = 8000043;
const int K = 15;
const int M = 1043;

int k;
char buf[N], buf2[M];
vector<string> t;
vector<int> c;
string s;

map<char, int> nxt[M];
int lnk[M];
int p[M];
char pchar[M];
map<char, int> go[M];
int term[M];
int ts = 1;
int A[M][K];
int F[M][K];
int dp[M];

int get_nxt(int x, char c)
{
    if(!nxt[x].count(c))
    {
        p[ts] = x;
        pchar[ts] = c;
        nxt[x][c] = ts++;
    }
    return nxt[x][c];
}

void add_string(int i)
{
    int cur = 0;
    for(auto x : t[i])
    {
        cur = get_nxt(cur, x);
    }
    term[cur] += c[i];
}

int get_go(int x, char c);

int get_lnk(int x)
{
    if(lnk[x] != -1)
        return lnk[x];
    if(x == 0 || p[x] == 0)
        return lnk[x] = 0;
    return lnk[x] = get_go(get_lnk(p[x]), pchar[x]);
}

int get_dp(int x)
{
    if(dp[x] != -1)
        return dp[x];
    dp[x] = term[x];
    if(get_lnk(x) != x)
        dp[x] += get_dp(get_lnk(x));
    return dp[x];
}

int get_go(int x, char c)
{
    if(go[x].count(c))
        return go[x][c];
    if(nxt[x].count(c))
        return go[x][c] = nxt[x][c];
    if(x == 0)
        return go[x][c] = 0;
    return go[x][c] = get_go(get_lnk(x), c);
}

void build_skip(const string& s, vector<int>& sA, vector<long long>& sF)
{                     
    sA = vector<int>(ts);
    for(int i = 0; i < ts; i++)
        sA[i] = i;
    sF = vector<long long>(ts);
    for(auto c : s)
    {
        int ci = int(c - 'a');
        for(int i = 0; i < ts; i++)
        {
            sF[i] += F[sA[i]][ci];
            sA[i] = A[sA[i]][ci];
        }
    }
}

long long solve(const string& s)
{
    long long BAD = (long long)(-1e18);

    vector<int> pos;
    for(int i = 0; i < s.size(); i++)
        if(s[i] == '?')
            pos.push_back(i);
    int cntQ = pos.size();
    vector<vector<int> > skip_A(cntQ + 1);
    vector<vector<long long> > skip_F(cntQ + 1);
    build_skip(s.substr(0, pos[0]), skip_A[0], skip_F[0]);
    for(int i = 1; i < cntQ; i++)
        build_skip(s.substr(pos[i - 1] + 1, pos[i] - pos[i - 1] - 1), skip_A[i], skip_F[i]);
    build_skip(s.substr(pos.back() + 1, s.size() - pos.back() - 1), skip_A[cntQ], skip_F[cntQ]);

    vector<vector<long long> > dp(1 << (K - 1), vector<long long>(ts, BAD));
    vector<int> used(1 << K);
    dp[0][skip_A[0][0]] = skip_F[0][0];
    queue<int> q;
    q.push(0);
    used[0] = 1;
    long long ans = BAD;
    while(!q.empty())
    {
        int k = q.front();
        q.pop();
        int step = __builtin_popcount(k);
        if(step == cntQ)
        {
            for(int i = 0; i < ts; i++)
                ans = max(ans, dp[k][i]);
            continue;
        }
        for(int i = 0; i < K - 1; i++)
        {
            if(k & (1 << i)) continue;
            int nk = (k ^ (1 << i));
            if(used[nk] == 0)
            {
                used[nk] = 1;
                q.push(nk);
            }
            for(int j = 0; j < ts; j++)
            {
                if(dp[k][j] == BAD)
                    continue;
                int nj = get_go(j, char('a' + i));
                int newSt = skip_A[step + 1][nj];
                long long add = get_dp(nj) + skip_F[step + 1][nj];
                dp[nk][newSt] = max(dp[nk][newSt], dp[k][j] + add);
            }
        }
    }
    return ans;
}

int main()
{
    scanf("%d", &k);
    t.resize(k);
    c.resize(k);
    for(int i = 0; i < k; i++)
    {
        scanf("%s %d", buf2, &c[i]);
        t[i] = buf2;
    }    
    scanf("%s", buf);
    s = buf;

    for(int i = 0; i < k; i++)
        add_string(i);
    for(int i = 0; i < ts; i++)
    {
        lnk[i] = -1;
        dp[i] = -1;
    }
    for(int i = 0; i < ts; i++)
    {
        get_lnk(i);
        for(char c = 'a'; c <= 'o'; c++)
            get_go(i, c);
    }
    for(int i = 0; i < ts; i++)
        get_dp(i);                               
    for(int i = 0; i < ts; i++)
    {
        for(int j = 0; j < K; j++)
        {
            A[i][j] = get_go(i, char('a' + j));
            F[i][j] = dp[A[i][j]];
        }
    }   
    int n = s.size();
    vector<int> leftQ(n, -1);
    vector<int> rightQ(n, -1);
    for(int i = 0; i < n; i++)
    {
        if(i != 0)
            leftQ[i] = leftQ[i - 1];
        if(s[i] == '?')
            leftQ[i] = i;
    }
    for(int i = n - 1; i >= 0; i--)
    {
        if(i != n - 1)
            rightQ[i] = rightQ[i + 1];
        if(s[i] == '?')
            rightQ[i] = i;
    }
    vector<int> bad(n, 0);
    
    if(leftQ.back() == -1)
        bad = vector<int>(n, 1);

    long long ans = 0;
    int curSt = 0;
    string news = "";
    for(int i = 0; i < n; i++)
    {
        int ci = (s[i] == '?' ? 14 : int(s[i] - 'a'));
        if(bad[i])
            ans += F[curSt][ci];
        curSt = A[curSt][ci];
        if(!bad[i])
            news.push_back(s[i]);
        else if(i != 0 && !bad[i - 1])
            news.push_back('o');
    }                    
    if(!news.empty())
        ans += solve(news);
    printf("%lld\n", ans);
}