oj.uz

Submission #680647

# Submission time Handle Problem Language Result Execution time Memory
680647 2023-01-11T12:11:15 Z aidfnbvosdnvla Nice sequence (IZhO18_sequence) C++14
34 / 100
 2000 ms 25104 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;
    int l = 0, r = n + m + 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 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 324 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 316 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 1 ms 320 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 320 KB Ok
12 Correct 1 ms 324 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Ok
2 Correct 1 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 166 ms 656 KB Ok
7 Execution timed out 2084 ms 2064 KB Time limit exceeded
8 Halted 0 ms 0 KB -

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 1 ms 212 KB Ok
4 Correct 1 ms 212 KB Ok
5 Correct 1 ms 212 KB Ok
6 Correct 1 ms 316 KB Ok
7 Correct 1 ms 212 KB Ok
8 Correct 0 ms 320 KB Ok
9 Correct 1 ms 212 KB Ok
10 Correct 0 ms 212 KB Ok
11 Correct 1 ms 212 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 1 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 Execution timed out 2077 ms 25104 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 324 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 316 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 1 ms 320 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 320 KB Ok
12 Correct 1 ms 324 KB Ok
13 Correct 0 ms 212 KB Ok
14 Correct 0 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 1 ms 316 KB Ok
19 Correct 1 ms 212 KB Ok
20 Correct 0 ms 320 KB Ok
21 Correct 1 ms 212 KB Ok
22 Correct 0 ms 212 KB Ok
23 Correct 1 ms 212 KB Ok
24 Correct 16 ms 724 KB Ok
25 Correct 16 ms 864 KB Ok
26 Correct 21 ms 700 KB Ok
27 Correct 28 ms 696 KB Ok
28 Correct 14 ms 744 KB Ok
29 Correct 32 ms 772 KB Ok
30 Correct 14 ms 628 KB Ok
31 Correct 23 ms 904 KB Ok
32 Correct 21 ms 672 KB Ok
33 Correct 22 ms 748 KB Ok
34 Correct 846 ms 1080 KB Ok
35 Correct 1624 ms 1128 KB Ok
36 Correct 1194 ms 1336 KB Ok
37 Correct 1646 ms 1088 KB Ok
38 Correct 1525 ms 1152 KB Ok
39 Correct 828 ms 1180 KB Ok
40 Correct 1664 ms 1356 KB Ok
41 Correct 1734 ms 1192 KB Ok
42 Correct 945 ms 1196 KB Ok
43 Correct 1636 ms 1372 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 324 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 316 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 1 ms 320 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 320 KB Ok
12 Correct 1 ms 324 KB Ok
13 Correct 0 ms 212 KB Ok
14 Correct 1 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 166 ms 656 KB Ok
19 Execution timed out 2084 ms 2064 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 324 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 316 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 1 ms 320 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 1 ms 340 KB Ok
11 Correct 1 ms 320 KB Ok
12 Correct 1 ms 324 KB Ok
13 Correct 0 ms 212 KB Ok
14 Correct 1 ms 212 KB Ok
15 Correct 1 ms 212 KB Ok
16 Correct 1 ms 212 KB Ok
17 Correct 1 ms 212 KB Ok
18 Correct 166 ms 656 KB Ok
19 Execution timed out 2084 ms 2064 KB Time limit exceeded
20 Halted 0 ms 0 KB -