A - Shout Everyday

This problem involves checking if a specific hour falls within a given time range spanning across midnight. We handle the wrap-around by adjusting the end time.

#include <cstdio>

int main() {
    int target, start, end;
    scanf("%d %d %d", &target, &start, &end);
    
    if (end <= start) end += 24;
    
    for (int t = start; t < end; ++t) {
        if (target == (t % 24)) {
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    return 0;
}

B - Cut .0

The task requires printing a floating-point number while removing unnecessary trailing zeros and decimal points. Using specific format specifiers allows handling different magnitudes of input effectively.

#include <cstdio>

int main() {
    double val;
    scanf("%lf", &val);
    
    if (val < 10.0) {
        printf("%.4g", val);
    } else {
        printf("%.5g", val);
    }
    return 0;
}

C - Enumerate Sequences

Given the small constraints, a Depth-First Search (DFS) approach is sufficient to genreate all possible sequences. We validate the sum modulo K and store valid results for sorting.

Time Complexity: O(R^N × N)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 10, MAX_RES = 400005;
int n, k, limits[MAX_N];
int curr_seq[MAX_N];

struct Result {
    int vals[MAX_N];
} results[MAX_RES];
int res_count;

void dfs(int idx) {
    if (idx > n) {
        int total = 0;
        for (int i = 1; i <= n; i++) total += curr_seq[i];
        
        if (total % k == 0) {
            res_count++;
            memcpy(results[res_count].vals, curr_seq, sizeof(curr_seq));
        }
        return;
    }
    for (int v = 1; v <= limits[idx]; v++) {
        curr_seq[idx] = v;
        dfs(idx + 1);
    }
}

bool compare(Result a, Result b) {
    for (int i = 1; i <= n; i++) {
        if (a.vals[i] != b.vals[i]) return a.vals[i] < b.vals[i];
    }
    return false;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &limits[i]);
    
    dfs(1);
    sort(results + 1, results + res_count + 1, compare);
    
    for (int i = 1; i <= res_count; i++) {
        for (int j = 1; j <= n; j++) {
            printf("%d ", results[i].vals[j]);
        }
        putchar('\n');
    }
    return 0;
}

D - Pedometer

The problem involves counting valid subarrays in a circular array where the sum modulo M is zero. We linearize the circle by duplicating the array and use prefix sums. The key is to handle the distance constraint (length <= N) and avoid pairing segments exclusively within the duplicated section.

Time Complexity: O(N)

#include <cstdio>
#include <cstring>
using namespace std;

const int MAX_N = 200005, MOD_RANGE = 1000005;
int n, m, steps[MAX_N * 2];
int prefix[MAX_N * 2];
long long freq[MOD_RANGE];
long long total_ans;

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &steps[i]);
        steps[n + i] = steps[i];
    }

    for (int i = 1; i < (n * 2); i++) {
        prefix[i] = (prefix[i - 1] + steps[i]) % m;
    }

    freq[prefix[0]]++;
    for (int i = 1; i < n; i++) {
        total_ans += freq[prefix[i]];
        freq[prefix[i]]++;
    }

    for (int i = n; i < (n * 2); i++) {
        freq[prefix[i - n]]--;
        total_ans += freq[prefix[i]];
    }

    printf("%lld\n", total_ans);
    return 0;
}

E - Permute K times

This problem demonstrates that permutation composition is associative, allowing the use of a "fast exponentiation" method (binary exponentiation) to apply a permutation K times efficiently.

#include <cstdio>
#include <array>
using namespace std;

const int MAX_N = 200005;
int n;
long long k;
array<int, MAX_N> base_perm, curr_state;

array<int, MAX_N> compose(array<int, MAX_N> &p, array<int, MAX_N> &q) {
    static array<int, MAX_N> res;
    for (int i = 1; i <= n; i++) {
        res[i] = p[q[i]];
    }
    return res;
}

int main() {
    scanf("%d %lld", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &base_perm[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &curr_state[i]);

    while (k > 0) {
        if (k & 1) curr_state = compose(curr_state, base_perm);
        base_perm = compose(base_perm, base_perm);
        k >>= 1;
    }

    for (int i = 1; i <= n; i++) printf("%d ", curr_state[i]);
    return 0;
}

F - Rearrange Query

We use a randomized hashing trick to check if two subarrays are permutations of each other. Each distinct value is mapped to a random unsigned integer. By compraing the sum of hash values in the ranges, we can determine equivalence probabilistically.

Note: Do not use XOR for hashing in this context, as it fails when dpulicate values cancel each other out.

#include <cstdio>
#include <ctime>
#include <random>
using namespace std;

const int MAX_N = 200005;
int n, q, arrA[MAX_N], arrB[MAX_N];
unsigned long long hashA[MAX_N], hashB[MAX_N];
unsigned int val_map[MAX_N];

int main() {
    mt19937 rng((unsigned)time(nullptr));
    scanf("%d %d", &n, &q);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &arrA[i]);
        if (!val_map[arrA[i]]) val_map[arrA[i]] = rng();
        hashA[i] = hashA[i - 1] + val_map[arrA[i]];
    }

    for (int i = 1; i <= n; i++) {
        scanf("%d", &arrB[i]);
        if (!val_map[arrB[i]]) val_map[arrB[i]] = rng();
        hashB[i] = hashB[i - 1] + val_map[arrB[i]];
    }

    while (q--) {
        int l1, r1, l2, r2;
        scanf("%d %d %d %d", &l1, &r1, &l2, &r2);
        unsigned long long segA = hashA[r1] - hashA[l1 - 1];
        unsigned long long segB = hashB[r2] - hashB[l2 - 1];
        printf("%s\n", segA == segB ? "Yes" : "No");
    }
    return 0;
}