Submission #493096

#	Time	Username	Problem	Language	Result	Execution time	Memory
493096		baokhue232005	Nice sequence (IZhO18_sequence)	C++17	76 / 100	2091 ms	36972 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];
vector<int> chim;
int cnt[maxN];
int l, r;

bool solve(int rang){
    chim.clear();
    memset(cnt, 0, sizeof(cnt));
    for1(i, 0, rang){
        if(i >= m) ++cnt[i - m];
        if(i >= n) ++cnt[i];
    }
    vector<int> stk;
    for1(i, 0, rang) if(!cnt[i]) stk.pb(i);
    while(!stk.empty()){
        x = stk.back(); stk.pop_back();
        chim.pb(x);
        for(int cc : vc[x]){
            --cnt[cc]; if(!cnt[cc]) stk.pb(cc);
        }
    }
    if(chim.size() <= 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;
        for(int cc : chim){
            if(cc == 0) x = 0; else --x;
            a[cc] = x;
        }
        cout << l << endl;
        for1(i, 1, l) cout << a[i] - a[i - 1] << " ";
        cout << endl;
    }
}

Compilation message (stderr)

sequence.cpp: In function 'bool solve(int)':
sequence.cpp:50:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |     if(chim.size() <= rang) return 0;
      |        ~~~~~~~~~~~~^~~~~~~

• 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