Submission #493069

#	Time	Username	Problem	Language	Result	Execution time	Memory
493069		baokhue232005	Nice sequence (IZhO18_sequence)	C++14	0 / 100	23 ms	24320 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 int long long
#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();
    for1(i, 0, rang) cnt[i] = 0;
    for1(i, 0, rang){
        vc[i].clear();
        if(i >= m){
            vc[i].pb(i - m);
            ++cnt[i - m];
        }
        if(i >= n){
            vc[i - n].pb(i);
            ++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;
    x = maxN;
    for(int cc : chim){
        if(cc == 0) x = 0; else --x;
        a[cc] = x;
    }
}

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

Compilation message (stderr)

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

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 14
• Subtask 4: 0 / 15
• Subtask 5: 0 / 14
• Subtask 6: 0 / 18
• Subtask 7: 0 / 24