Pagini recente » Cod sursa (job #893176) | Cod sursa (job #329735) | Cod sursa (job #215894) | Cod sursa (job #2145164) | Cod sursa (job #716387)
Cod sursa(job #716387)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <string.h>
#include <vector>
#define MAX 100010
#define bit(x) (x & (x ^ (x - 1)))
#define pb push_back
using namespace std;
int n, ns, nr, x;
int sel[MAX], nra[MAX];
char strCit[MAX];
string str[MAX];
vector <string> vctStr;
int valAIB[MAX];
inline void addAIB(int loc)
{
for (int i = loc; i <= ns; i += bit(i))
valAIB[i]++;
}
inline int searchAIB()
{
int i = 1, loc = 0;
for (i = 1; i * 2 <= ns && valAIB[i] < nr; i *= 2);
for (; i; i /= 2)
if (valAIB[loc + i] < nr)
{
nr -= valAIB[loc + i];
loc += i;
}
return loc + 1;
}
inline bool cmp(const string &a, const string &b)
{
if (a.size() != b.size())
return a.size() < b.size();
else return a < b;
}
int main()
{
ifstream cin("nums.in");
ofstream cout("nums.out");
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> x;
cin >> strCit;
str[i] = strCit;
if (x)
vctStr.pb(strCit);
else nra[i] = 1;
}
sort(vctStr.begin(), vctStr.end(), cmp);
ns = vctStr.size();
for (int i = 1; i <= n; i++)
if (!nra[i])
{
vector <string>::iterator it = lower_bound(vctStr.begin(), vctStr.end(), str[i], cmp);
int loc = int(it - vctStr.begin()) + 1;
if (!sel[loc])
addAIB(loc), sel[loc] = 1;
}
else
{
nr = atoi(str[i].c_str());
cout << vctStr[searchAIB() - 1] << "\n";
}
return 0;
}