#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n, k;
        cin >> n >> k;
        vector < vector <int> > b(k);
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            b[x % k].push_back(i);
        }
        int res = -1;
        for (int i = 0; i < k; i++) {
            if ((int)b[i].size() == 1) {
                res = b[i][0];
                break;
            }
        }
        if (res == -1) {
            cout << "NO" << endl;
        }
        else {
            cout << "YES" << endl << res << endl;
        }
    }
    
    return 0;
}

for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = [[] for _ in range(k)]
    for i in range(0, n):
        x = a[i]
        b[x % k].append(i + 1)
    res = -1
    for i in range(k):
        if len(b[i]) == 1:
            res = b[i][0]
            break
    if res == -1:
        print("NO")
    else:
        print("YES\n" + str(res))

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        for (int ans = 1, cur = 1; ; ans++, cur = cur * 2 + 2) {
            if (cur >= n) {
                cout << ans << '\n';
                break;
            }
        }
    }
    
    return 0;
}

tt = int(input())
for _ in range(tt):
    n = int(input())
    ans = 1
    cur = 1
    while True:
        if cur >= n:
            print(ans)
            break
        ans += 1
        cur = cur * 2 + 2

В какой-то момент разработки этой задачи появилось следующее альтернативное условие: нам необходимо минимизировать общее количество операций обоих типов. Как решить эту задачу?

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        long long k;
        cin >> n >> k;
        vector <int> a, b;
        
        if (n <= 60 && (1ll << (n - 1)) < k) {
            cout << -1 << endl;
            continue;
        }
        k--;
        vector <int> d;
        while (k) {
            d.push_back(k % 2);
            k /= 2;
        }
        while (d.size() < n - 1) d.push_back(0);
        
        for (int i = n - 2, j = 1; i >= 0; i--, j++) {
            if (d[i] == 0) a.push_back(j);
            else b.push_back(j);
        }
        
        reverse(b.begin(), b.end());
        for (int i : a) cout << i << ' ';
        cout << n << ' ';
        for (int i : b) cout << i << ' ';
        cout << endl;
    }
 
    return 0;
}

tt = int(input())
for _ in range(tt):
    n, k = map(int, input().split())
    a, b = [], []
 
    if n <= 60 and (1 << (n - 1)) < k:
        print(-1)
        continue
    k -= 1
    d = []
    while k:
        d.append(k % 2)
        k //= 2
    while len(d) < n - 1:
        d.append(0)
 
    a, b = [], []
    j = 1
    for i in range(n - 2, -1, -1):
        if d[i] == 0:
            a.append(j)
        else:
            b.append(j)
        j += 1
 
    b.reverse()
    print(*a, n, *b)

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector < vector <int> > g(n);
        for (int i = 0; i < n - 1; i++) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        
        vector <int> res(n);
        int lst = 1;
        res[0] = lst;
        
        function <void(int, int)> dfs = [&](int v, int p) {
            for (int to : g[v]) {
                if (to == p) continue;
                res[to] = lst + 1;
                while (res[to] != res[v] + 1 && 
                      (res[to] % 2 != res[v] % 2 || res[to] - res[v] == 2)) {
                    res[to]++;   
                }
                lst = res[to];
                dfs(to, v);
            }
        };
        
        dfs(0, 0);
        for (int i : res) cout << i << ' ';
        cout << endl;
    }
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
void dfs(int v, vector<vector<int>>& g, vector<int>& h, int p) {
    h[v] = h[p] + 1;
    for (int u : g[v]) {
        if (u == p)
            continue;
        dfs(u, g, h, v);
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector<vector<int>> g(n);
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        vector<int> h(n);
        dfs(0, g, h, 0);
        vector<vector<int>> hs(n + 1);
        for (int i = 0; i < n; i++)
            hs[h[i]].push_back(i);
        int l = 2, r = 2 * n;
        int cur = 0;
        vector<int> ans(n);
        for (int i = 1; i <= n; i++) {
           if (cur) {
               for (int v : hs[i]) {
                    ans[v] = r;
                    r -= 2;
               }
           } 
           else {
               for (int v : hs[i]) {
                    ans[v] = l;
                    l += 2;
               }
           }
           cur ^= 1;
        }
        bool found = false;
        for (int i = 0; i < n; i++) {
            for (int v : g[i]) {
                if (h[v] < h[i])
                    continue;
                if (abs(ans[v] - ans[i]) == 2) {
                    ans[v] = ans[i] - 1;
                    found = true;
                    break;
                }
            }
            if (found)
                break;
        }
        for (int i = 0; i < n; i++)
            cout << ans[i] << ' ';
        cout << '\n';
    }
    
    return 0;
}

Существует множество возможных решений этой проблемы, и почти все тестировщики реализовали уникальное решение. Есть решения, правильность которых мы не смогли доказать, но и взломать их тоже не смогли.

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, q;
    cin >> n >> q;
    
    vector < vector <int> > g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    vector <int> depth(n);
    vector <int> d(n);
    vector <int> par(n);
 
    function <void(int, int)> dfs = [&](int v, int p) {
        if (depth[v] == 1) d[v] = 1;
        if (depth[v] > 1) d[v] = d[par[p]] + 2 * (int)g[p].size();
        par[v] = p;
        for(int to : g[v]) {
            if (to == p) continue;
            depth[to] = depth[v] + 1;
            dfs(to, v);
        }
    };
    
    dfs(0, 0);
    
    while (q--) {
        int v, p;
        cin >> v >> p;
        v--;
        int res = d[v];
        vector <int> cnt;
        while (v != 0 && par[v] != 0) {
            cnt.push_back((int)g[par[v]].size());
            v = par[par[v]];
        }
        sort(cnt.rbegin(), cnt.rend());
        for (int i = 0; i < min(p, (int)cnt.size()); i++) {
            res -= 2 * (cnt[i] - 1);
        }
        cout << res << '\n';
    }
}
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
 
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
void solve() {
    int n, q;
    cin >> n >> q;
    
    vector < vector <int> > g(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    vector <int> depth(n);
    vector <int> d(n);
    vector < vector < pair <int,int> > > qrs(n); // <p, idx>
    vector <int> res(q);
    
    for (int i = 0; i < q; i++) {
        int v, p;
        cin >> v >> p;
        v--;
        qrs[v].push_back({p, i});
    }
    
    multiset <int> st[2]; // store negative number to be able to use usual foreach loop
    
    function <void(int, int, int)> dfs = [&](int v, int p, int pp) {
        if (depth[v] == 1) d[v] = 1;
        if (depth[v] > 1) d[v] = d[pp] + 2 * (int)g[p].size();
        
        for (pair <int, int> qr : qrs[v]) {
            int p = qr.first, idx = qr.second;
            int ans = d[v];
            for (int i : st[1 - depth[v] % 2]) {
                if (p == 0) break;
                ans -= (-i - 1) * 2;
                p--;
            }
            res[idx] = ans;
        }
        
        if (depth[v] != 0) st[depth[v] % 2].insert(-(int)g[v].size());
        
        for (int to : g[v]) {
            if (to == p) continue;
            depth[to] = depth[v] + 1;
            dfs(to, v, p);
        }
        
        if (depth[v] != 0) st[depth[v] % 2].erase(st[depth[v] % 2].find(-(int)g[v].size()));
    };
    
    dfs(0, 0, 0);
    
    for (int i = 0; i < q; i++)
        cout << res[i] << '\n';
}
 
int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
 
    return 0;
}

Изначально эта задача имела следующие ограничения:

1. $$$1 \le n, q \le 2 \cdot 10^5$$$

2. Сумма $$$p$$$ во всех запросах не больше $$$2 \cdot 10^5$$$

Как решить эту задачу?

Могли бы вы решить эту задачу и без второго ограничения?

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 3000010;
const int mod = 998244353;
int fact[N], ifact[N], phi[N];
 
int powmod(int a, int n) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            a = (a * a) % mod;
            n /= 2;
        }
        else {
            res = (res * a) % mod;
            n--;
        }
    }
    return res;
}
 
int inv(int a) {
    return powmod(a, mod - 2);
}
 
void prepare() {
    fact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
    ifact[N - 1] = inv(fact[N - 1]);
    for (int i = N - 2; i >= 0; i--) {
        ifact[i] = (ifact[i + 1] * (i + 1)) % mod;
    }
 
    phi[0] = 0;
    phi[1] = 1;
    for (int i = 2; i < N; i++) {
        phi[i] = i - 1;
    }
    for (int i = 2; i < N; i++) {
        for (int j = i * 2; j < N; j += i) {
            phi[j] -= phi[i];
        }
    }
}
 
int C(int n, int k) {
    return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod;
}
 
int MC(vector <int> &a) {
    int sum=0;
    for (int i : a) sum += i;
    int res = fact[sum];
    for (int i : a) {
        res = (res * ifact[i]) % mod;
    }
    return res;
}
 
int lcm(int a, int b) {
    return a / __gcd(a, b) * b;
}
 
vector <int> all_divs(int x) {
    vector <int> d;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            d.push_back(i);
            if (i * i != x) {
                d.push_back(x / i);
            }
        }
    }
    return d;
}
 
void solve() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    vector <int> v(k);
    for (int &i : v) cin >> i;
 
    int g = v[0];
    for (int i : v) g = __gcd(g, i);
 
    map <int, int> mp;
    for (int i : all_divs(a)) {
        for (int j : all_divs(b)) {
            for (int l : all_divs(c)) {
                int N = lcm(i, lcm(j, l));
                if (g % N == 0) {
                    mp[N] += phi[i] * phi[j] * phi[l];
                }
            }
        }
    }
 
    int sum = 0;
    for (pair <int, int> pr : mp) {
        int N = pr.first, cnt = pr.second;
        vector <int> u;
        for (int t : v) u.push_back(t / N);
        sum = (sum + (MC(u) * cnt) % mod) % mod;
    }
 
    sum = (sum * inv(a * b * c)) % mod;
 
    cout << sum << endl;
}
 
int32_t main() {
    prepare();
 
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
 
    return 0;
}

#include <bits/stdc++.h>
#define int long long
 
using namespace std;
 
const int N = 3000010;
const int mod = 998244353;
int fact[N], ifact[N];
int pos[N];
 
int powmod(int a, int n) {
    int res = 1;
    while (n) {
        if (n % 2 == 0) {
            a = (a * a) % mod;
            n /= 2;
        }
        else {
            res = (res * a) % mod;
            n--;
        }
    }
    return res;
}
 
int inv(int a) {
    return powmod(a, mod - 2);
}
 
void prepare() {
    fact[0] = 1;
    for (int i = 1;i < N; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
    ifact[N - 1] = inv(fact[N - 1]);
    for (int i = N - 2; i >= 0; i--) {
        ifact[i] = (ifact[i + 1] * (i + 1)) % mod;
    }
}
 
int C(int n, int k) {
    return ((fact[n] * ifact[k]) % mod * ifact[n - k]) % mod;
}
 
int MC(vector <int> &a) {
    int sum=0;
    for (int i : a) sum += i;
    int res = fact[sum];
    for (int i : a) {
        res = (res * ifact[i]) % mod;
    }
    return res;
}
 
int lcm(int a, int b) {
    return a / __gcd(a, b) * b;
}
 
vector <int> all_divs(int x) {
    vector <int> d1, d2;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            d1.push_back(i);
            if (i * i != x) {
                d2.push_back(x / i);
            }
        }
    }
    reverse(d2.begin(), d2.end());
    for (int i : d2) d1.push_back(i);
    return d1;
}
 
void solve() {
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    vector <int> v(k);
    for (int &i : v) cin >> i;
 
    int g = v[0];
    for (int i : v) g = __gcd(g, i);
    vector <int> divs_g = all_divs(g);
 
    set <int> divs;
    for (int i : all_divs(a)) divs.insert(i);
    for (int i : all_divs(b)) divs.insert(i);
    for (int i : all_divs(c)) divs.insert(i);
    for (int i : all_divs(g)) divs.insert(i);
    int D = divs.size();
    int i = 0;
    for (int j : divs) {
        pos[j] = i;
        i++;
    }
 
    int n = max({a, b, c}) + 1;
    vector < vector <int> > tmp(3, vector <int> (D));
    vector < vector <int> > cnt(3, vector <int> (D));
    for (int t = 0; t < 3; t++) {
        int x;
        if (t == 0) x = a;
        if (t == 1) x = b;
        if (t == 2) x = c;
        vector <int> divs_x = all_divs(x);
 
        for (int i = (int)divs_x.size() - 1; i >= 0; i--) {
            tmp[t][pos[divs_x[i]]] += x / divs_x[i];
            for (int j = 0; j < i; j++) {
                if (divs_x[i] % divs_x[j] == 0) {
                    tmp[t][pos[divs_x[j]]] -= tmp[t][pos[divs_x[i]]];
                }
            }
            cnt[t][pos[x / divs_x[i]]] = tmp[t][pos[divs_x[i]]];
        }
    }
        
    vector < vector <int> > dp(4, vector <int> (D));
    dp[0][0] = 1;
    for(int i = 0; i < 3; i++) {
        for (int t1 : divs_g) {
            for (int t2 : divs_g) {
                int new_pos = lcm(t1, t2);
                if (t2 < n) {
                    dp[i + 1][pos[new_pos]] = (dp[i + 1][pos[new_pos]] + dp[i][pos[t1]] * cnt[i][pos[t2]]) % mod;
                }
            }
        }
    }
 
    int sum = 0;
    i = 0;
    for (int j : divs) {
        if (g % j != 0) continue;
        int N = j, cnt = dp[3][pos[j]];
        vector <int> u;
        for (int t : v) u.push_back(t / N);
        sum = (sum + (MC(u) * cnt) % mod) % mod;
    }
 
    sum = (sum * inv(a * b * c)) % mod;
 
    cout << sum << endl;
}
 
int32_t main() {
    prepare();
 
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
 
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n, k, x = -1;
        cin >> n >> k;
        for (int i = 0; i <= n; i++) {
            if (i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k) {
                x = i;
            }
        }
        if (x == -1)
            cout << "NO\n";
        else {
            cout << "YES\n";
            for (int i = 0; i < n; i++) {
                if (i < x)
                    cout << 1 << ' ';
                else
                    cout << -1 << ' ';
            }
            cout << '\n';
        }
    }

    return 0;
}

for tt in range(int(input())):
    n, k = map(int, input().split())
    x = -1

    for i in range(0, n + 1):
        if i * (i - 1) / 2 + (n - i) * (n - i - 1) / 2 == k:
            x = i

    if x == -1:
        print("NO")
    else:
        print("YES")
        for i in range(0, n):
            if i < x:
                print("1 ", end = '')
            else:
                print("-1 ", end = '')
        print("")

#include <bits/stdc++.h>

using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n, k;
        cin >> n >> k;
        vector <int> p(n);
        for (int i = 0; i < n; i++) {
            cin >> p[i];
            p[i]--;
        }

        int bad = 0;
        for (int i=0; i<n; i++) {
            if (p[i] % k != i % k) {
                bad++;
            }
        }

        if(bad == 0)
            cout << 0 << '\n';
        else if(bad == 2)
            cout << 1 << '\n';
        else
            cout << -1 << '\n';
    }

    return 0;
}

for tt in range(int(input())):
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    for i in range(0, n):
        p[i] -= 1

    bad = 0
    for i in range(0, n):
        if p[i] % k != i % k:
            bad += 1

    if bad == 0:
        print(0)
    elif bad == 2:
        print(1)
    else:
        print(-1)

#include <bits/stdc++.h>

using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        map <int,int> a;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            for (int j = 2; j * j <= x; j++) {
                while (x % j == 0) {
                    x /= j;
                    a[j]++;
                }
            }
            if (x != 1) {
                a[x]++;
            }
        }

        int res = 0, rem = 0;

        for (pair <int, int> p : a) {
            int num = p.first;
            int cnt = p.second;
            res += cnt / 2;
            rem += cnt % 2;
        }

        res += rem / 3;
        cout << res << '\n';
    }

    return 0;
}

def is_prime(x):
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

def is_strongly_composite(x):
    m = []
    i = 2
    while i * i <= x:
        while x % i == 0:
            x = x // i
            m.append(i)
        i += 1
    if not x == 1:
        m.append(i)
    return (len(m) >= 3 or (len(m) == 2 and m[0] == m[1]))

for tt in range(int(input())):
    n = int(input())
    lst = list(map(int, input().split()))
    a = {}
    for x in lst:
        i = 2
        while i * i <= x:
            while x % i == 0:
                x = x // i
                if i in a:
                    a[i] += 1
                else:
                    a[i] = 1
            i += 1
        if x != 1:
            if x in a:
                a[x] += 1
            else:
                a[x] = 1

    res, rem = 0, 0

    for num in a:
        cnt = a[num]
        res += cnt // 2
        rem += cnt % 2

    res += rem // 3
    print(res)

Изначально была более сложная версия этой задачи. Сможете ее решить?

Вам даны $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ ($$$a_i > 1$$$). Вы можете выполнить следующую операцию с массивом $$$a$$$ любое количество раз:

1. выбрать два индекса $$$i$$$ и $$$j$$$ ($$$i < j$$$);

2. удалить элементы $$$a_i$$$ и $$$a_j$$$ из $$$a$$$;

3. вставить элемент $$$a_i \cdot a_j$$$ в $$$a$$$.

После выполнения одной такой операции длина $$$a$$$ уменьшается на единицу.

Назовем массив $$$a$$$ хорошим, если он содержит только сильно составные числа.

Какое минимальное количество операций необходимо выполнить, чтобы сделать массив $$$a$$$ хорошим.

#include <bits/stdc++.h>

using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n, k;
        cin >> n >> k;
        vector <int> x(k), c(k);
        for (int i = 0; i < k; i++)
            cin >> x[i];
        for (int i = 0; i < k; i++)
            cin >> c[i];

        if (c[0] < 3 || c[0] > x[0]) {
            cout << "NO\n";
            continue;
        }

        string s;

        char cur = 'a';
        for (int i = 0; i < c[0] - 3; i++)
            s.push_back('a');

        for (int i = c[0] - 3; i < x[0]; i++) {
            s.push_back(cur);
            cur++;
            if (cur == 'd') cur = 'a';
        }

        bool good = true;
        for (int j = 1; j < k; j++) {
            int dx = x[j] - x[j - 1];
            int dc = c[j] - c[j - 1];
            if (dc > dx) {
                good = false;
                break;
            }

            for (int i = 0; i < dc; i++)
                s.push_back('c' + j);
            for (int i = dc; i < dx; i++) {
                s.push_back(cur);
                cur++;
                if (cur == 'd') cur = 'a';
            }
        }

        if (good)
            cout << "YES" << endl << s << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

for tt in range(int(input())):
    n, k = map(int, input().split())
    x = list(map(int, input().split()))
    c = list(map(int, input().split()))

    if c[0] < 3 or c[0] > x[0]:
        print("NO")
        continue

    s = ""
    cur = 'a'

    for i in range(0, c[0] - 3):
        s += "a"

    for i in range(c[0] - 3, x[0]):
        s += cur
        cur = chr(ord(cur) + 1)
        if cur == 'd':
            cur = 'a'

    good = True
    for j in range(1, k):
        dx = x[j] - x[j - 1]
        dc = c[j] - c[j - 1]
        if dc > dx:
            good = False
            break

        for i in range(0, dc):
            s += chr(ord('c') + j)
        for i in range(dc, dx):
            s += cur
            cur = chr(ord(cur) + 1)
            if cur == 'd':
                cur = 'a'

    if good:
        print("YES")
        print(s)
    else:
        print("NO")

Изначально была упрощенная версия этой задачи с $$$k = 1$$$, но она совпала с другой задачей.

А как в этой задаче работает чекер?

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, l, r;
    cin >> n >> l >> r;
    vector < vector <int> > g(n);
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int res=0, size;
    vector <int> used(n);

    function <void(int)> dfs = [&] (int v) {
        used[v] = true;
        size++;
        for (int to : g[v]) {
            if (!used[to])
                dfs(to);
        }
    };

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            size = 0;
            dfs(i);
            if (size <= l + r - 1) {
                res ^= size / l;
            }
        }
    }

    if (res)
        cout << "Alice\n";
    else
        cout << "Bob\n";

    return 0;
}

from sys import setrecursionlimit
import threading

def main():
    n, l, r = map(int, input().split())

    g = [[] for i in range(0, n)]
    for i in range(0, n):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    res = 0
    used = [False for i in range(0, n)]

    def dfs(v):
        used[v] = True
        size = 1
        for to in g[v]:
            if not used[to]:
                size += dfs(to)
        return size

    for i in range(0, n):
        if not used[i]:
            size = dfs(i)
            if size <= l + r - 1:
                res ^= size // l

    if res:
        print("Alice")
    else:
        print("Bob")

setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()

#include <bits/stdc++.h>
 
using namespace std;
 
const int mod = 998244353;
 
int main(){
    int n, s, t;
    cin >> n >> s >> t;
    s--, t--;
 
    vector < vector <int> > g(n);
    vector <int> previous(n, -1);
    vector <int> inPath(n);
    vector <long long> res(n);
 
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
 
    function <void (int, int)> dfs = [&] (int v, int p) {
        for (int to : g[v]) {
            if (to == p) continue;
            previous[to] = v;
            dfs(to, v);
        }
    };
 
    function <void (int, int, long long)> dfs2 = [&] (int v, int p, long long k) {
        res[v] = k * (long long)g[v].size();
        for (int to : g[v]) {
            if (to == p) continue;
            dfs2(to, v, k);
        }
    };
 
    dfs(s, -1);
 
    int ptr = t;
    inPath[t] = true;
 
    while (ptr != s) {
        res[previous[ptr]] = res[ptr] + 2;
        ptr = previous[ptr];
        inPath[ptr] = true;
    }
 
    for (int v = 0; v < n; v++) {
        if (inPath[v]) {
            res[v] = res[v] / 2 * (long long)g[v].size();
            for (int to : g[v]) {
                if (!inPath[to]) {
                    dfs2(to, v, res[v] / (int)g[v].size());
                }
            }
        }
    }
 
    res[t]++;
 
    for (long long i : res)
        cout << i % mod << ' ';
    cout<<'\n';
 
    return 0;
}

from sys import setrecursionlimit
import threading
 
mod = 998244353
 
def main():
    n, s, t = map(int, input().split())
    s -= 1
    t -= 1
    
    g = [[] for i in range(0, n)]
    previous = [-1 for i in range(0, n)]
    inPath = [False for i in range(0, n)]
    res = [0 for i in range(0, n)]
    
    for i in range(0, n - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)
    
    def dfs(v, p):
        for to in g[v]:
            if to == p:
                continue
            previous[to] = v
            dfs(to, v)
    
    def dfs2(v, p, k):
        res[v] = k * len(g[v])
        for to in g[v]:
            if to == p:
                continue
            dfs2(to, v, k)
    
    dfs(s, -1)
    
    ptr = t
    inPath[t] = True
    
    while ptr != s:
        res[previous[ptr]] = res[ptr] + 2
        ptr = previous[ptr]
        inPath[ptr] = True
    
    for v in range(0, n):
        if inPath[v]:
            res[v] = res[v] // 2 * len(g[v])
            for to in g[v]:
                if not inPath[to]:
                    dfs2(to, v, res[v] // len(g[v]))
    
    res[t] += 1
    
    for i in res:
        print(i % mod, end = ' ')
    print("")
 
setrecursionlimit(10 ** 9)
threading.stack_size(2 ** 27)
thread = threading.Thread(target=main)
thread.start()

#include <iostream>
#include <vector>
#include <functional>

using namespace std;

int main(){
    function <bool()> func=[](){
      vector <bool> a(1,true);
      return a[0];
    };
    
    for(int i=0;i<10;i++)
        cout<<func()<<'\n';

    return 0;
}

I coundn't find, how disable formatting.

==4924==ERROR: AddressSanitizer: heap-use-after-free on address 0x129004d0 at pc 0x00ff646e bp 0x116cf574 sp 0x116cf570 READ of size 4 at 0x129004d0 thread T0 #0 0xff646d in std::_Vb_reference<std::_Wrap_alloc<std::allocator > >::operator bool C:\Program Files (x86)\Microsoft Visual Studio\2017\Enterprise\VC\Tools\MSVC\14.11.25503\include\vector:2213 #1 0xff294d in std::_Invoker_ret<bool,0>::_Call<`lambda at p71.cpp:8:2...

Runtime error: exit code is 1

Used: 46 ms, 16108 KB

#include <iostream>
#include <vector>
#include <functional>

using namespace std;

int main(){
    function <bool()> func=[](){
      vector <bool> a(1,true);
      bool t=a[0];
      return t;
    };
    
    for(int i=0;i<10;i++)
        cout<<func()<<'\n';

    return 0;
}

I solved a problem in Timus, and approximately this function was called several times on sample. In my local Windows G++ 8.1.0 the output was always correct. In Timus the output was incorrect in first call (I got WA1). In Codeforcess::CustomTest the output first 3 times was correct, then incorrect (I mension, that internal body of the function with all variables' values it used was the same). I can show code with this behaviour, but not in public, as except this place, this is the correct solution of some problem.

/**< Будем представлять комплексное число парой (действительная часть, мнимая часть) */
typedef pair <long double,long double> comp;
const long double pi=2*acos(0.0);

/**< Сложение двух комплексных чисел */
comp operator +(comp a,comp b){
    comp c={a.first+b.first,a.second+b.second};
    return c;
}

/**< Разность двух комплексных чисел */
comp operator -(comp a,comp b){
    comp c={a.first-b.first,a.second-b.second};
    return c;
}

/**< Произведение двух комплексных чисел */
comp operator *(comp a,comp b){
    comp c={a.first*b.first-a.second*b.second,a.first*b.second+a.second*b.first};
    return c;
}

/**< Деление комплексного числа на действительное число */
comp operator /(comp a,long double b){
    comp c={a.first/b,a.second/b};
    return c;
}

/**< Будем передавать массивы по ссылке */
void fft(vector <comp> &a){
    int n=a.size();
    if(n==1) return; //Для полинома нулевой степени БПФ - он сам
    vector <comp> a1(n/2),a2(n/2); //Кладем, чередуя, коэффициенты в a1 и a2
    for(int i=0;i<n/2;i++)
        a1[i]=a[i*2],a2[i]=a[i*2+1];
    fft(a1),fft(a2);//Теперь в a1 и a2 - их БПФ
    for(int i=0;i<n/2;i++){
        comp x={cos(2*pi*i/n),sin(2*pi*i/n)}; //Это комплексное число с единичным модулем и аргументом равным 2*pi*i/n
        a[i]=a1[i]+x*a2[i];
        a[i+n/2]=a1[i]-x*a2[i];
    }
}

void revfft(vector <comp> &a){
    int n=a.size();
    if(n==1) return;
    vector <comp> a1(n/2),a2(n/2);
    for(int i=0;i<n/2;i++)
        a1[i]=a[i*2],a2[i]=a[i*2+1];
    revfft(a1),revfft(a2);
    for(int i=0;i<n/2;i++){
        comp x={cos(2*pi*i/n),-sin(2*pi*i/n)}; //Это комплексное число с единичным модулем и аргументом равным -2*pi*i/n
        a[i]=a1[i]+x*a2[i];
        a[i+n/2]=a1[i]-x*a2[i];
        a[i]=a[i]/2; //Глубина рекурсии lb(n), поэтому мы поделим a на 2 всего lb(n) раз, в результате он уменьшится в n раз
        a[i+n/2]=a[i+n/2]/2;
    }
}

vector <int> mult(vector <int> a,vector <int> b){
    /**< Подготовка полиномов */
    vector <comp> fa,fb; //Переводим числа в комплексные
    for(int i=0;i<a.size();i++) fa.push_back({a[i],0});
    for(int i=0;i<b.size();i++) fb.push_back({b[i],0});
    int l=0;
    while(1<<l < a.size()+b.size())
        l++;
    int n=1<<l; //n - наименьшая целая степень числа 2 не меньшая, чем сумма длин данных полиномов
    while(fa.size()<n*2) fa.push_back({0,0}); // Дополняем массивы до размера 2n
    while(fb.size()<n*2) fb.push_back({0,0});

    fft(fa),fft(fb); //Шаг 1
    for(int i=0;i<n*2;i++) //Шаг 2
        fa[i]=fa[i]*fb[i];
    revfft(fa); //Шаг 3

    vector <int> res(fa.size()); // Переводим комплексные числа в целые
    for(int i=0;i<fa.size();i++)
        res[i]=(int)(fa[i].first+0.5);
    while(!res.empty() && res.back()==0) res.pop_back();
    return res;
}

Хотелось бы вставить пояснительную картинку, но как это сделать, я так и не понял.

void fft(vector <comp> &a){
    int n=a.size();

    /**< Сортировка по двоичной форме, записанной зеркально */
    for(int i=1,j=0;i<n;i++){
        int bit=(n>>1);
        while(j>=bit){
            j-=bit;
            bit>>=1;
        }
        j+=bit;
        if(i<j)
            swap(a[i],a[j]);
    }

    for(int len=2;len<=n;len<<=1){ //Строим итеративно БПФ для отрезков длины 2, 4, 8, ... n
        comp w={cos(2*pi/len),sin(2*pi/len)}; //Множитель, умножив на который, мы прокрутим аргумент на один пункт длины 2*pi/len дальше
        for(int i=0;i<n;i+=len){ //Обрабатываем поблочно, i - начало очередного блока
            comp cur_w={1,0}; //Аргумент
            for(int j=0;j<len/2;j++){ //Итерируемся по блоку
                comp u=a[i+j],v=a[i+j+len/2]*cur_w; //Так как записываем в эти элементы массива, их нужно скопировать
                a[i+j]=u+v;
                a[i+j+len/2]=u-v;
                cur_w=cur_w*w; //Прокручиваем аргумент на угол 2*pi/len
            } //Когда мы вышли из цикла, аргумент cur_w снова равен нулю, так как мы добавили 2*pi/len len раз.
        }
    }
}

void revfft(vector <comp> &a){
    int n=a.size();

    /**< Сортировка по двоичной форме, записанной зеркально */
    for(int i=1,j=0;i<n;i++){
        int bit=(n>>1);
        while(j>=bit){
            j-=bit;
            bit>>=1;
        }
        j+=bit;
        if(i<j)
            swap(a[i],a[j]);
    }

    for(int len=2;len<=n;len<<=1){
        comp w={cos(2*pi/len),-sin(2*pi/len)}; //Значения аргумента отображены
        for(int i=0;i<n;i+=len){
            comp cur_w={1,0};
            for(int j=0;j<len/2;j++){
                comp u=a[i+j],v=a[i+j+len/2]*cur_w;
                a[i+j]=u+v;
                a[i+j+len/2]=u-v;
                cur_w=cur_w*w;
            }
        }
    }

    for(int i=0;i<n;i++) //Мы вычислили nW^{-1}, нужно разделить массив на n
        a[i]=a[i]/n;
}

поток:=0;
пока истина:
    найти любой путь из истока в сток p[];
    если путь не нашелся:
        выйти из цикла;
    иначе:
        дополняющий_поток:=min(c[p[i-1]][p[i]]);
        поток+=дополняющий_поток;
        для всех i:=1 до p.size-1:
            c[p[i-1]][p[i]]-=дополняющий_поток;
            c[p[i]][p[i-1]]+=дополняющий_поток;

/**
 * Дано количество вершин и ребер, исток и сток, затем ребра с их пропускными способностями.
 * Везде 0-индексация. Необходимо вывести максимальный поток и матрицу остаточных пропускных способностей.
 */

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;
const int inf=1e9;

int n,m,s,t;//Количество вершин и ребер, исток и сток
int c[1000][1000];//Матрица пропускных способностей

int main(){
    scanf("%d %d %d %d",&n,&m,&s,&t);
    for(int i=0;i<m;i++){
        int a,b,cap;
        scanf("%d %d %d",&a,&b,&cap);
        c[a][b]=cap;
    }

    int MaxFlow=0;//Искомый максимальный поток
    while(true){
        /**< Поиск в ширину */
        vector <int> parent(n,-1);
        vector <bool> used(n,false);
        queue <int> q;

        used[s]=true;
        q.push(s);

        while(!q.empty()){
            int v=q.front();
            q.pop();

            for(int i=0;i<n;i++){
                if(!used[i] && c[v][i]>0){
                    parent[i]=v;
                    used[i]=true;
                    q.push(i);
                }
            }
        }

        if(!used[t])//Не дошли до стока - поток уже максимальный
            break;

        int AugFlow=inf;//Дополнительный поток

        /**< Бежим по пути и ищем ребро с минимальной пропускной способностью */
        int ptr=t;
        while(ptr!=s){
            AugFlow=min(AugFlow,c[parent[ptr]][ptr]);
            ptr=parent[ptr];
        }

        /**< Изменяем пропускные способности */
        ptr=t;
        while(ptr!=s){
            c[parent[ptr]][ptr]-=AugFlow;//По пути вычитаем
            c[ptr][parent[ptr]]+=AugFlow;//Против пути добавляем
            ptr=parent[ptr];
        }

        MaxFlow+=AugFlow;
    }

    /**< Выводим ответ */
    printf("%d\n",MaxFlow);

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%3d ",c[i][j]);
        }
        printf("\n");
    }
    return 0;
}

c[][]
left[];
d[];

функция решить():
    поток:=0;
    пока истина:
        вычислить расстояния до каждой вершины d[];
        если пути до стока нет:
            выйти из цикла;
        заполнить(left[],V,0);
        пока истина:
            дополняющий_поток=протолкнуть(s,inf);
            если дополняющий_поток==0:
                выйти из цикла;
            иначе:
                поток+=дополняющий_поток;
            
функция протолкнуть(вершина,поток):
    если вершина==сток:
        вернуть поток;
    пока left[вершина]<V:
        если d[left[вершина]]+1==d[вершина] и c[вершина][left[вершина]]>0:
            дополняющий_поток=протолкнуть(left[вершина],min(поток,c[вершина][left[вершина]]));
            если дополняющий_поток>0:
                c[вершина][left[вершина]]-=дополняющий_поток;
                c[left[вершина]][вершина]+=дополняющий_поток;
                вернуть дополняющий_поток;
    вернуть 0;

/**
 * Дано количество вершин и ребер, исток и сток, затем ребра с их пропускными способностями.
 * Везде 0-индексация. Необходимо вывести максимальный поток и матрицу остаточных пропускных способностей.
 */

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;
const int inf=1e9;

int n,m,s,t;//Количество вершин и ребер, исток и сток
int c[1000][1000];//Матрица пропускных способностей
int d[1000];//Расстояния
int left[1000];//Самый левый нерассмотренный сосед

/**< Построить слоистую сеть обходом в ширину */
void buildNet(){
    for(int i=0;i<n;i++)
        d[i]=-1;//Пути до вершины нет

    queue <int> q;
    d[s]=0;
    q.push(s);

    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int i=0;i<n;i++){
            if(d[i]==-1 && c[v][i]>0){
                d[i]=d[v]+1;
                q.push(i);
            }
        }
    }
}

/**< Протолкнуть поток обходом в глубину */
int push(int v,int flow){
    /**< Уже прошли какой-то путь из s в v, минимальная пропускная способность - flow */

    if(v==t){//Если зашли в сток, нашли дополняющий путь, возвращаем минимальную пропускную способность на пути, завершаем обход
        return flow;
    }

    for(;left[v]<n;left[v]++){//Перебираем вершины не от начала (без этого алгоритм деградирует!)
        int to=left[v];
        if(d[to]==d[v]+1 && c[v][to]>0){//Если вершина на следующем слое
            int AugFlow=push(to,min(flow,c[v][to]));//Проталкиваем от нее, путь увеличился на ребро c[v][to], поэтому flow возможно уменьшился
            if(AugFlow>0){//Если протолкнули - завершаем обход
                c[v][to]-=AugFlow;//По пути вычитаем
                c[to][v]+=AugFlow;//Против пути добавляем
                return AugFlow;
            }
        }
    }

    return 0;
}

int main(){
    scanf("%d %d %d %d",&n,&m,&s,&t);
    for(int i=0;i<m;i++){
        int a,b,cap;
        scanf("%d %d %d",&a,&b,&cap);
        c[a][b]=cap;
    }

    int MaxFlow=0;//Искомый максимальный поток

    while(true){
        buildNet();//Строим новую слоистую сеть
        if(d[t]==-1)//Если пути до стока нет, поток максимальный
            break;

        for(int i=0;i<n;i++)//Начинаем новые проталкивания
            left[i]=0;

        while(true){
            int AugFlow=push(0,inf);//Проталкиваем из истока, пока минимальная пропускная способность на пути отсутствует
            if(AugFlow==0)//Если не протолкнули, строим новую слоистую сеть
                break;
            else
                MaxFlow+=AugFlow;//Добавляем дополняющий поток
        }
    }

    /**< Выводим ответ */
    printf("%d\n",MaxFlow);

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%3d ",c[i][j]);
        }
        printf("\n");
    }
    return 0;
}

c[][];
e[];
h[];

функция решить():
    e[s]=inf;
    h[s]=n;
    для всех i:=1 до n:
        h[i]:=0;
        если c[s][i]>0:
            протолкнуть(s,i);
    пока есть переполненная вершина i, которая не исток или сток:
        разрядить(i);

функция протолкнуть(откуда,куда):
    величина:=min(e[откуда],c[откуда][куда]);
    e[откуда]-=величина;
    e[куда]+=величина;
    c[откуда][куда]-=величина;
    c[откуда][куда]+=величина;
    
функция поднять(вершина):
    h[вершина]:=1+min(h[i]) для такой i что c[вершина][i]>0, если такой i существует;
    
функция разрядить(вершина):
    пока вершина переполнена:
        для всех i:=1 до n:
            если c[вершина][i]>0 и h[вершина]==h[i]+1:
                протолкнуть(вершина,i);
        поднять(вершина);

/**
 * Дано количество вершин и ребер, исток и сток, затем ребра с их пропускными способностями.
 * Везде 0-индексация. Необходимо вывести максимальный поток и матрицу остаточных пропускных способностей.
 */

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;
const int inf=1e9;

int n,m,s,t;//Количество вершин и ребер, исток и сток
int c[1000][1000];//Матрица пропускных способностей
int e[1000],h[1000];//Переполнение и высота
int MaxFlow=0;//Максимальный поток

/**< Протолкнуть по ребру */
int push(int from,int to){
    int pushed=min(e[from],c[from][to]);//Проталкиваем на столько, на сколько переполнен from, но не более, чем позволит протолкнуть ребро
    if(to==t)//Если протолкнули в сток, добавляем в ответ
        MaxFlow+=pushed;
    e[from]-=pushed;
    e[to]+=pushed;
    c[from][to]-=pushed;
    c[to][from]+=pushed;
    return pushed;
}

/**< Поднять вершину */
void lift(int v){
    /**< Ищем вершину с минимальной высотой и устанавливаем высоту на единицу больше, если таковая есть */
    int New=inf;
    for(int i=0;i<n;i++){
        if(c[v][i]>0){
            New=min(New,h[i]);
        }
    }
    if(New!=inf)
        h[v]=New+1;
}

/**< Разрядить */
void discharge(int v){
    /**< Пока вершина переполнена, проталкиваем во все вершины, затем поднимаем */
    while(e[v]>0){
        for(int i=0;i<n;i++){
            if(c[v][i]>0 && h[v]==h[i]+1){
                push(v,i);
            }
        }
        lift(v);
    }
}

int main(){
    scanf("%d %d %d %d",&n,&m,&s,&t);
    for(int i=0;i<m;i++){
        int a,b,cap;
        scanf("%d %d %d",&a,&b,&cap);
        c[a][b]=cap;
    }

    /**< Начальная инициализация */
    e[s]=inf;
    h[s]=n;
    for(int i=0;i<n;i++){
        if(c[s][i]>0){
            push(s,i);
        }
    }

    while(true){
        bool good=false;//Есть вершины, которые нужно разрядить
        for(int i=0;i<n;i++){
            if(i!=s && i!=t && e[i]>0){
                discharge(i);
                good=true;
            }
        }
        if(!good)//Все вершины разряжены - предпоток есть максимальный поток
            break;
    }

    /**< Выводим ответ */
    printf("%d\n",MaxFlow);

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%3d ",c[i][j]);
        }
        printf("\n");
    }
    return 0;
}

c[][];
e[];
h[];
очередь;

функция решить():
    e[s]=inf;
    h[s]=n;
    для всех i:=1 до n:
        h[i]:=0;
        если c[s][i]>0:
            протолкнуть(s,i);
    пока очередь не пуста:
        разрядить(очередь.начало);
        очередь.удалить_начало;

функция протолкнуть(откуда,куда):
    величина:=min(e[откуда],c[откуда][куда]);
    если e[куда]==0 и куда не исток или сток:
        положить куда в очередь;
    e[откуда]-=величина;
    e[куда]+=величина;
    c[откуда][куда]-=величина;
    c[откуда][куда]+=величина;
    
функция поднять(вершина):
    h[вершина]:=1+min(h[i]) для такой i что c[вершина][i]>0, если такой i существует;
    
функция разрядить(вершина):
    пока вершина переполнена:
        для всех i:=1 до n:
           если c[вершина][i]>0 и h[вершина]==h[i]+1:
                протолкнуть(вершина,i);
        поднять(вершина);

/**
 * Дано количество вершин и ребер, исток и сток, затем ребра с их пропускными способностями.
 * Везде 0-индексация. Необходимо вывести максимальный поток и матрицу остаточных пропускных способностей.
 */

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;
const int inf=1e9;

int n,m,s,t;//Количество вершин и ребер, исток и сток
int c[1000][1000];//Матрица пропускных способностей
int e[1000],h[1000];//Переполнение и высота
int MaxFlow=0;//Максимальный поток
queue <int> q;//Очередь

/**< Протолкнуть по ребру */
int push(int from,int to){
    int pushed=min(e[from],c[from][to]);//Проталкиваем на столько, на сколько переполнен from, но не более, чем позволит протолкнуть ребро
    if(to==t)//Если протолкнули в сток, добавляем в ответ
        MaxFlow+=pushed;
    if(e[to]==0 && to!=t)//Вершина to не была переполненной, а теперь переполненна
        q.push(to);
    e[from]-=pushed;
    e[to]+=pushed;
    c[from][to]-=pushed;
    c[to][from]+=pushed;
    return pushed;
}

/**< Поднять вершину */
void lift(int v){
    /**< Ищем вершину с минимальной высотой и устанавливаем высоту на единицу больше, если таковая есть */
    int New=inf;
    for(int i=0;i<n;i++){
        if(c[v][i]>0){
            New=min(New,h[i]);
        }
    }
    if(New!=inf)
        h[v]=New+1;
}

/**< Разрядить */
void discharge(int v){
    /**< Пока вершина переполнена, проталкиваем во все вершины, затем поднимаем */
    while(e[v]>0){
        for(int i=0;i<n;i++){
            if(c[v][i]>0 && h[v]==h[i]+1){
                push(v,i);
            }
        }
        lift(v);
    }
}

int main(){
    scanf("%d %d %d %d",&n,&m,&s,&t);
    for(int i=0;i<m;i++){
        int a,b,cap;
        scanf("%d %d %d",&a,&b,&cap);
        c[a][b]=cap;
    }

    /**< Начальная инициализация */
    e[s]=inf;
    h[s]=n;
    for(int i=0;i<n;i++){
        if(c[s][i]>0){
            push(s,i);
        }
    }

    /**< Пока есть переполненные вершины - разрядить */
    while(!q.empty()){
        int v=q.front();
        q.pop();
        discharge(v);
    }

    /**< Выводим ответ */
    printf("%d\n",MaxFlow);

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%3d ",c[i][j]);
        }
        printf("\n");
    }
    return 0;
}

...