Light OJ 1097 / PBDS

/***
 created: 2022-08-06-01.06.10
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

ll ans[200005],lim=1429455;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    ll n,m,i,j,k,l;

    ordered_set<ll>x;

    x.insert(0);

    for(i=1;i<lim;i+=2) x.insert(i);

    ans[1]=1;

    for(i=2;i<100003;i++)
    {
        if(i>=x.size()) break;

        m = *x.find_by_order(i);

        vector<ll>y;

        for(j=m;j<lim;j+=m)
        {
            if(j>=x.size()) break;

            y.push_back(*x.find_by_order(j));
        }

        for(auto d:y) x.erase(d);

        ans[i]=m;

    }

    test
    {
        cin>>n;
        cout<<"Case "<<cs<<": "<<ans[n]<<nl;
    }

    get_lost_idiot;
}