Submission #1307156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307156		jahongir	Nice sequence (IZhO18_sequence)	C++20	76 / 100	2094 ms	56896 KiB

sequence

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(a) a.begin(),a.end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef unsigned long long ull;
typedef vector<int> vi;


const int mxn = 1e6;
vector<int> g[mxn];
int indeg[mxn], pref[mxn];


void solve(){
    int n,m; cin >> n >> m;

    int l = 0, r = mxn;

    while(l+1 < r){
        int mid = (l+r)>>1;

        indeg[0] = 0;
        g[0].clear();
        for(int i = 1; i <= mid; i++){
            indeg[i] = 0;
            g[i].clear();
            if(i >= m){
                g[i].push_back(i-m);
                indeg[i-m]++;
            }
            if(i >= n){
                g[i-n].push_back(i);
                indeg[i]++;
            }
        }

        queue<int> qu;
        int cnt = 0;
        for(int i = 0; i <= mid; i++) if(indeg[i]==0)
            qu.push(i);
            
        while(!qu.empty()){
            auto u = qu.front(); qu.pop();
            cnt++;

            for(auto v : g[u])
                if(--indeg[v]==0)
                    qu.push(v);
        }

        if(cnt < mid) r = mid;
        else l = mid;
    }

    indeg[0] = 0;
    g[0].clear();
    for(int i = 1; i <= l; i++){
        indeg[i] = 0;
        g[i].clear();
        if(i >= m){
            g[i].push_back(i-m);
            indeg[i-m]++;
        }
        if(i >= n){
            g[i-n].push_back(i);
            indeg[i]++;
        }
    }

    queue<int> qu;
    int cnt = l;
    for(int i = 0; i <= l; i++) if(indeg[i]==0)
        qu.push(i);

    while(!qu.empty()){
        auto u = qu.front(); qu.pop();
        pref[u] = cnt--;
        for(auto v : g[u]) if(--indeg[v]==0)
            qu.push(v);
    }



    cout << l << '\n';
    for(int i = 1; i <= l; i++)
        cout << pref[i]-pref[i-1] << ' ';
    cout << '\n';
}   


signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    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: 0 / 24