Submission #493100

#	Time	Username	Problem	Language	Result	Execution time	Memory
493100		baokhue232005	Nice sequence (IZhO18_sequence)	C++17	76 / 100	2063 ms	36300 KiB

sequence

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

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

#define all(flg) flg.begin(), flg.end()
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 500005;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k;
int m;

vector<int> vc[maxN];
int chim[maxN];
int track = 0;
int cnt[maxN];
int l, r;
int stk[maxN];
int pinn;

bool solve(int rang){
    track = 0;
    pinn = 0;
    memset(cnt, 0, sizeof(cnt));
    for1(i, 0, rang){
        if(i >= m) ++cnt[i - m];
        if(i >= n) ++cnt[i];
    }
    for1(i, 0, rang) if(!cnt[i]) stk[++pinn] = i;
    while(pinn){
        x = stk[pinn--];
        chim[track++] = x;
        for(int cc : vc[x]){
            --cnt[cc]; if(!cnt[cc]) stk[++pinn] = cc;
        }
    }
    if(track <= rang) return 0;
    return 1;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int o; cin >> o; while(o--){
        cin >> n >> m;
        l = max(n, m) - 1; r = n + m;
        for1(i, 0, r){
            vc[i].clear();
            if(i >= m) vc[i].pb(i - m);
            if(i >= n) vc[i - n].pb(i);
        }
        while(l != r){
            int mid = (l + r + 1) / 2;
            if(solve(mid)) l = mid;
            else r = mid - 1;
        }
        solve(l);
        x = maxN;
        int cc;
        for1(i, 0, track - 1){
            if(chim[i] == 0) x = 0; else --x;
            a[chim[i]] = x;
        }
        cout << l << endl;
        for1(i, 1, l) cout << a[i] - a[i - 1] << " ";
        cout << endl;
    }
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:76:13: warning: unused variable 'cc' [-Wunused-variable]
   76 |         int cc;
      |             ^~

• 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