Submission #379128

#TimeUsernameProblemLanguageResultExecution timeMemory
379128syl123456Birthday gift (IZhO18_treearray)C++17
0 / 100
1 ms364 KiB
#include <bits/stdc++.h>
#define all(i) i.begin(), i.end()
#define rall(i) i.rbegin(), i.rend()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
int d[400005];
bool check(int n, int m, int len) {
    ++len;
    vector<vector<int>> g(len);
    memset(d, 0, sizeof(int) * len);
    for (int i = n; i < len; ++i) g[i - n].push_back(i), ++d[i];
    for (int i = m; i < len; ++i) g[i].push_back(i - m), ++d[i - m];
    vector<int> stk;
    for (int i = 0; i < len; ++i) if (d[i] == 0) stk.push_back(i);
    while (!stk.empty()) {
        int i = stk.back();
        stk.pop_back();
        for (int j : g[i])
            if (--d[j] == 0) stk.push_back(j);
    }
    for (int i : d) if (i != 0) return false;
    return true;
}
vector<int> get(int n, int m, int len) {
    ++len;
    vector<vector<int>> g(len);
    memset(d, 0, sizeof(int) * len);
    for (int i = n; i < len; ++i) g[i - n].push_back(i), ++d[i];
    for (int i = m; i < len; ++i) g[i].push_back(i - m), ++d[i - m];
    vector<int> stk, ans(len);
    for (int i = 0; i < len; ++i) if (d[i] == 0) stk.push_back(i);
    int tmp = len;
    while (!stk.empty()) {
        int i = stk.back();
        stk.pop_back();
        ans[i] = tmp--;
        for (int j : g[i])
            if (--d[j] == 0) stk.push_back(j);
    }
    for (int i = len - 1; i; --i) ans[i] = ans[i] - ans[i - 1];
    return ans;
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int l = max(n, m) - 1, r = n + m - 1;
        while (l < r - 1) {
            int mid = l + r >> 1;
            if (check(n, m, mid)) l = mid;
            else r = mid;
        }
        vector<int> ans = get(n, m, l);
        cout << l << '\n';
        for (int i = 1; i <= l; ++i) cout << ans[i] << ' ';
        cout << '\n';
    }
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:53:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |             int mid = l + r >> 1;
      |                       ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...