oj.uz

Submission #680648

# Submission time Handle Problem Language Result Execution time Memory
680648 2023-01-11T12:14:00 Z aidfnbvosdnvla Nice sequence (IZhO18_sequence) C++14
76 / 100
 2000 ms 50052 KB 
//#pragma GCC optimize("O3")
//#pragma gcc optimize("sse,sse2,sse3,sse4,ssse3")
//#pragma gcc optimize("abm,mmx,avx,avx2,fast-math,section-anchors")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("popcnt")

#define _USE_MATH_DEFINES

//#include <_ctype.h>
//#include <immintrin.h>
#include <math.h>

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

//#define INF ((int)2e9)
#define INF ((int)2e9)
#define INF_LL ((int64_t)1e18 + 57)
#define filin(x) freopen(x, "r", stdin)
#define filout(x) freopen(x, "w", stdout)

typedef int64_t ll;
// typedef int ll;
typedef long double ld;

//#define int int64_t

#ifndef __APPLE__
#define FAST_ALLOCATOR_MEMORY (2e8 + 5e7)
#endif

#ifdef FAST_ALLOCATOR_MEMORY
// int allocator_pos = 0;
// char allocator_memory[(int)FAST_ALLOCATOR_MEMORY];
// void *operator new(size_t n) {
//    char *res = allocator_memory + allocator_pos;
//    allocator_pos += n; //
//    // assert(allocator_pos <= (int)FAST_ALLOCATOR_MEMORY);
//    return (void *)res;
//}
// void operator delete(void *) noexcept {}
#endif

struct h228 {
    uint64_t operator()(const int &x) const {
        return ((uint64_t)x * (uint64_t)x + 3) % (uint64_t)(1e9 + 7);
    }
};

#ifndef __APPLE__
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define unordered_map gp_hash_table
#endif

bool dfs(vector<vector<int>> &g, vector<int> &vis, int lim, int v) {
    vis[v] = 1;
    for (auto &it : g[v])
        if (it <= lim) {
            if (vis[it] == 1)
                return true;
            if (vis[it] == 0)
                if (dfs(g, vis, lim, it))
                    return true;
        }
    vis[v] = 2;
    return false;
}

void dpfs(vector<vector<int>> &g, vector<int> &vis, vector<int> &st, int lim,
          int v) {
    vis[v] = 1;
    for (auto &it : g[v])
        if (it <= lim) {
            if (vis[it] == 0) {
                dpfs(g, vis, st, lim, it);
            }
        }
    st.push_back(v);
}

signed solve(int n, int m) {
    int l = 0, r = n + m;
    vector<vector<int>> g(r + 1);
    for (int i = 1; i <= r; ++i) {
        if (i >= n)
            g[i - n].push_back(i);
        if (i >= m)
            g[i].push_back(i - m);
    }
    while (r - l > 1) {
        int k = (l + r) / 2;
        //    for (int k = r - 1; k > l; --k) {
        vector<int> vis(k + 1);
        bool ok = true;
        for (int i = 0; i <= k; ++i)
            if (vis[i] == 0 && dfs(g, vis, k, i)) {
                ok = false;
                break;
            }
        if (ok)
            l = k;
        else
            r = k;
    }
    vector<int> vis(l + 1, 0);
    vector<int> st;
    for (int i = 0; i <= l; ++i)
        if (vis[i] == 0)
            dpfs(g, vis, st, l, i);
    for (int i = 0; i <= l; ++i)
        vis[st[i]] = i;
    cout << l << "\n";
    for (int i = 1; i <= l; ++i) {
        cout << vis[i] - vis[i - 1] << " ";
    }
    cout << "\n";
    return 0;
}

signed main() {
    (*cin.tie(0)).sync_with_stdio(0);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int r = solve(n, m);
        if (r != 0)
            return r;
        //        cout << "\n";
    }

    return 0;
}
//
// 3
// 3 1
// 2 3
// 1 1

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 0 ms 212 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 212 KB Ok
12 Correct 1 ms 212 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 0 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 4 ms 596 KB Ok
7 Correct 31 ms 1756 KB Ok
8 Correct 15 ms 1008 KB Ok
9 Correct 25 ms 2024 KB Ok
10 Correct 14 ms 1352 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 0 ms 212 KB Ok
4 Correct 0 ms 212 KB Ok
5 Correct 0 ms 212 KB Ok
6 Correct 0 ms 212 KB Ok
7 Correct 0 ms 212 KB Ok
8 Correct 1 ms 212 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 1 ms 212 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 0 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 274 ms 23692 KB Ok
7 Correct 266 ms 29888 KB Ok
8 Correct 564 ms 33464 KB Ok
9 Correct 341 ms 29676 KB Ok
10 Correct 182 ms 16288 KB Ok
11 Correct 285 ms 28992 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 0 ms 212 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 212 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 0 ms 212 KB Ok
14 Correct 0 ms 212 KB Ok
15 Correct 0 ms 212 KB Ok
16 Correct 0 ms 212 KB Ok
17 Correct 0 ms 212 KB Ok
18 Correct 0 ms 212 KB Ok
19 Correct 0 ms 212 KB Ok
20 Correct 1 ms 212 KB Ok
21 Correct 1 ms 212 KB Ok
22 Correct 1 ms 212 KB Ok
23 Correct 1 ms 212 KB Ok
24 Correct 5 ms 468 KB Ok
25 Correct 4 ms 596 KB Ok
26 Correct 6 ms 468 KB Ok
27 Correct 4 ms 596 KB Ok
28 Correct 3 ms 468 KB Ok
29 Correct 3 ms 596 KB Ok
30 Correct 4 ms 512 KB Ok
31 Correct 4 ms 596 KB Ok
32 Correct 4 ms 468 KB Ok
33 Correct 4 ms 468 KB Ok
34 Correct 10 ms 852 KB Ok
35 Correct 9 ms 896 KB Ok
36 Correct 10 ms 964 KB Ok
37 Correct 10 ms 916 KB Ok
38 Correct 12 ms 980 KB Ok
39 Correct 8 ms 852 KB Ok
40 Correct 13 ms 852 KB Ok
41 Correct 9 ms 948 KB Ok
42 Correct 12 ms 952 KB Ok
43 Correct 10 ms 980 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 0 ms 212 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 212 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 0 ms 212 KB Ok
15 Correct 0 ms 212 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 4 ms 596 KB Ok
19 Correct 31 ms 1756 KB Ok
20 Correct 15 ms 1008 KB Ok
21 Correct 25 ms 2024 KB Ok
22 Correct 14 ms 1352 KB Ok
23 Correct 0 ms 212 KB Ok
24 Correct 0 ms 212 KB Ok
25 Correct 0 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 0 ms 212 KB Ok
28 Correct 0 ms 212 KB Ok
29 Correct 0 ms 212 KB Ok
30 Correct 1 ms 212 KB Ok
31 Correct 1 ms 212 KB Ok
32 Correct 1 ms 212 KB Ok
33 Correct 1 ms 212 KB Ok
34 Correct 5 ms 468 KB Ok
35 Correct 4 ms 596 KB Ok
36 Correct 6 ms 468 KB Ok
37 Correct 4 ms 596 KB Ok
38 Correct 3 ms 468 KB Ok
39 Correct 3 ms 596 KB Ok
40 Correct 4 ms 512 KB Ok
41 Correct 4 ms 596 KB Ok
42 Correct 4 ms 468 KB Ok
43 Correct 4 ms 468 KB Ok
44 Correct 10 ms 852 KB Ok
45 Correct 9 ms 896 KB Ok
46 Correct 10 ms 964 KB Ok
47 Correct 10 ms 916 KB Ok
48 Correct 12 ms 980 KB Ok
49 Correct 8 ms 852 KB Ok
50 Correct 13 ms 852 KB Ok
51 Correct 9 ms 948 KB Ok
52 Correct 12 ms 952 KB Ok
53 Correct 10 ms 980 KB Ok
54 Correct 181 ms 8284 KB Ok
55 Correct 246 ms 9408 KB Ok
56 Correct 199 ms 9556 KB Ok
57 Correct 166 ms 8952 KB Ok
58 Correct 163 ms 9372 KB Ok
59 Correct 152 ms 9616 KB Ok
60 Correct 162 ms 7544 KB Ok
61 Correct 131 ms 8928 KB Ok
62 Correct 192 ms 9776 KB Ok
63 Correct 150 ms 7604 KB Ok
64 Correct 193 ms 8488 KB Ok
65 Correct 158 ms 10524 KB Ok
66 Correct 168 ms 8136 KB Ok
67 Correct 175 ms 9436 KB Ok
68 Correct 182 ms 9992 KB Ok
69 Correct 824 ms 22016 KB Ok
70 Correct 785 ms 21256 KB Ok
71 Correct 654 ms 20576 KB Ok
72 Correct 761 ms 20832 KB Ok
73 Correct 751 ms 19436 KB Ok
74 Correct 692 ms 19280 KB Ok
75 Correct 712 ms 19748 KB Ok
76 Correct 805 ms 20780 KB Ok
77 Correct 717 ms 21188 KB Ok
78 Correct 664 ms 21240 KB Ok
79 Correct 895 ms 20052 KB Ok
80 Correct 701 ms 20432 KB Ok
81 Correct 702 ms 21288 KB Ok
82 Correct 723 ms 21324 KB Ok
83 Correct 588 ms 19544 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 0 ms 212 KB Ok
3 Correct 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 0 ms 212 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 212 KB Ok
11 Correct 0 ms 212 KB Ok
12 Correct 1 ms 212 KB Ok
13 Correct 1 ms 212 KB Ok
14 Correct 0 ms 212 KB Ok
15 Correct 0 ms 212 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 4 ms 596 KB Ok
19 Correct 31 ms 1756 KB Ok
20 Correct 15 ms 1008 KB Ok
21 Correct 25 ms 2024 KB Ok
22 Correct 14 ms 1352 KB Ok
23 Correct 0 ms 212 KB Ok
24 Correct 0 ms 212 KB Ok
25 Correct 0 ms 212 KB Ok
26 Correct 0 ms 212 KB Ok
27 Correct 0 ms 212 KB Ok
28 Correct 0 ms 212 KB Ok
29 Correct 0 ms 212 KB Ok
30 Correct 1 ms 212 KB Ok
31 Correct 1 ms 212 KB Ok
32 Correct 1 ms 212 KB Ok
33 Correct 1 ms 212 KB Ok
34 Correct 0 ms 212 KB Ok
35 Correct 0 ms 212 KB Ok
36 Correct 1 ms 212 KB Ok
37 Correct 0 ms 212 KB Ok
38 Correct 1 ms 212 KB Ok
39 Correct 274 ms 23692 KB Ok
40 Correct 266 ms 29888 KB Ok
41 Correct 564 ms 33464 KB Ok
42 Correct 341 ms 29676 KB Ok
43 Correct 182 ms 16288 KB Ok
44 Correct 285 ms 28992 KB Ok
45 Correct 5 ms 468 KB Ok
46 Correct 4 ms 596 KB Ok
47 Correct 6 ms 468 KB Ok
48 Correct 4 ms 596 KB Ok
49 Correct 3 ms 468 KB Ok
50 Correct 3 ms 596 KB Ok
51 Correct 4 ms 512 KB Ok
52 Correct 4 ms 596 KB Ok
53 Correct 4 ms 468 KB Ok
54 Correct 4 ms 468 KB Ok
55 Correct 10 ms 852 KB Ok
56 Correct 9 ms 896 KB Ok
57 Correct 10 ms 964 KB Ok
58 Correct 10 ms 916 KB Ok
59 Correct 12 ms 980 KB Ok
60 Correct 8 ms 852 KB Ok
61 Correct 13 ms 852 KB Ok
62 Correct 9 ms 948 KB Ok
63 Correct 12 ms 952 KB Ok
64 Correct 10 ms 980 KB Ok
65 Correct 181 ms 8284 KB Ok
66 Correct 246 ms 9408 KB Ok
67 Correct 199 ms 9556 KB Ok
68 Correct 166 ms 8952 KB Ok
69 Correct 163 ms 9372 KB Ok
70 Correct 152 ms 9616 KB Ok
71 Correct 162 ms 7544 KB Ok
72 Correct 131 ms 8928 KB Ok
73 Correct 192 ms 9776 KB Ok
74 Correct 150 ms 7604 KB Ok
75 Correct 193 ms 8488 KB Ok
76 Correct 158 ms 10524 KB Ok
77 Correct 168 ms 8136 KB Ok
78 Correct 175 ms 9436 KB Ok
79 Correct 182 ms 9992 KB Ok
80 Correct 824 ms 22016 KB Ok
81 Correct 785 ms 21256 KB Ok
82 Correct 654 ms 20576 KB Ok
83 Correct 761 ms 20832 KB Ok
84 Correct 751 ms 19436 KB Ok
85 Correct 692 ms 19280 KB Ok
86 Correct 712 ms 19748 KB Ok
87 Correct 805 ms 20780 KB Ok
88 Correct 717 ms 21188 KB Ok
89 Correct 664 ms 21240 KB Ok
90 Correct 895 ms 20052 KB Ok
91 Correct 701 ms 20432 KB Ok
92 Correct 702 ms 21288 KB Ok
93 Correct 723 ms 21324 KB Ok
94 Correct 588 ms 19544 KB Ok
95 Correct 548 ms 23348 KB Ok
96 Correct 719 ms 31404 KB Ok
97 Correct 575 ms 27128 KB Ok
98 Correct 503 ms 33952 KB Ok
99 Correct 555 ms 28040 KB Ok
100 Correct 578 ms 23940 KB Ok
101 Correct 586 ms 35200 KB Ok
102 Correct 627 ms 32568 KB Ok
103 Correct 589 ms 27916 KB Ok
104 Correct 776 ms 30520 KB Ok
105 Correct 687 ms 39076 KB Ok
106 Correct 675 ms 39404 KB Ok
107 Correct 709 ms 29156 KB Ok
108 Correct 771 ms 32228 KB Ok
109 Correct 758 ms 31148 KB Ok
110 Execution timed out 2081 ms 50052 KB Time limit exceeded
111 Halted 0 ms 0 KB -