Submission #1073739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073739		Sputnik123	Nice sequence (IZhO18_sequence)	C++17	100 / 100	694 ms	52672 KiB

sequence

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define in insert
#define pll pair<ll,ll>
#define vpl vector<pll>
#define vll vector <ll>
#define vl vector<ll>
#define F first
#define S second
#define ll long long
#define all(v) v.begin(),v.end()
#define endl "\n"
#define ull unsigned long long
#define ld long double
using namespace std;
//using namespace __gnu_pbds;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
const ll sz= 9e5 + 5;
const ll inf=1e18;
const ll mod=1e9+7;
const ll mod2=998244353;
const ll eps = 1e-12;
const ll P1=47; // for hashing 
const ll P2=41; // for hashing 
//template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// ll idx = 1;
ll n, m, ln, pref[sz], a[sz];
bool used[sz];
vll order;
void dfs(ll node)
{
    if(used[node])
        return;
    used[node] = 1;
    if(node + n <= ln)
        dfs(node + n);
    if(node - m >= 0)
        dfs(node - m);
    order.push_back(node);
}
bool check(ll mid)
{
    order.clear();
    ln = mid;
    memset(used, 0, sizeof(used));
    for(ll i = 0 ; i <= ln; i++)
        dfs(i);
    for(ll i = 0; i <= ln; i++)
        pref[order[i]] = i + 1;
    for(ll i = n; i <= ln; i++)
        if(pref[i] - pref[i - n] >= 0)
            return 0;
    for(ll i = m; i <= ln; i++)
        if(pref[i] - pref[i - m] <= 0)
            return 0;
    for(ll i = 1; i <= ln; i++)
        a[i] = pref[i] - pref[i - 1];
    return 1;
}
void solve()
{
    cin >> n >> m;
    ll l = 1, r = max(n, m) * 2;
    while(l <= r)
    {
        ll mid = (l + r) / 2;
        if(check(mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    cout << l - 1 << "\n";
    for(ll i = 1; i <= l - 1; ++i)
        cout << a[i] << " ";
    cout << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long t = 1;
    cin >> t;
    while(t--)
    {	   
        // cout << "Case " << (int) ix <<":\n";
        solve();
        ///idx++;
    }
}
/* 
Note : don`t use fast input in interactive questions
Note : Compare long double with eps = 1e-12
*/

• 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