Submission #493100

#TimeUsernameProblemLanguageResultExecution timeMemory
493100baokhue232005Nice sequence (IZhO18_sequence)C++17
76 / 100
2063 ms36300 KiB
/*
#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;
      |             ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...