Submission #680648

#	Time	Username	Problem	Language	Result	Execution time	Memory
680648		aidfnbvosdnvla	Nice sequence (IZhO18_sequence)	C++14	76 / 100	2081 ms	50052 KiB

sequence

//#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 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 0 / 24