oj.uz

Submission #680644

# Submission time Handle Problem Language Result Execution time Memory
680644 2023-01-11T12:02:42 Z aidfnbvosdnvla Nice sequence (IZhO18_sequence) C++14
0 / 100
 1 ms 340 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> &dp, int lim, int v) {
    for (auto &it : g[v])
        if (it <= lim) {
            if (dp[it] != -1)
                dp[v] = max(dp[v], dp[it] + 1);
            else {
                dpfs(g, dp, lim, it);
                dp[v] = max(dp[v], dp[it] + 1);
            }
        }
    if (dp[v] == -1)
        dp[v] = 0;
}

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> dp(l + 1, -1);
    for (int i = 0; i <= l; ++i)
        if (dp[i] == -1)
            dpfs(g, dp, l, i);
    cout << l << "\n";
    for (int i = 1; i <= l; ++i) {
        cout << dp[i] - dp[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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Incorrect 1 ms 340 KB All the numbers must be nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Ok
2 Correct 0 ms 212 KB Ok
3 Incorrect 1 ms 212 KB All the numbers must be nonzero
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB All the numbers must be nonzero
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Incorrect 1 ms 340 KB All the numbers must be nonzero
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Incorrect 1 ms 340 KB All the numbers must be nonzero
3 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Ok
2 Incorrect 1 ms 340 KB All the numbers must be nonzero
3 Halted 0 ms 0 KB -