Advertisement
Saleh127

Light OJ 1097 / PBDS

Aug 5th, 2022
969
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None
  1. /***
  2.  created: 2022-08-06-01.06.10
  3. ***/
  4.  
  5. #include <bits/stdc++.h>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10. template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
  11. #define ll long long
  12. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  13. #define get_lost_idiot return 0
  14. #define nl '\n'
  15.  
  16. ll ans[200005],lim=1429455;
  17.  
  18. int main()
  19. {
  20.     ios_base::sync_with_stdio(0);
  21.     cin.tie(0);
  22.     cout.tie(0);
  23.  
  24.  
  25.     ll n,m,i,j,k,l;
  26.  
  27.     ordered_set<ll>x;
  28.  
  29.     x.insert(0);
  30.  
  31.     for(i=1;i<lim;i+=2) x.insert(i);
  32.  
  33.     ans[1]=1;
  34.  
  35.     for(i=2;i<100003;i++)
  36.     {
  37.         if(i>=x.size()) break;
  38.  
  39.         m = *x.find_by_order(i);
  40.  
  41.         vector<ll>y;
  42.  
  43.         for(j=m;j<lim;j+=m)
  44.         {
  45.             if(j>=x.size()) break;
  46.  
  47.             y.push_back(*x.find_by_order(j));
  48.         }
  49.  
  50.         for(auto d:y) x.erase(d);
  51.  
  52.         ans[i]=m;
  53.  
  54.     }
  55.  
  56.     test
  57.     {
  58.         cin>>n;
  59.         cout<<"Case "<<cs<<": "<<ans[n]<<nl;
  60.     }
  61.  
  62.     get_lost_idiot;
  63. }
  64.  
Advertisement
RAW Paste Data Copied
Advertisement