Submission #379151

#	Time	Username	Problem	Language	Result	Execution time	Memory
379151		syl123456	Nice sequence (IZhO18_sequence)	C++17	100 / 100	1835 ms	32868 KiB

sequence

#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;
bool check(int n, int m, int len) {
    ++len;
    vector<int> d(len, 0);
    for (int i = n; i < len; ++i) ++d[i];
    for (int i = m; i < len; ++i) ++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();
        if (i + n < len) if (--d[i + n] == 0) stk.push_back(i + n);
        if (i - m >= 0) if (--d[i - m] == 0) stk.push_back(i - m);
    }
    for (int i : d) if (i != 0) return false;
    return true;
}
vector<int> get(int n, int m, int len) {
    ++len;
    vector<int> d(len, 0);
    for (int i = n; i < len; ++i) ++d[i];
    for (int i = m; i < len; ++i) ++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--;
        if (i + n < len) if (--d[i + n] == 0) stk.push_back(i + n);
        if (i - m >= 0) if (--d[i - m] == 0) stk.push_back(i - m);
    }
    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)

sequence.cpp: In function 'int main()':
sequence.cpp:50:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |             int mid = l + r >> 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: 24 / 24