Submission #1305155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305155		LIA	Nice sequence (IZhO18_sequence)	C++17	100 / 100	1382 ms	84780 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i,s,e)for(ll i =s;i<e;++i)





v<v<ll>> g;
v<ll> pre;
v<ll> in;
void topo() {
    queue<ll> q;
    lp(i,0,1e6) if (in[i]==0) q.push(i);
    ll cnt =0;
    while (!q.empty()) {
        auto nd = q.front();
        q.pop();
        pre[nd] =cnt++;
        for (auto it : g[nd]) {
            in[it]--;
            if (in[it]==0) {
                // pre[it] = cnt++;
                q.push(it);
            }
        }
    }
}
void solve() {
    ll n,m;
    cin>>n>>m;
    g.clear();
    g.resize(1e6);
    pre.assign(1e6,0);
    in.assign(1e6,0);
    ll ans = n+m -gcd(n,m)-1;
    cout<<ans<<endl;
    lp(i,0,ans) {
        if (i+n <=ans) {
            g[i+n].push_back(i);
            in[i]++;
        }
        if (i+m <=ans) {
            g[i].push_back(i+m);
            in[i+m]++;

        }
    }

    topo();

    lp(i,1,ans+1) {
        cout<<(i==0 ? pre[i] : pre[i]-pre[i-1])<<" ";
    }
}
int main() {
ll t; cin>>t;
    while (t--) {
        solve();
    }
}

• 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