oj.uz

Submission #1086981

# Submission time Handle Problem Language Result Execution time Memory
1086981 2024-09-12T01:35:34 Z Ausp3x Digital Circuit (IOI22_circuit) C++17
100 / 100
 866 ms 52468 KB 
// 人外有人，天外有天
// author: Ausp3x

#pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define pb push_back
// #define DEBUG
#ifndef DEBUG
#include "circuit.h"
#endif
typedef long long    lng;
typedef __int128     lll;
template<class T> 
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int const INF32 = 0x3f3f3f3f;
lng const INF64 = 0x3f3f3f3f3f3f3f3f;

lng N, M;
vector<int> P;
vector<lng> A;
vector<vector<int>> adjl;

struct ModInt {
    lng const MOD = 1'000'002'022;
    lng const PHI_MOD = 497'758'632;
    lng exp_2 = 0, exp_223 = 0, rem = 0;

    void init(lng x) {
        while (x % 2 == 0 && x > 0) {
            exp_2++;
            x /= 2;
        }

        while (x % 223 == 0 && x > 0) {
            exp_223++;
            x /= 223;
        }

        rem = x % MOD;
    }

    void copy(ModInt const &x) {
        exp_2 = x.exp_2;
        exp_223 = x.exp_223;
        rem = x.rem;
    }

    void multiplyBy(ModInt const &x) {
        exp_2 += x.exp_2;
        exp_223 += x.exp_223;
        rem *= x.rem;
        rem %= MOD;

        return;
    }

    // only works when divisible by x
    void divideBy(ModInt const &x) {
        assert(exp_2 >= x.exp_2);
        assert(exp_223 >= x.exp_223);

        exp_2 -= x.exp_2;
        exp_223 -= x.exp_223;
        rem *= modPow(x.rem, PHI_MOD - 1, MOD);
        rem %= MOD;
    
        return;
    }

    lng getValue() {
        return modPow(2, exp_2, MOD) * modPow(223, exp_223, MOD) % MOD * rem % MOD;
    }
    
    lng modPow(lng x, lng y, lng mod) {
        lng res = 1;
        while (y > 0) {
            if (y & 1) {
                res *= x;
                res %= mod;
            }

            y >>= 1;
            x *= x;
            x %= mod;
        }

        return (res + mod) % mod;
    }
};

struct SegTree {
    lng const MOD = 1'000'002'022;
    int l, r;
    lng ttl = 0; // must be constant after initialization
    lng sum = 0, upd = 0;
    SegTree *l_child, *r_child;

    template<class T> 
    SegTree(int l, int r, const vector<T> &arr): l(l), r(r) {
        if (l == r) {
            ttl = arr[l];
            sum = arr[l];
            l_child = r_child = nullptr;
        } else {
            int m = (l + r) / 2;
            l_child = new SegTree(l, m, arr);
            r_child = new SegTree(m + 1, r, arr);
            ttl = (l_child->ttl + r_child->ttl) % MOD;
            sum = (l_child->sum + r_child->sum) % MOD;
        }
    }

    // push updates down to children
    void push() {
        if (l_child != nullptr && r_child != nullptr) {
            l_child->upd += upd;
            l_child->upd %= 2;
            if (upd)
                l_child->reverseSum();
            r_child->upd += upd;
            r_child->upd %= 2;
            if (upd)
                r_child->reverseSum();
            upd = 0;
        }

        return;
    }

    // pull states up from children
    void pull() {
        assert(upd == 0);
        if (l_child != nullptr && r_child != nullptr) {
            sum = (l_child->sum + r_child->sum) % MOD;
        }

        return;
    }

    void rangeSumUpdate(int cur_l, int cur_r) {
        if (cur_l > cur_r || (r < cur_l || cur_r < l)) {
            return;
        }

        if (cur_l <= l && r <= cur_r) {
            upd++;
            upd %= 2;
            reverseSum();
            return;
        }
        
        push();
        l_child->rangeSumUpdate(cur_l, cur_r);
        r_child->rangeSumUpdate(cur_l, cur_r);
        pull();
        return;
    }

    lng rangeSumQuery(int cur_l, int cur_r) {
        if (cur_l > cur_r || (r < cur_l || cur_r < l)) {
            return 0;
        } 
        
        if (cur_l <= l && r <= cur_r) {
            return sum;
        }
        
        push();
        return (l_child->rangeSumQuery(cur_l, cur_r) + r_child->rangeSumQuery(cur_l, cur_r)) % MOD;
    }

    void reverseSum() {
        sum = (ttl - sum + MOD) % MOD;
    }

    void debugPrint(int depth = 0) {
        for (int t = 0; t < depth; t++) {
            cout << '\t';
        }
        cout << "[" << l << ", " << r << "] has ttl " << ttl << ", has sum " << sum << ", and upd " << upd << endl;
        if (l_child != nullptr && r_child != nullptr) {
            l_child->debugPrint(depth + 1);
            r_child->debugPrint(depth + 1);
        }

        return;
    }
};

// TODO: W must be ModInt
vector<ModInt> W;
void initW(int cur, int prv) {
    if (cur >= N)
        return;

    W[cur].init(adjl[cur].size() - (cur != 0));
    for (int nxt : adjl[cur]) {
        if (nxt == prv)
            continue;

        initW(nxt, cur);

        W[cur].multiplyBy(W[nxt]);
    }

    return;
}

vector<ModInt> C;
void initC(int cur, int prv) {
    ModInt cnt;
    cnt.init(adjl[cur].size() - (cur != 0));
    for (int nxt : adjl[cur]) {
        if (nxt == prv)
            continue;

        C[nxt].copy(C[cur]);
        C[nxt].divideBy(cnt);

        initC(nxt, cur);
    }
    
    return;
}

SegTree *segt = nullptr;
void init(int _N, int _M, vector<int> _P, vector<int> _A) {
    N = _N;
    M = _M;
    P.clear();
    P.resize(N + M);
    for (int i = 0; i < N + M; i++)
        P[i] = _P[i];
    A.clear();
    A.resize(M);
    for (int i = 0; i < M; i++)
        A[i] = _A[i];

    adjl.clear();
    adjl.resize(N + M);
    for (int i = 1; i < N + M; i++) {
        adjl[P[i]].pb(i);
        adjl[i].pb(P[i]);
    }

    W.clear();
    W.resize(N + M);
    for (int i = 0; i < N + M; i++)
        W[i].init(1);
    initW(0, 0);

    C.clear();
    C.resize(N + M);
    C[0].copy(W[0]);
    initC(0, 0);

    vector<lng> C_ints(M);
    for (int i = 0; i < M; i++) 
        C_ints[i] = C[i + N].getValue();

    segt = new SegTree(0, M - 1, C_ints);
    for (int i = 0; i < M; i++)
        if (!A[i])
            segt->rangeSumUpdate(i, i);

    // segt->debugPrint();

    return;
}

int count_ways(int L, int R) {
    L -= N;
    R -= N;
    segt->rangeSumUpdate(L, R);
    // segt->debugPrint();

    return segt->rangeSumQuery(0, M - 1);
}

#ifdef DEBUG
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    // cin >> t;
    while (t--) {
        int _N, _M, Q;
        cin >> _N >> _M >> Q;
        vector<int> _P(_N + _M);
        for (int &p : _P)
            cin >> p;
        vector<int> _A(_M);
        for (int &a : _A)
            cin >> a;

        init(_N, _M, _P, _A);

        while (Q--) {
            int L, R;
            cin >> L >> R;

            cout << count_ways(L, R) << endl; 
        }
    }

    return 0;
}
#endif

Compilation message

circuit.cpp:4:55: warning: bad option '-f O2' to pragma 'optimize' [-Wpragmas]
    4 | #pragma GCC optimize("O1, O2, O3, Ofast, unroll-loops")
      |                                                       ^
circuit.cpp:4:55: warning: bad option '-f O3' to pragma 'optimize' [-Wpragmas]
circuit.cpp:4:55: warning: bad option '-f Ofast' to pragma 'optimize' [-Wpragmas]
circuit.cpp:4:55: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
In file included from circuit.cpp:15:
circuit.h:3:63: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
    3 | void init(int N, int M, std::vector<int> P, std::vector<int> A);
      |                                                               ^
circuit.h:3:63: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.h:3:63: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.h:3:63: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.h:3:63: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
circuit.h:3:63: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.h:3:63: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.h:3:63: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.h:4:28: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
    4 | int count_ways(int L, int R);
      |                            ^
circuit.h:4:28: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.h:4:28: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.h:4:28: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.h:4:28: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
circuit.h:4:28: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.h:4:28: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.h:4:28: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:35:20: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   35 |     void init(lng x) {
      |                    ^
circuit.cpp:35:20: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:35:20: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:35:20: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:49:30: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   49 |     void copy(ModInt const &x) {
      |                              ^
circuit.cpp:49:30: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:49:30: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:49:30: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:55:36: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   55 |     void multiplyBy(ModInt const &x) {
      |                                    ^
circuit.cpp:55:36: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:55:36: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:55:36: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:65:34: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   65 |     void divideBy(ModInt const &x) {
      |                                  ^
circuit.cpp:65:34: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:65:34: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:65:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:77:18: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   77 |     lng getValue() {
      |                  ^
circuit.cpp:77:18: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:77:18: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:77:18: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:81:37: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
   81 |     lng modPow(lng x, lng y, lng mod) {
      |                                     ^
circuit.cpp:81:37: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:81:37: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:81:37: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:106:47: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  106 |     SegTree(int l, int r, const vector<T> &arr): l(l), r(r) {
      |                                               ^
circuit.cpp:106:47: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:106:47: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:106:47: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:121:15: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  121 |     void push() {
      |               ^
circuit.cpp:121:15: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:121:15: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:121:15: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:138:15: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  138 |     void pull() {
      |               ^
circuit.cpp:138:15: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:138:15: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:138:15: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:147:45: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  147 |     void rangeSumUpdate(int cur_l, int cur_r) {
      |                                             ^
circuit.cpp:147:45: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:147:45: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:147:45: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:166:43: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  166 |     lng rangeSumQuery(int cur_l, int cur_r) {
      |                                           ^
circuit.cpp:166:43: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:166:43: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:166:43: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:179:21: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  179 |     void reverseSum() {
      |                     ^
circuit.cpp:179:21: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:179:21: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:179:21: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:183:34: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  183 |     void debugPrint(int depth = 0) {
      |                                  ^
circuit.cpp:183:34: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:183:34: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:183:34: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:199:28: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  199 | void initW(int cur, int prv) {
      |                            ^
circuit.cpp:199:28: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:199:28: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:199:28: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:217:28: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  217 | void initC(int cur, int prv) {
      |                            ^
circuit.cpp:217:28: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:217:28: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:217:28: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:234:57: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  234 | void init(int _N, int _M, vector<int> _P, vector<int> _A) {
      |                                                         ^
circuit.cpp:234:57: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:234:57: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:234:57: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
circuit.cpp:278:28: warning: bad option '-f O2' to attribute 'optimize' [-Wattributes]
  278 | int count_ways(int L, int R) {
      |                            ^
circuit.cpp:278:28: warning: bad option '-f O3' to attribute 'optimize' [-Wattributes]
circuit.cpp:278:28: warning: bad option '-f Ofast' to attribute 'optimize' [-Wattributes]
circuit.cpp:278:28: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 600 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 600 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 856 KB Output is correct
16 Correct 1 ms 856 KB Output is correct
17 Correct 1 ms 856 KB Output is correct
18 Correct 1 ms 856 KB Output is correct
19 Correct 1 ms 856 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 2 ms 600 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Correct 1 ms 856 KB Output is correct
25 Correct 2 ms 856 KB Output is correct
26 Correct 1 ms 856 KB Output is correct
27 Correct 1 ms 856 KB Output is correct
28 Correct 1 ms 856 KB Output is correct
29 Correct 1 ms 600 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 1 ms 856 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 1 ms 600 KB Output is correct
35 Correct 1 ms 600 KB Output is correct
36 Correct 1 ms 856 KB Output is correct
37 Correct 1 ms 812 KB Output is correct
38 Correct 1 ms 812 KB Output is correct
39 Correct 1 ms 600 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 1 ms 600 KB Output is correct
42 Correct 1 ms 600 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 14672 KB Output is correct
2 Correct 710 ms 29000 KB Output is correct
3 Correct 679 ms 29008 KB Output is correct
4 Correct 711 ms 29008 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 14672 KB Output is correct
2 Correct 710 ms 29000 KB Output is correct
3 Correct 679 ms 29008 KB Output is correct
4 Correct 711 ms 29008 KB Output is correct
5 Correct 564 ms 14672 KB Output is correct
6 Correct 712 ms 29024 KB Output is correct
7 Correct 752 ms 29004 KB Output is correct
8 Correct 720 ms 29008 KB Output is correct
9 Correct 317 ms 1320 KB Output is correct
10 Correct 670 ms 2220 KB Output is correct
11 Correct 648 ms 2216 KB Output is correct
12 Correct 619 ms 2212 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 1 ms 856 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 480 ms 14672 KB Output is correct
14 Correct 710 ms 29000 KB Output is correct
15 Correct 679 ms 29008 KB Output is correct
16 Correct 711 ms 29008 KB Output is correct
17 Correct 564 ms 14672 KB Output is correct
18 Correct 712 ms 29024 KB Output is correct
19 Correct 752 ms 29004 KB Output is correct
20 Correct 720 ms 29008 KB Output is correct
21 Correct 317 ms 1320 KB Output is correct
22 Correct 670 ms 2220 KB Output is correct
23 Correct 648 ms 2216 KB Output is correct
24 Correct 619 ms 2212 KB Output is correct
25 Correct 767 ms 43344 KB Output is correct
26 Correct 851 ms 44108 KB Output is correct
27 Correct 866 ms 44108 KB Output is correct
28 Correct 655 ms 44100 KB Output is correct
29 Correct 853 ms 52048 KB Output is correct
30 Correct 768 ms 52048 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 856 KB Output is correct
16 Correct 1 ms 856 KB Output is correct
17 Correct 1 ms 856 KB Output is correct
18 Correct 1 ms 856 KB Output is correct
19 Correct 1 ms 856 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 2 ms 600 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Correct 1 ms 856 KB Output is correct
25 Correct 2 ms 856 KB Output is correct
26 Correct 1 ms 856 KB Output is correct
27 Correct 1 ms 856 KB Output is correct
28 Correct 1 ms 856 KB Output is correct
29 Correct 1 ms 600 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 1 ms 856 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 1 ms 600 KB Output is correct
35 Correct 1 ms 600 KB Output is correct
36 Correct 1 ms 856 KB Output is correct
37 Correct 1 ms 812 KB Output is correct
38 Correct 1 ms 812 KB Output is correct
39 Correct 1 ms 600 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 1 ms 600 KB Output is correct
42 Correct 1 ms 600 KB Output is correct
43 Correct 457 ms 1660 KB Output is correct
44 Correct 618 ms 1752 KB Output is correct
45 Correct 640 ms 1760 KB Output is correct
46 Correct 674 ms 2624 KB Output is correct
47 Correct 653 ms 2648 KB Output is correct
48 Correct 630 ms 2648 KB Output is correct
49 Correct 632 ms 2648 KB Output is correct
50 Correct 691 ms 2648 KB Output is correct
51 Correct 567 ms 1908 KB Output is correct
52 Correct 643 ms 1912 KB Output is correct
53 Correct 578 ms 1528 KB Output is correct
54 Correct 649 ms 2616 KB Output is correct
55 Correct 693 ms 2252 KB Output is correct
56 Correct 663 ms 2080 KB Output is correct
57 Correct 630 ms 1892 KB Output is correct
58 Correct 691 ms 3000 KB Output is correct
59 Correct 645 ms 3020 KB Output is correct
60 Correct 626 ms 3028 KB Output is correct
61 Correct 623 ms 1768 KB Output is correct
62 Correct 644 ms 1760 KB Output is correct
63 Correct 586 ms 1748 KB Output is correct
64 Correct 601 ms 1924 KB Output is correct
65 Correct 336 ms 1320 KB Output is correct
66 Correct 642 ms 2212 KB Output is correct
67 Correct 657 ms 2212 KB Output is correct
68 Correct 636 ms 2216 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 2 ms 856 KB Output is correct
16 Correct 1 ms 856 KB Output is correct
17 Correct 1 ms 856 KB Output is correct
18 Correct 1 ms 856 KB Output is correct
19 Correct 1 ms 856 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 2 ms 600 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 1 ms 600 KB Output is correct
24 Correct 1 ms 856 KB Output is correct
25 Correct 2 ms 856 KB Output is correct
26 Correct 1 ms 856 KB Output is correct
27 Correct 1 ms 856 KB Output is correct
28 Correct 1 ms 856 KB Output is correct
29 Correct 1 ms 600 KB Output is correct
30 Correct 1 ms 600 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 1 ms 856 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 1 ms 600 KB Output is correct
35 Correct 1 ms 600 KB Output is correct
36 Correct 1 ms 856 KB Output is correct
37 Correct 1 ms 812 KB Output is correct
38 Correct 1 ms 812 KB Output is correct
39 Correct 1 ms 600 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 1 ms 600 KB Output is correct
42 Correct 1 ms 600 KB Output is correct
43 Correct 480 ms 14672 KB Output is correct
44 Correct 710 ms 29000 KB Output is correct
45 Correct 679 ms 29008 KB Output is correct
46 Correct 711 ms 29008 KB Output is correct
47 Correct 564 ms 14672 KB Output is correct
48 Correct 712 ms 29024 KB Output is correct
49 Correct 752 ms 29004 KB Output is correct
50 Correct 720 ms 29008 KB Output is correct
51 Correct 317 ms 1320 KB Output is correct
52 Correct 670 ms 2220 KB Output is correct
53 Correct 648 ms 2216 KB Output is correct
54 Correct 619 ms 2212 KB Output is correct
55 Correct 767 ms 43344 KB Output is correct
56 Correct 851 ms 44108 KB Output is correct
57 Correct 866 ms 44108 KB Output is correct
58 Correct 655 ms 44100 KB Output is correct
59 Correct 853 ms 52048 KB Output is correct
60 Correct 768 ms 52048 KB Output is correct
61 Correct 457 ms 1660 KB Output is correct
62 Correct 618 ms 1752 KB Output is correct
63 Correct 640 ms 1760 KB Output is correct
64 Correct 674 ms 2624 KB Output is correct
65 Correct 653 ms 2648 KB Output is correct
66 Correct 630 ms 2648 KB Output is correct
67 Correct 632 ms 2648 KB Output is correct
68 Correct 691 ms 2648 KB Output is correct
69 Correct 567 ms 1908 KB Output is correct
70 Correct 643 ms 1912 KB Output is correct
71 Correct 578 ms 1528 KB Output is correct
72 Correct 649 ms 2616 KB Output is correct
73 Correct 693 ms 2252 KB Output is correct
74 Correct 663 ms 2080 KB Output is correct
75 Correct 630 ms 1892 KB Output is correct
76 Correct 691 ms 3000 KB Output is correct
77 Correct 645 ms 3020 KB Output is correct
78 Correct 626 ms 3028 KB Output is correct
79 Correct 623 ms 1768 KB Output is correct
80 Correct 644 ms 1760 KB Output is correct
81 Correct 586 ms 1748 KB Output is correct
82 Correct 601 ms 1924 KB Output is correct
83 Correct 336 ms 1320 KB Output is correct
84 Correct 642 ms 2212 KB Output is correct
85 Correct 657 ms 2212 KB Output is correct
86 Correct 636 ms 2216 KB Output is correct
87 Correct 1 ms 344 KB Output is correct
88 Correct 539 ms 38052 KB Output is correct
89 Correct 742 ms 26192 KB Output is correct
90 Correct 750 ms 26960 KB Output is correct
91 Correct 751 ms 44360 KB Output is correct
92 Correct 789 ms 44488 KB Output is correct
93 Correct 818 ms 44368 KB Output is correct
94 Correct 828 ms 44368 KB Output is correct
95 Correct 826 ms 44368 KB Output is correct
96 Correct 712 ms 30176 KB Output is correct
97 Correct 762 ms 29944 KB Output is correct
98 Correct 655 ms 22608 KB Output is correct
99 Correct 802 ms 44124 KB Output is correct
100 Correct 747 ms 36944 KB Output is correct
101 Correct 798 ms 33616 KB Output is correct
102 Correct 754 ms 30032 KB Output is correct
103 Correct 746 ms 52048 KB Output is correct
104 Correct 772 ms 52420 KB Output is correct
105 Correct 755 ms 52468 KB Output is correct
106 Correct 783 ms 25420 KB Output is correct
107 Correct 722 ms 25940 KB Output is correct
108 Correct 752 ms 27652 KB Output is correct
109 Correct 699 ms 30316 KB Output is correct