In this HackerEarth Retrieve passwords problem solution A password is a number that is exactly divisible by 9. It is the largest number that can be formed by rearranging all the available digits in a provided range (L, R) inclusive and adding another number of your own choice to this sequence at any position. The password is missing a digit that must be added. You are also given an encrypted number. You are also provided q queries. The queries could be of two types.
Update a digit at a position.
Determine the largest number that is divisible by 9 in the provided range with the mentioned conditions. In the provided mentioned number, print its xth digit.
You must retrieve the password.
HackerEarth Retrieve passwords problem solution.
#include <bits/stdc++.h>
#//include <ext/pb_ds/assoc_container.hpp>
#//include <ext/pb_ds/tree_policy.hpp>
#//include <ext/pb_ds/detail/standard_policies.hpp>
//using namespace __gnu_pbds;
using namespace std;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//insert(), find_by_order(), order_of_key()
typedef long long int ll;
typedef unsigned long long int llu;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
#define ref(i, n) for (int i = 0; i < n; ++i)
#define rer(i, n) for (int i = n; i >= 0; --i)
#define refv(i, n, k) for (int i = k; i <= n; ++i)
#define rerv(i, n, k) for (int i = k; i >= n; --i)
#define fi first
#define pii pair<int, int>
#define piii pair<pii, int>
#define priority_queue_2 priority_queue<int, vector<int>, greater<int>>
#define se second
#define fast1 ios_base::sync_with_stdio(false)
#define fast2 cin.tie(NULL)
inline void pin(int n)
{
printf("%dn", n);
}
#define onec(x) __builtin_popcount(x);
#define all(x) x.begin(), x.end()
double PI = acos(-1);
const int inf = 0x3f3f3f3f;
#define sv()
int t;
scanf("%d", &t);
while (t--)
#define MOD 1000000007
#define TRACE
#ifdef TRACE
#define trace1(x) cerr << #x << ": " << x << endl;
#define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z) cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
#else
#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)
#endif
struct node
{
vector<int> p;
node()
{
p.resize(10, 0);
}
};
string s;
int n;
vector<node> v(1000005);
void update(int pos, int val, int no)
{
while (pos <= n)
{
v[pos].p[no] += val;
pos += pos & (-pos);
}
}
int sum(int pos, int no)
{
int s = 0;
while (pos > 0)
{
s += v[pos].p[no];
pos -= pos & (-pos);
}
return s;
}
int main()
{
bool ti= false;
fast1;
fast2;
cin >> s;
n = s.size();
clock_t start, end;
start = clock();
assert(n <= 1000000);
for (int i = 0; i < n; i++)
update(i + 1, 1, s[i] - '0');
int q;
cin >> q;
assert(q <= 500000);
vector<int> m(10, 0);
while (q--)
{
int t;
cin >> t;
assert(t == 2 || t == 1);
if (t == 1)
{
int x, y;
cin >> x >> y;
assert(x>0 && x <= n);
assert(y >= 0 && y < 10);
int old = s[x-1] - '0';
if(old==y)
continue;
s[x-1] = (char)(y + '0');
update(x , -1, old);
update(x , 1, y);
//cout<< s << endl;
}
else
{
int l, r, x;
cin >> l >> r >> x;
assert(l <= n && r >= l && r <= n && l>0);
assert(x>0 && x <= (r - l + 2));
for (int i = 0; i < 10; i++)
{
m[i] = sum(r, i);
m[i] -= sum(l-1, i);
//trace2(i,m[i]);
}
int ss = 0;
for (int i = 1; i < 10; i++)
{
ss += ((i % 9) * (m[i] % 9)) % 9;
ss %= 9;
}
m[9 - ss]++;
for (int i = 9; i >= 0; i--)
{
if (m[i] >= x)
{
cout << i << endl;
break;
}
x -= m[i];
}
}
}
end = clock();
if(ti){
double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
cout << "Time taken by program is : " << fixed
<< time_taken << setprecision(5);
cout << " sec " << endl;}
return 0;
}