Josephus Problem I CSES solution vector related problem

 

problem: https://cses.fi/problemset/task/2162

#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;

#define ll long long int

#define endl "\n"

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

int main()

{

ios_base::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

ll n,i;

cin>>n;

vector<ll>v;

for(i=0;i<n;i++)

{

v.push_back(i+1);

}

while(v.size()>1)

{

vector<ll>v1;

for(i=0;i<v.size();i++)

{

if(i%2)

{

cout<<v[i]<<" ";

}

else v1.push_back(v[i]);

}

if((ll)v.size()%2==0)

{

v=v1;

}

else

{

ll r;

r=v1.back();

v.clear();

v.push_back(r);

for(i=0;i<v1.size()-1;i++)

{

v.push_back(v1[i]);

}

}

}

cout<<v[0]<<endl;

return 0;

}